莫队算法：解决一切区间问题。o(n sqrt(n)).离线一般处理1e4

普通莫队算法解决无修改区间查询问题。

讯享网

//A[i]为输入数组 //B[i]为每个询问区间 //MonAns:区间l,r中不同数的个数，不同的题目求的不同，具体该它 //cnt[i]表示区间中数i的个数 #include <cstdio> #include <algorithm> using namespace std; int const SIZE = 30100; int const BLOCK_SIZE = 200;//分块大小为接近根号n的整数，这样容易调试 struct _t{ int s,e; int idx; }; bool operator < (_t const&lhs,_t const&rhs){ int ln = lhs.s / BLOCK_SIZE; int rn = rhs.s / BLOCK_SIZE; return ln < rn || ( ln == rn && lhs.e < rhs.e ); } int N,Q; int A[SIZE]; _t B[SIZE ]; int Ans[SIZE ]; int Cnt[SIZE ] = {0}; void read(){ scanf("%d",&N); for(int i=1;i<=N;++i)scanf("%d",A+i); scanf("%d",&Q); for(int i=0;i<Q;++i){ scanf("%d%d",&B[i].s,&B[i].e); B[i].idx = i; } } int MoAns; inline void insert(int n){ ++Cnt[n]; if ( 1 == Cnt[n] ) ++MoAns; } inline void remove(int n){ --Cnt[n]; if ( 0 == Cnt[n] ) --MoAns; } void Mo(){ sort(B,B+Q); int curLeft = 1; int curRight = 0; MoAns = 0; for(int i=0;i<Q;++i){ while( curRight < B[i].e ) insert(A[++curRight]); while( curLeft > B[i].s ) insert(A[--curLeft]); while( curRight > B[i].e ) remove(A[curRight--]); while( curLeft < B[i].s ) remove(A[curLeft++]); Ans[B[i].idx] = MoAns; } } int main(){ //freopen("1.txt","r",stdin); read(); Mo(); for(int i=0;i<Q;++i)printf("%d\n",Ans[i]); return 0; } 

G、区间求和

讯享网//A[i]为输入数组 //B[i]为每个询问区间 //MonAns:区间l,r中不同数的个数，不同的题目求的不同，具体该它 //cnt[i]表示区间中数i的个数 #include <cstdio> #include <algorithm> typedef long long ll; using namespace std; int const SIZE = ; int const BLOCK_SIZE = 350;//分块大小为接近根号n的整数，这样容易调试 struct _t{ int s,e; int idx; }; bool operator < (_t const&lhs,_t const&rhs){ int ln = lhs.s / BLOCK_SIZE; int rn = rhs.s / BLOCK_SIZE; return ln < rn || ( ln == rn && lhs.e < rhs.e ); } int N,Q; int A[SIZE]; _t B[]; ll Ans[]; int Cnt[] = {0}; void read(){ scanf("%d%d",&N,&Q); for(int i=1;i<=N;++i)scanf("%d",A+i); for(int i=0;i<Q;++i){ scanf("%d%d",&B[i].s,&B[i].e); B[i].idx = i; } } ll MoAns; inline void insert(int n){ ++Cnt[n]; //if ( 1 == Cnt[n] ) ++MoAns; MoAns+=2LL*Cnt[n]*n-n; } inline void remove(int n){ --Cnt[n]; //if ( 0 == Cnt[n] ) --MoAns; MoAns-=2LL*Cnt[n]*n+n; } void Mo(){ sort(B,B+Q); int curLeft = 1; int curRight = 0; MoAns = 0; for(int i=0;i<Q;++i){ while( curRight < B[i].e ) insert(A[++curRight]); while( curLeft > B[i].s ) insert(A[--curLeft]); while( curRight > B[i].e ) remove(A[curRight--]); while( curLeft < B[i].s ) remove(A[curLeft++]); Ans[B[i].idx] = 1LL*MoAns; } } int main(){ read(); Mo(); for(int i=0;i<Q;++i)printf("%lld\n",Ans[i]); return 0; }

带单点修改莫队算法

theme：n个元素，q次询问：，num(ai​)代表aia_iai​在这个区间中出现的次数。

//theme：n个元素，q次询问：l,r区间中a[i]*num[i]之和。num(ai​)代表aia_iai​在这个区间中出现的次数。 #include <cstdio> #include <list> #include <algorithm> using namespace std; typedef long long ll; int const SIZE = 10010; int const BLOCK_SIZE = 300;//分块大小为接近根号n的整数，这样容易调试 struct _t{ int s,e; int idx; int changedCnt; }Query[SIZE]; bool operator < (_t const&lhs,_t const&rhs){ int la = lhs.s / BLOCK_SIZE; int ra = rhs.s / BLOCK_SIZE; int lb = lhs.e / BLOCK_SIZE; int rb = rhs.e / BLOCK_SIZE; return la < ra || ( la == ra && lb < rb )||(la==ra&&lb==rb&&lhs.changedCnt<rhs.changedCnt); } struct change_t{ int pos; //改变的位置 int newColor;//改变前的值 int preColor;//改变后的值 }Change[SIZE]; int N,M;//N为元素个数，M为总操作数 int A[SIZE]; int PreColor[SIZE]; int MoAns; int Cnt[]; int QCnt,CCnt;//查询、修改的个数(查询修改从0开始编号) int Ans[SIZE]; int curLeft,curRight,curChangedCnt; void read(){ scanf("%d",&N); scanf("%d",&M); for(int i=1;i<=N;++i)scanf("%d",A+i),PreColor[i]=A[i]; QCnt=CCnt=0; char cmd; int l,r; for(int i=0;i<M;++i){ getchar(); cmd=getchar(); scanf("%d%d",&l,&r); if(cmd=='Q') { Query[QCnt].s=l; Query[QCnt].e=r; Query[QCnt].idx=QCnt; Query[QCnt++].changedCnt=CCnt; } else { Change[CCnt].preColor=PreColor[l]; Change[CCnt].pos=l; Change[CCnt++].newColor=PreColor[l]=r; } } } inline void insert(int n){ ++Cnt[n]; if(1==Cnt[n]) ++MoAns; } inline void remove(int n){ --Cnt[n]; if(0==Cnt[n]) --MoAns; } inline void change(int pos,int color) { if(curLeft<=pos&&pos<=curRight) { remove(A[pos]); insert(color); } A[pos]=color; } void Mo(){ sort(Query,Query+QCnt); curLeft = 1; curRight = 0;//下标 curChangedCnt=0; MoAns = 0; for(int i=0;i<QCnt;++i){ while(curChangedCnt<Query[i].changedCnt) change(Change[curChangedCnt].pos,Change[curChangedCnt].newColor),++curChangedCnt; while(curChangedCnt>Query[i].changedCnt) --curChangedCnt,change(Change[curChangedCnt].pos,Change[curChangedCnt].preColor); while( curRight < Query[i].e ) insert(A[++curRight]); while( curLeft > Query[i].s ) insert(A[--curLeft]); while( curRight > Query[i].e ) remove(A[curRight--]); while( curLeft < Query[i].s ) remove(A[curLeft++]); Ans[Query[i].idx]=MoAns; } } int main(){ //freopen("1.txt","r",stdin); read(); Mo(); for(int i=0;i<QCnt;++i)printf("%d\n",Ans[i]); return 0; }