这几天感觉要学的要做的有点多，就偷了个懒没写笔记，赶紧补一下
莫队嘛，一个离线处理各种区间（或树上）询问的神奇算法
简单而言，按左端点排个序然后指针l,r递推就好了
复杂度证明貌似是不待修改的n^1.5，带修改的n^5/3（证明又与我何干呢）
这东西我只学了一天左右，感觉常规题没什么亮点，毒瘤起来就不知道了
然后我分享一下无修莫队和带修莫队的两道例题做法，回滚的话后面补吧
小z的袜子https://www.luogu.org/problemnew/show/P1494
抽到一样袜子的情况总和为 cnt[i]∗(cnt[i]−1)(cnt[i]>=2)(1<=i<=n)
那么请手推当cnt[i]+1或cnt[i]-1时的情况
#include<bits/stdc++.h> #define int long long//这题貌似会爆int using namespace std; inline int read(){ int w=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ w=(w<<3)+(w<<1)+ch-48; ch=getchar(); } return w*f; } int n,m,block,ans,pos[500010],col[500010],cnt[500010]; struct Query{ int l,r,ans1,ans2,id;//l,r表示当前询问区间，ans1,ans2表示答案的分子分母，id就是这个问题的序号 }q[500010]; inline int comp1(Query a,Query b){ if(pos[a.l]==pos[b.l]) return a.r<b.r; else return a.l>b.l;//如果左端点所在块一样，按右端点排序，否则按左端点排序 }//这个貌似有很多种写法，面向数据编程吧(逃 inline int comp2(Query a,Query b){ return a.id<b.id;//回到最初的顺序 } inline void add(int x){ ans+=cnt[col[x]]*2,cnt[col[x]]++;return;//当你加为一个颜色加一的时候答案的变化 } inline void del(int x){ if(cnt[col[x]]>=1)ans-=(cnt[col[x]]-1)*2,cnt[col[x]]--;return;//当你删一个颜色的时候答案的变化 } inline void work(){ int i,j,k;int l=1,r=0;//这个地方我建议写l=1,r=0，这表示一个空区间，如果写l=0,r=0会发生一些奇怪边界问题 for(i=1;i<=m;i++){ if(q[i].l==q[i].r){ q[i].ans1=0;q[i].ans2=1;continue;//题目要求特判的情况 } else{
/*
四种情况，分别讨论，然而在add的时候应该先移动指针再修改，del的话先修改再移动指针
*/ while(l>q[i].l) add(--l); while(r<q[i].r) add(++r); while(l<q[i].l) del(l++); while(r>q[i].r) del(r--); q[i].ans1=ans;q[i].ans2=(r-l+1)*(r-l); } } } inline int GCD(int x,int y){//题目要求的 if(!y) return x; else return GCD(y,x%y); } signed main(){//按题目要求走就好了 n=read();m=read();int i,j,k;int block=sqrt(n); for(i=1;i<=n;i++){ col[i]=read();pos[i]=(i-1)/block+1; } for(i=1;i<=m;i++){ q[i].id=i;q[i].l=read();q[i].r=read(); } sort(q+1,q+m+1,comp1); work(); sort(q+1,q+m+1,comp2); for(i=1;i<=m;i++){ if(q[i].ans1==0&&q[i].ans2==1){ } else{ int x=GCD(q[i].ans1,q[i].ans2); q[i].ans1/=x;q[i].ans2/=x; } printf("%lld/%lld ",q[i].ans1,q[i].ans2); } return 0; }