tcga做多因素分析的网站,抚州做网站的公司,精品个人网站源码下载,音乐模板wordpress它来了#xff01;
分析一下第一个操作#xff0c;不是写过嘛#xff0c;并查集
分析一下第二个操作#xff0c;二分套二分答案
拿下了这题
仔细分析#xff0c;貌似时间复杂度是错的
我们考虑块套块 时间复杂度
对1e5的值域进行分块
求k值我们可以先找是第几个块
分析一下第一个操作不是写过嘛并查集
分析一下第二个操作二分套二分答案
拿下了这题
仔细分析貌似时间复杂度是错的
我们考虑块套块 时间复杂度
对1e5的值域进行分块
求k值我们可以先找是第几个块再找到是块内第几个数
如何做
散块
我们可以做一个桶来临时存数量
整块
我们可以做一个前缀和O(1)询问范围内的数量与k的关系小于k我们就累加否则我们就找到了那个块找到第几个数也是一样的原理
因此我们维护bc[i][j] i个块内 j个值域块内的数量c[i][j] i个块内j个数值的数量那么散块也需要临时维护t1[i]第i个值域块的数量,t2[i]第i个数值的数量提前预处理
如果只有一个散块可以直接找nth_element
inline int kth(int l,int r,int k){int ppos[l];int qpos[r];ll res0;ll sum0;if(pq){pushdown(p);for(int il;ir;i){t2[i]a[i];}nth_element(t2l,t2lk-1,t2r1);rest2[lk-1];//0-kfor(int il;ir;i){t2[i]0;//清空}}else{//散块计数pushdown(p);for(int il;iR[p];i){t1[PP[a[i]]];t2[a[i]];}pushdown(q);for(int iL[q];ir;i){t1[PP[a[i]]];t2[a[i]];}//整块处理for(int i1;itt;i){//枚举值域块if(sumt1[i]bc[q-1][i]-bc[p][i]k){//[p1,q-1]for(int jLL[i];jRR[i];j){//枚举块内值域if(sumt2[j]c[q-1][j]-c[p][j]k){//找到位置//查询结束前清空for(int ol;oR[p];o){//[l,R[p]]t1[PP[a[o]]]--;t2[a[o]]--;}for(int oL[q];or;o){//[R[q],r]t1[PP[a[o]]]--;t2[a[o]]--;}//返回答案return j;//kth}else{sum(t2[j]c[q-1][j]-c[p][j]);}}}else{sum(t1[i]bc[q-1][i]-bc[p][i]);//累加}}}return res;
}
结合操作一
我们维护val[i][j] 记录在第i块内的第j个位置的值index[i][j]记录在第i个块内的a[j]在什么位置
loc[i]记录index[i][a[i]]
预处理
inline void build(int id){//建立关系int cur0;//根标号for(int i1;iblo;i){//清空关系index[id][val[id][i]]0;}for(int iL[id];iR[id];i){if(!index[id][a[i]]){cur;index[id][a[i]]cur;val[id][cur]a[i];}loc[i]index[id][a[i]];}
}
这样我们可以通过3个数组推出a[i]的真实值
inline void pushdown(int id){//还原数组for(int iL[id];iR[id];i){a[i]val[id][loc[i]];//}
}
合并操作
inline void merge(int id,int x,int y){//合并index[id][y]index[id][x];val[id][index[id][x]]y;index[id][x]0;
} 修改我们考虑差分再单块处理后前缀和时间复杂度不变
散块
直接modify
整块
如果没有x,直接跳过
如果没有x,有y 转移贡献
如果有x,有y 合并
inline void modify(int l,int r,int x,int y){//散块for(int il;ir;i){if(a[i]x){bc[pos[i]][PP[x]]--;bc[pos[i]][PP[y]];c[pos[i]][x]--;c[pos[i]][y];a[i]y;}}
}
inline void update(int l,int r,int x,int y){//处理每个块的数据可以差分处理if((xy) || c[pos[r]][x]-c[pos[l]-1][x]0 ){//xy 或者是 区间内没有xreturn;}//差分单独处理这块的答案for(int it;ipos[l];i--){bc[i][PP[x]]-bc[i-1][PP[x]];bc[i][PP[y]]-bc[i-1][PP[y]];c[i][x]-c[i-1][x];c[i][y]-c[i-1][y];}int ppos[l];int qpos[r];if(pq){pushdown(p);modify(l,r,x,y);//散块build(p);for(int ip;it;i){bc[i][PP[x]]bc[i-1][PP[x]];bc[i][PP[y]]bc[i-1][PP[y]];c[i][x]c[i-1][x];c[i][y]c[i-1][y]; }}else{pushdown(p);modify(l,R[p],x,y);//散块build(p);pushdown(q);modify(L[q],r,x,y);//散块build(q);for(int ip1;iq-1;i){if(!c[i][x]){//不存在x continue;}else if(c[i][y]){pushdown(i);modify(L[i],R[i],x,y);build(i); }else{bc[i][PP[y]]c[i][x];bc[i][PP[x]]-c[i][x];c[i][y]c[i][x];c[i][x]0;merge(i,x,y);}}for(int ip;it;i){bc[i][PP[x]]bc[i-1][PP[x]];bc[i][PP[y]]bc[i-1][PP[y]];c[i][x]c[i-1][x];c[i][y]c[i-1][y]; }}
}
完整代码
#includeiostream
#includealgorithm
#includecmath
#includevector
#define INF (1ll60)
using namespace std;
typedef long long ll;
namespace Lan {inline string sread() {string s ;char egetchar();while(e ||e\n)egetchar();while(e! e!\n)se,egetchar();return s;}inline void swrite(string s){for(char e:s)putchar(e);printf(\n);}inline ll read() {ll x0,y1;char cgetchar();while(!isdigit(c)){if(c-)y-1;cgetchar();}while(isdigit(c)){x(x3)(x1)(c^48);cgetchar();}return x*y;}inline void write(ll x) {if(x0){x-x,putchar(-);}ll sta[35],top0;do sta[top]x%10,x/10;while(x);while(top)putchar(sta[--top]0);}
}using namespace Lan;
const int N1e59;
const int M1e52;
const int B5e29;
int a[N],bc[B][N],c[B][N];//块内的值域块中的数的数量以及该数值的数
int L[B],R[B],pos[N];
int LL[B],RR[B],PP[N];
int index[B][N],val[B][N],loc[N];
int t1[B],t2[N];//散块查kth
int blo,t,tt;
inline void merge(int id,int x,int y){//合并index[id][y]index[id][x];val[id][index[id][x]]y;index[id][x]0;
}
inline void pushdown(int id){//还原数组for(int iL[id];iR[id];i){a[i]val[id][loc[i]];//}
}
inline void build(int id){//建立关系int cur0;//根标号for(int i1;iblo;i){//清空关系index[id][val[id][i]]0;}for(int iL[id];iR[id];i){if(!index[id][a[i]]){cur;index[id][a[i]]cur;val[id][cur]a[i];}loc[i]index[id][a[i]];}
}
inline void modify(int l,int r,int x,int y){//散块for(int il;ir;i){if(a[i]x){bc[pos[i]][PP[x]]--;bc[pos[i]][PP[y]];c[pos[i]][x]--;c[pos[i]][y];a[i]y;}}
}
inline void update(int l,int r,int x,int y){//处理每个块的数据可以差分处理if((xy) || c[pos[r]][x]-c[pos[l]-1][x]0 ){//xy 或者是 区间内没有xreturn;}//差分单独处理这块的答案for(int it;ipos[l];i--){bc[i][PP[x]]-bc[i-1][PP[x]];bc[i][PP[y]]-bc[i-1][PP[y]];c[i][x]-c[i-1][x];c[i][y]-c[i-1][y];}int ppos[l];int qpos[r];if(pq){pushdown(p);modify(l,r,x,y);//散块build(p);for(int ip;it;i){bc[i][PP[x]]bc[i-1][PP[x]];bc[i][PP[y]]bc[i-1][PP[y]];c[i][x]c[i-1][x];c[i][y]c[i-1][y]; }}else{pushdown(p);modify(l,R[p],x,y);//散块build(p);pushdown(q);modify(L[q],r,x,y);//散块build(q);for(int ip1;iq-1;i){if(!c[i][x]){//不存在x continue;}else if(c[i][y]){pushdown(i);modify(L[i],R[i],x,y);build(i); }else{bc[i][PP[y]]c[i][x];bc[i][PP[x]]-c[i][x];c[i][y]c[i][x];c[i][x]0;merge(i,x,y);}}for(int ip;it;i){bc[i][PP[x]]bc[i-1][PP[x]];bc[i][PP[y]]bc[i-1][PP[y]];c[i][x]c[i-1][x];c[i][y]c[i-1][y]; }}
}
inline int kth(int l,int r,int k){int ppos[l];int qpos[r];ll res0;ll sum0;if(pq){pushdown(p);for(int il;ir;i){t2[i]a[i];}nth_element(t2l,t2lk-1,t2r1);rest2[lk-1];//0-kfor(int il;ir;i){t2[i]0;//清空}}else{//散块计数pushdown(p);for(int il;iR[p];i){t1[PP[a[i]]];t2[a[i]];}pushdown(q);for(int iL[q];ir;i){t1[PP[a[i]]];t2[a[i]];}//整块处理for(int i1;itt;i){//枚举值域块if(sumt1[i]bc[q-1][i]-bc[p][i]k){//[p1,q-1]for(int jLL[i];jRR[i];j){//枚举块内值域if(sumt2[j]c[q-1][j]-c[p][j]k){//找到位置//查询结束前清空for(int ol;oR[p];o){//[l,R[p]]t1[PP[a[o]]]--;t2[a[o]]--;}for(int oL[q];or;o){//[R[q],r]t1[PP[a[o]]]--;t2[a[o]]--;}//返回答案return j;//kth}else{sum(t2[j]c[q-1][j]-c[p][j]);}}}else{sum(t1[i]bc[q-1][i]-bc[p][i]);//累加}}}return res;
}
int main(){// ios::sync_with_stdio(false);// cin.tie(0),cout.tie(0);int n,m;nread(),mread();for(int i1;in;i){a[i]read();}//分块blosqrt(n);tsqrt(n);for(int i1;it;i){L[i](i-1)*t1;R[i]i*t;}if(R[t]n){t;L[t]R[t-1]1;R[t]n;}for(int i1;it;i){for(int jL[i];jR[i];j){pos[j]i;}}//值域分块ttsqrt(M);for(int i1;itt;i){LL[i](i-1)*tt1;RR[i]i*tt;}if(RR[tt]M){tt;LL[tt]RR[tt-1]1;RR[tt]M;}for(int i1;itt;i){for(int jLL[i];jRR[i];j){PP[j]i;}}//预处理//值域分块for(int i1;it;i){for(int j1;jt100;j){bc[i][j]bc[i-1][j];//块继承}for(int j1;jM;j){c[i][j]c[i-1][j];//数量继承}for(int jL[i];jR[i];j){bc[i][PP[a[j]]];//继续记录c[i][a[j]];}}//并查集for(int i1;it;i){build(i);}for(int i1;im;i){int op;opread();int l,r;lread(),rread();if(op1){int x,y;xread(),yread();update(l,r,x,y);}else{int k;kread();coutkth(l,r,k)\n;}}return 0;
}
学会了值域分块求k值学完第二分块并查集感觉第一分块的操作一并查集那块挺好写的
差分修改还是很妙的
下一个大分块 maybe 天降之物
