Introduction
Here are some of my thinking about DS.
All are written in the Chinese language and MarkDown&LateX.
If you can't understand what I'm talking about, you could use AI to help. I'm sure they are good at this.
I hope this can help you so here to share.
If there is a problem with the rendering format, you can open it on **https://www.luogu.me/article/5i00f2kz** for a better reading experience.
群论
将信息进行分类。
半群信息
满足结合律的信息。
即满足
Unable to parse markup [type=CF_MATHJAX]
\oplus$ 为信息运算。比如 $$$\max$$$ 运算就是半群，因为
Unable to parse markup [type=CF_MATHJAX]
\min$ 运算同理。所以我们可以在 $$$a\le b\le c\le d$$$ 时通过 $$$\min(\min_{i=a}^c,\min_{i=b}^d)$$$ 来获得 $$$\min_{i=a}^d$$$ 的结果。
或者取并集运算也是半群。
群信息：
存在逆运算的信息。
比如加法运算就是群，因为如果你知道 $$$y$$$ 是由 $$$a+x$$$ 得到的，同时知道 $$$x$$$ 的值，能够反推出 $$$a$$$ 的值。
而不是群的运算做不到，比如
Unable to parse markup [type=CF_MATHJAX]
\max(a,3)=3$，你不知道 $$$a$$$ 的值具体是多少。群信息满足差分性质。
所有群信息都是半群信息。
分块
对半群信息的平衡规划优化。
通过“整块懒标记，散点暴力做”平衡时间复杂度。
时间复杂度 $$$\mathcal{O}(B\times T_1+\frac{n}{B}\times T_2)\times C$$$，其中 $$$T_1,T_2$$$ 分别为单个整块、散块单个元素处理时间复杂度，$B$ 为块的个数。
显然 $$$B=1,n$$$ 时为暴力。
显然 $$$B\times T_1=\frac{n}{B}\times T_2$$$ 时达到最优，即 $B=\sqrt{\frac{T_2}{T_1}n}$，通常 $T_1=T_2=1$，可得 $B=\sqrt{n}$。
进阶地，我们可以根据修改与询问的比例调整块长。
预处理
计算 $\texttt{bk,L[i],R[i],bel[i]}$，分别表示块总数、每块左右端点、元素从属块编号。
:::success[代码] cpp int i;bk=sqrt(n);//根据上文公式具体计算 for(i=1;i;++i){ L[i]=R[i-1]+1, R[i]=min(n,L[i]+bk); if(R[i]==n) break; } bk=i; for(i=1;i<=bk;++i){ sum[i]=0;//初始化、预处理计算 for(int j=L[i];j<=R[i];++j) bel[j]=i;//记录从属块编号 } :::
区间开方求和
区间开方，区间求和，$n\le 5\times 10^4,a_i\le 2\times 10^9$ 。
思路：
Unable to parse markup [type=CF_MATHJAX]
\ge 6$ 次一定变为 $1$。只用管开根次数 $$$\le 5$$$ 的数，弄个链表指向下一个开根次数 $$$\le 5$$$ 的数然后暴力做，用分块或者其他任何数据结构维护做即可。
:::success[代码] cpp const int N=1e6+5; int n,m,tree[N],nxt[N]; inline int lowbit(int x){return x&(-x);} inline void add(int p,int x){ while(p<=n){ tree[p]+=x; p+=lowbit(p); } }//把第p个数字+x inline int get(int p){ int ans=0; while(p){ ans+=tree[p]; p-=lowbit(p); } return ans; }//数组中1~p的和 int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ int x;cin>>x; add(i,x); nxt[i]=i+1; } m=n; for(int i=1;i<=m;i++){ int k,l,r,FW_number; cin>>k>>l>>r>>FW_number; if(k==0){ for(int i=l,j=0;i<=r;i=nxt[i]){ int x=get(i)-get(i-1); int y=sqrt(x); add(i,y-x); if(y==1)nxt[j]=nxt[i]; j=i; } } if(k==1)cout<<get(r)-get(l-1)<<"\n"; } return 0; } :::
区间加乘
区间加法，区间乘法， $$$n\le 10^5,a_i\le 2\times 10^9$$$ 。
思路：
准备加法 $$$tag$$$ 和乘法 $$$tag$$$，每次操作前 $$$pushdown$$$ 即可。
注意预处理乘法 $$$tag$$$ 为 $$$1$$$，注意在 $$$main$$$ 函数内调用 $$$pre$$$ 。
:::success[代码] cpp typedef long long ll; const int N=1e6+5,mod=10007; int n,a[N],bk,L[N],R[N],bel[N]; ll mtag[N],atag[N]; void pre(){ bk=sqrt(n);int i; for(i=1;;++i){ L[i]=R[i-1]+1, R[i]=min(n,L[i]+bk); if(R[i]==n) break; } bk=i; for(int i=1;i<=bk;++i){ mtag[i]=1; for(int j=L[i];j<=R[i];++j) bel[j]=i; } } void ptag(int p){ if(atag[p]==0 and mtag[p]==1) return; for(int i=L[p];i<=R[p];++i) a[i]=a[i]*mtag[p]%mod+atag[p], a[i]%=mod; atag[p]=0,mtag[p]=1; } void mul(int l,int r,int c){ int x=bel[l],y=bel[r]; if(x==y){ ptag(x); for(int i=l;i<=r;++i) a[i]*=c, a[i]%=mod; return; } ptag(x),ptag(y); for(int i=x+1;i<y;++i) atag[i]*=c, atag[i]%=mod, mtag[i]*=c, mtag[i]%=mod; for(int i=l;i<=R[x];++i) a[i]*=c, a[i]%=mod; for(int i=L[y];i<=r;++i) a[i]*=c, a[i]%=mod; } void add(int l,int r,int c){ int x=bel[l],y=bel[r]; if(x==y){ ptag(x); for(int i=l;i<=r;++i) a[i]+=c, a[i]%=mod; return; } ptag(x),ptag(y); for(int i=x+1;i<=y-1;++i) atag[i]+=c, atag[i]%=mod; for(int i=l;i<=R[x];++i) a[i]+=c, a[i]%=mod; for(int i=L[y];i<=r;++i) a[i]+=c, a[i]%=mod; } int ask(int l){ int x=bel[l]; return (a[l]*mtag[x]+atag[x])%mod; } signed main(){ cin>>n; for(int i=1;i<=n;++i) cin>>a[i]; pre(); for(int i=1;i<=n;++i){ int op,l,r,c; cin>>op>>l>>r>>c; c%=mod; if(op==0) add(l,r,c); else if(op==1) mul(l,r,c); else cout<<ask(r)<<'\n'; } return 0; } :::
区间众数
无修改，查询区间值最小的众数。
思路：
求众数随机算法：在区间内随机选择 $$$30$$$ 个检验。
该方法在绝对众数题目中非常见效，本题由于存在“最小”二字，只有 80pts ，是考试骗分的有用技巧。
:::success[代码] cpp int vis[N],tim;//可持久化bool数组 int main(){ n=read(); for(int i=1;i<=n;++i) a[i]=b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;++i) if(i==1 or b[i]!=b[i-1]) mp[b[i]]=++tot; for(int i=1;i<=n;++i) b[mp[a[i]]]=a[i], a[i]=mp[a[i]]; for(int i=1;i<=n;++i) v[a[i]].push_back(i); for(int i=1;i<=n;++i){ ++tim; int x=read(),y=read(); int val=1e9,mx=-1; for(int f=1;f<=300;++f){ int i=a[rand()%(y-x+1)+x]; if(vis[i]==tim or (int)v[i].size()<mx) continue; vis[i]=tim; int l=0,r=v[i].size()-1; while(l<r){ int mid=l+r>>1; if(v[i][mid]>=x) r=mid; else l=mid+1; } int tmp=l; l=0,r=v[i].size()-1; while(l<r){ int mid=l+r+1>>1; if(v[i][mid]<=y) l=mid; else r=mid-1; } if(l-tmp+1>mx){ mx=l-tmp+1; val=b[i]; }else if(l-tmp+1==mx and b[i]<val) val=b[i]; } write(val); putchar(10); } return 0; } :::
也有分块做法，比较普通，不予展示。
树状数组
对满足**可减性（前缀）**、可加性的问题的“线性空间、单 $$$\log$$$ 时复”解法。
使用前缀和、二进制思想，$t_i=\sum a_j~\in[i-lowbit(i)+1,i]$。
显然 $$$\sum a_i(i\in[1,n])=t_n+t_{n-lowbit(n)}+t_{n-lowbit(n)-lowbit(n-lowbit(n))}...$$$
即可实现 $$$\mathcal{O}(\log)$$$ 的前缀查询。更多具体原理非考试关键，不赘述。
:::success[代码] cpp void add(int x,int c){ while(x<=n)tree[x]+=c,x+=-x&x; } ll ask(int x){ ll ret=0; while(x)ret+=tree[x],x-=-x&x; return ret; } :::
区修单查
考虑维护差分数组，区修单查 $$$\to$$$ 单修区查。
具体地，本题区修可看作在差分数组上对区间端点进行单修，本题单修可看作查询差分数组的前缀。
:::success[代码] cpp const int N=1e6+5; int a[N],n,q; ll tree[N]; void add(int x,int c){ while(x<=n) tree[x]+=c, x+=-x&x; } ll ask(int x){ ll ret=0; while(x) ret+=tree[x], x-=-x&x; return ret; } signed main(){ n=read(),q=read(); for(int i=1;i<=n;++i) a[i]=read(), add(i,a[i]-a[i-1]); for(int i=1;i<=q;++i){ int op=read(); if(op==1){ int l=read(),r=read(),x=read(); add(l,x),add(r+1,-x); } else{ int x=read(); write(ask(x)), putchar(10); } } return 0; } :::
区修区查
显然区查 $$$\sum_{i=1}^{x}\sum_{j=1}^{i}b_j$$$，其中 $$$b$$$ 为差分数组。
可得 $$$原式\=\sum_{i=1}^{x}b_i\times (x+1-i)\=(x+1)\times \sum_{i=1}^{x}b_i-\sum_{i=1}^{x}i\times b_i$$$
所以维护 $sum1_i\to b_i,\to i\times b_i$。
区修时 $$$sum2_l+=l\times c,~~sum2_{r+1}-=(r+1)\times c$$$，$$$sum1$$$ 同理。
:::success[代码] cpp const int N=1e6+5; int n,q; ll a[N]; struct BIT{ ll tree[N]; void add(int x,ll c){ while(x<=n) tree[x]+=c, x+=-x&x; } ll ask(int x){ ll ret=0; while(x) ret+=tree[x], x-=-x&x; return ret; } }t[2]; signed main(){ n=read(),q=read(); for(int i=1;i<=n;++i) a[i]=a[i-1]+read(); for(int i=1;i<=q;++i){ int op=read(),l=read(),r=read(); if(op==1){ int x=read(); t[0].add(l,x), t[0].add(r+1,-x), t[1].add(l,l*x), t[1].add(r+1,-x*(r+1)); } else{ int ans=a[r]-a[l-1]; ans+=(r+1)*t[0].ask(r)-l*t[0].ask(l-1); ans-=t[1].ask(r)-t[1].ask(l-1); write(ans), putchar(10); } } return 0; } :::
二维区修区查
类似于一维，$sum1_{i,j}\to b_{i,j},~{i,j}\to b_{i,j}\times i,~{i,j}\to b_{i,j}\times j,~{i,j}\to b_{i,j}\times i\times j$。
注意容斥边界 $$$+-1$$$ 问题！
:::success[代码] cpp const int N=2055; int n,m,op,t[N][N][4]; void ins(int x,int y,int z){ for(int i=x;i<=n;i+=-x&i) for(int j=y;j<=n;j+=-j&j) t[i][j][1]+=z*x*y, t[i][j][2]+=z*x, t[i][j][3]+=z*y, t[i][j][4]+=z; } void add(int a,int b,int c,int d,int z){ ins(a,b,z), ins(a,d+1,-z), ins(c+1,b,-z), ins(c+1,d+1,z); } int query(int x,int y){ int ret=0; for(int i=x;i;i-=-i&i) for(int j=y;j;j-=-j&j) ret+=t[i][j][1], ret-=t[i][j][2]*(y+1), ret-=t[i][j][3]*(x+1), ret+=t[i][j][4]*(x+1)*(y+1); return ret; } int ask(int a,int b,int c,int d){ return query(c,d)-query(a-1,d) -query(c,b-1)+query(a-1,b-1); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; while(cin>>op){ int a,b,c,d; cin>>a>>b>>c>>d; if(op==1){ int x; cin>>x; add(a,b,c,d,x); }else cout<<ask(a,b,c,d)<<'\n'; } return 0; } :::
逆序对
注意逆序对个数是 $$$N^2$$$ 级别开 long long。
注意离散化。
:::success[代码] cpp const int N=1e5+5; int n,t[N],ans,a[N],b[N],tot; void add(int x,int c){ for(int i=x;i<=n;i+=-i&i) t[i]+=c; } int ask(int x){ int ret=0; for(int i=x;i;i-=-i&i) ret+=t[i]; return ret; } unordered_map<int,int> mp; signed main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); n=read(); for(int i=1;i<=n;++i) a[i]=b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;++i) if(i==1 or mp[b[i]]!=mp[b[i-1]]) mp[b[i]]=++tot; for(int i=1;i<=n;++i) a[i]=mp[a[i]]; for(int i=1;i<=n;++i) add(a[i],1), ans+=ask(n)-ask(a[i]); cout<<ans; return 0; } :::
基础线段树
对满足 区间可加性 问题的 单 $$$\log$$$、大常数、$$$4$$$ 倍空间 解法。
通常 $4\times 10^5\le n\le 2\times 10^6$。
线段树模板 1
区修区查。
注意，线段树 开 $$$4$$$ 倍空间，**递归前 $$$pushtag$$$**。
:::success[代码] cpp const int N=1e6+5; int n,q,a[N]; struct node{ int sum,tag; }tree[N<<3]; void init(int p,int l,int r){ if(l>r) return; tree[p].tag=0; if(l==r){ tree[p].sum=a[l]; return; } int mid=l+r>>1; init(p<<1,l,mid),init(p<<1|1,mid+1,r); tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum; } inline void pushtag(int p,int l,int mid,int r){ int c=tree[p].tag; if(!c) return; tree[p<<1].sum+=(mid-l+1)*c, tree[p<<1|1].sum+=(r-mid)*c; tree[p<<1].tag+=c, tree[p<<1|1].tag+=c; tree[p].tag=0; } void add(int p,int l,int r,int fl,int fr,int c){ if(fl<=l and r<=fr){ tree[p].sum+=c*(r-l+1); tree[p].tag+=c; return; } int mid=l+r>>1; pushtag(p,l,mid,r); if(fl<=mid) add(p<<1,l,mid,fl,fr,c); if(fr>mid) add(p<<1|1,mid+1,r,fl,fr,c); tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum; } int ask(int p,int l,int r,int fl,int fr){ if(fl<=l and r<=fr) return tree[p].sum; int mid=l+r>>1,ret=0; pushtag(p,l,mid,r); if(fl<=mid) ret+=ask(p<<1,l,mid,fl,fr); if(fr>mid) ret+=ask(p<<1|1,mid+1,r,fl,fr); return ret; } signed main(){ n=read(),q=read(); for(int i=1;i<=n;++i) a[i]=read(); init(1,1,n); for(int i=1;i<=q;++i){ int op=read(),l=read(),r=read(); if(op==1) add(1,1,n,l,r,read()); else write(ask(1,1,n,l,r)), putchar(10); } return 0; } :::
线段树模板 2
区间加乘，单点查询。
注意预处理乘法标记为 $$$1$$$。
注意在 $$$main$$$ 函数内调用 $$$pre$$$ 预处理函数。
注意及时取模。
注意复制函数的时候递归调用也要修改。
:::success[代码] cpp const int N=1e5+5,mod=10007; int n,a[N]; struct node{ int mtag,atag; }t[N<<2]; void pushtag(int p){ if(t[p].mtag!=1){ t[p<<1].atag*=t[p].mtag, t[p<<1].atag%=mod, t[p<<1|1].atag*=t[p].mtag, t[p<<1|1].atag%=mod, t[p<<1].mtag*=t[p].mtag, t[p<<1].mtag%=mod, t[p<<1|1].mtag*=t[p].mtag, t[p<<1|1].mtag%=mod; t[p].mtag=1; } if(t[p].atag!=0){ t[p<<1].atag+=t[p].atag, t[p<<1].atag%=mod, t[p<<1|1].atag+=t[p].atag, t[p<<1|1].atag%=mod; t[p].atag=0; } } void add(int p,int l,int r,int fl,int fr,int c){ if(fl<=l and r<=fr){ t[p].atag+=c, t[p].atag%=mod; return; } pushtag(p); int mid=l+r>>1; if(fl<=mid) add(p<<1,l,mid,fl,fr,c); if(fr>mid) add(p<<1|1,mid+1,r,fl,fr,c); } void mul(int p,int l,int r,int fl,int fr,int c){ if(fl<=l and r<=fr){ t[p].atag*=c, t[p].atag%=mod; t[p].mtag*=c, t[p].mtag%=mod; return; } pushtag(p); int mid=l+r>>1; if(fl<=mid) mul(p<<1,l,mid,fl,fr,c); if(fr>mid) mul(p<<1|1,mid+1,r,fl,fr,c); } void pre(int p,int l,int r){ t[p].mtag=1; if(l==r)return; int mid=l+r>>1; pre(p<<1,l,mid), pre(p<<1|1,mid+1,r); } int ask(int p,int l,int r,int x){ if(l==r) return (a[l]*t[p].mtag+t[p].atag)%mod; pushtag(p); int mid=l+r>>1; if(x<=mid) return ask(p<<1,l,mid,x); return ask(p<<1|1,mid+1,r,x); } signed main(){ //freopen(".in","r",stdin); //freopen(".out","w",stdout); n=read(); for(int i=1;i<=n;++i) a[i]=read(); pre(1,1,n); for(int i=1;i<=n;++i){ int op=read(),l=read(),r=read(),c=read(); if(op==0){ add(1,1,n,l,r,c); } else if(op==1){ mul(1,1,n,l,r,c); } else if(op==2) cout<<ask(1,1,n,r)<<'\n'; } return 0; } :::
区间最大公约数
一个很重要的
Unable to parse markup [type=CF_MATHJAX]
\gcd (a,b,c)= \gcd (a,b-a,c-b)$。所以 $\gcd (a_i)\in[l,r]= \gcd (a_l, \gcd (a_i-a_{i-1})\in[l+1,r])$。
所以我们维护差分数组的 $sum& \gcd$。
$ans_{l,r}= \gcd (ASKsum_{1,l},ASK \gcd _{l+1,r})$。
:::success[代码] ```cpp const int N=5e5+5; int n,m,a[N],b[N]; struct node{ int sum,g; }tree[N<<2]; /* A：区间修改，单点查询 对b数组 单点修改，区间求和
B：单点修改，区间GCD 对b数组 单点修改，区间求GCD */ void pushup(int p){ tree[p].g=abs(__gcd(tree[p<<1].g,tree[p<<1|1].g)); tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum; } void build(int l,int r,int p){ if(l==r){ tree[p].g=tree[p].sum=b[l]; return; } int mid=l+r>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); pushup(p); } void add(int l,int r,int p,int f,int c){ if(l==r){ tree[p].g+=c; tree[p].sum+=c; return; } int mid=l+r>>1; if(f<=mid)add(l,mid,p<<1,f,c); if(f>mid)add(mid+1,r,p<<1|1,f,c); pushup(p); } int asksum(int l,int r,int p,int fl,int fr){ if(fl<=l and r<=fr)return tree[p].sum; int mid=l+r>>1,ret=0; if(fl<=mid)ret+=asksum(l,mid,p<<1,fl,fr); if(fr>mid)ret+=asksum(mid+1,r,p<<1|1,fl,fr); return ret; } int askg(int l,int r,int p,int fl,int fr){ if(fl<=l and r<=fr)return tree[p].g; int mid=l+r>>1,ret=0; if(fl<=mid)ret=abs(__gcd(ret,askg(l,mid,p<<1,fl,fr))); if(fr>mid)ret=abs(__gcd(ret,askg(mid+1,r,p<<1|1,fl,fr))); return ret; } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1]; build(1,n,1); for(int i=1;i<=m;i++){ int l,r,c;char opt; cin>>opt>>l>>r; if(opt=='Q'){ int ans=askg(1,n,1,l+1,r); ans=__gcd(ans,asksum(1,n,1,1,l)); cout<<ans<<'\n'; } else{ cin>>c; add(1,n,1,l,c); if(r+1<=n)add(1,n,1,r+1,-c); } } return 0; } ``` :::
区间最大连续子段和
维护 $$$sum,lmx,rmx,mx$$$ 分别表示区间和、至少包含 $$$1$$$ 个元素的最大前缀、至少包含 $$$1$$$ 个元素的最大后缀、区间最大子段和。
注意复制函数时递归调用也要改！
:::success[代码] cpp const int N=5e5+5; int n,m,a[N]; struct node{ ll sum,lmx,rmx,mx; node(ll xa=0,ll xb=-1e18,ll xc=-1e18,ll xd=-1e18){ sum=xa,lmx=xb,rmx=xc,mx=xd; } node operator+(node p){ node r; r.sum=sum+p.sum, r.lmx=max(lmx,sum+p.lmx), r.rmx=max(p.rmx,p.sum+rmx), r.mx=max(max(mx,p.mx),rmx+p.lmx); return r; } }t[N<<2]; void pre(int p,int l,int r){ if(l==r){ t[p]={a[l],a[l],a[l],a[l]}; return; } int mid=l+r>>1; pre(p<<1,l,mid); pre(p<<1|1,mid+1,r); t[p]=t[p<<1]+t[p<<1|1]; } void add(int p,int l,int r,int x){ if(l==r){ t[p]={a[l],a[l],a[l],a[l]}; return; } int mid=l+r>>1; if(x<=mid)add(p<<1,l,mid,x); else add(p<<1|1,mid+1,r,x); t[p]=t[p<<1]+t[p<<1|1]; } node ask(int p,int l,int r,int fl,int fr){ if(fl<=l and r<=fr) return t[p]; int mid=l+r>>1;node ret; if(fl<=mid)ret=ask(p<<1,l,mid,fl,fr); if(fr>mid)ret=ret+ask(p<<1|1,mid+1,r,fl,fr); return ret; } signed main(){ n=read(),m=read(); for(int i=1;i<=n;++i) a[i]=read(); pre(1,1,n); for(int i=1;i<=m;++i){ int op=read(),x=read(),y=read(); if(op==1){ if(x>y) swap(x,y); write(ask(1,1,n,x,y).mx), putchar(10); } else a[x]=y, add(1,1,n,x); } return 0; } :::
线段树变式
权值线段树。
以权值为编号处理问题，**注意空间不再是 $$$4$$$ 倍了**
通常搭配动态开点使用，**注意下标不要写成 $$$p«1,p«1|1$$$**
代码略长，慢写细调。
序列维护
插入删除、前驱后继、查询排名、值域元素个数。考虑动态开点。
注意动态开点空间不再是 $$$4$$$ 倍了。
复习一下，对于 $$$[l,r]$$$ 内排名 $$$x$$$
- $$$[l,mid]$$$ 内元素个数 $$$\le x$$$，在 $$$[l,mid]$$$ 查询排名 $$$x$$$
- 否则在 $$$[mid+1,r]$$$ 查询排名 $$$x-sz[l,mid]$$$
递归处理直到 $l=r$。
$$$Trick$$$：$$$x$$$ 前驱就是排名为“$x$ 的排名 $-1$”的数，就可组合其他函数计算前驱。后继同理。
:::success[代码] cpp const int N=1e7+5; int n,tot,rt; struct node{ int lc,rc,sum; }t[N]; void add(int &p,int l,int r,int x,int c){ if(!p) p=++tot; t[p].sum+=c; if(l==r) return; int mid=l+r>>1; if(x<=mid) add(t[p].lc,l,mid,x,c); else add(t[p].rc,mid+1,r,x,c); } int ask(int p,int l,int r,int fl,int fr){ if(!p or l>r or fl>fr) return 0; if(fl<=l and r<=fr) return t[p].sum; int mid=l+r>>1,ret=0; if(fl<=mid) ret+=ask(t[p].lc,l,mid,fl,fr); if(fr>mid) ret+=ask(t[p].rc,mid+1,r,fl,fr); return ret; } int query(int p,int l,int r,int x){ if(l==r) return l; int mid=l+r>>1,lsz=t[t[p].lc].sum; if(x<=lsz) return query(t[p].lc,l,mid,x); return query(t[p].rc,mid+1,r,x-lsz); } signed main(){ n=read(); for(int i=1;i<=n;++i){ int op=read(),x=read(); if(op==1) add(rt,-2e9,2e9,x,1); else if(op==2) add(rt,-2e9,2e9,x,-1); else if(op==3) cout<<ask(rt,-2e9,2e9,-2e9,x-1)+1<<'\n'; else if(op==4) cout<<query(rt,-2e9,2e9,x)<<'\n'; else if(op==5) cout<<query(rt,-2e9,2e9,ask(rt,-2e9,2e9,-2e9,x-1))<<'\n'; else cout<<query(rt,-2e9,2e9,ask(rt,-2e9,2e9,-2e9,x)+1)<<'\n'; } return 0; } :::
长序列区修区查
注意在 $$$pushtag$$$ 时要先判断是否已给 $$$lc,rc$$$ 分配编号，不然就全加给 $$$0$$$ 编号了。
区间很长，记得开 long long 。
:::success[代码] cpp const int N=1e6+5; int n,m,rt,tot; struct node{ int lc,rc,sum,tag; }tree[N]; inline void pushtag(int p,int l,int mid,int r){ int c=tree[p].tag; if(!c) return; if(!tree[p].lc) tree[p].lc=++tot; if(!tree[p].rc) tree[p].rc=++tot; tree[tree[p].lc].sum+=c*(mid-l+1), tree[tree[p].rc].sum+=c*(r-mid); tree[tree[p].lc].tag+=c, tree[tree[p].rc].tag+=c; tree[p].tag=0; } void add(int &p,int l,int r,int fl,int fr,int c){ if(!p) p=++tot; if(fl<=l and r<=fr){ tree[p].sum+=c*(r-l+1), tree[p].tag+=c; return; } int mid=l+r>>1; pushtag(p,l,mid,r); if(fl<=mid) add(tree[p].lc,l,mid,fl,fr,c); if(fr>mid) add(tree[p].rc,mid+1,r,fl,fr,c); tree[p].sum=tree[tree[p].lc].sum+tree[tree[p].rc].sum; } int ask(int p,int l,int r,int fl,int fr){ if(!p or l>r or fl>fr) return 0; if(fl<=l and r<=fr) return tree[p].sum; int mid=l+r>>1,ret=0; pushtag(p,l,mid,r); if(fl<=mid) ret+=ask(tree[p].lc,l,mid,fl,fr); if(fr>mid) ret+=ask(tree[p].rc,mid+1,r,fl,fr); return ret; } signed main(){ n=read(),m=read(); for(int i=1;i<=m;++i){ int op=read(),x=read(),y=read(); if(op==1) add(rt,1,n,x,y,read()); else write(ask(rt,1,n,x,y)), putchar(10); } return 0; } :::
线段树分裂与合并
极不常见，基本会模板就行。
线段树合并 & 分裂
注意对 $$$-1$$$ 的判断。
分裂时应判断是否给新节点分配编号！
记得初始化！
合并时复用节点 $$$p$$$ 可以节省空间。
记得开 long long（尤其是函数返回值与函数中接触过 long long 的变量）
:::success[代码] cpp const int N=2e5+5,M=8e6; int n,m,tot,all=1; int root[N]; struct node{ int lc,rc; ll sum; }tree[M]; void add(int &p,int l,int r,int x,ll c){ if(!p)p=++tot; if(l==r){ tree[p].sum+=c; return; } int mid=l+r>>1; if(x<=mid)add(tree[p].lc,l,mid,x,c); else add(tree[p].rc,mid+1,r,x,c); tree[p].sum=tree[tree[p].lc].sum+tree[tree[p].rc].sum; } int ask(int p,int l,int r,int fl,int fr){ if(!p)return 0; if(fl<=l and r<=fr)return tree[p].sum; int mid=l+r>>1;ll ans=0; if(fl<=mid)ans+=ask(tree[p].lc,l,mid,fl,fr); if(fr>mid)ans+=ask(tree[p].rc,mid+1,r,fl,fr); return ans; } int merge(int p1,int p2){ if(!p1 or !p2) return p1+p2; int p=++tot; tree[p].lc=merge(tree[p1].lc,tree[p2].lc); tree[p].rc=merge(tree[p1].rc,tree[p2].rc); tree[p].sum=tree[p1].sum+tree[p2].sum; return p; } void split(int &p1,int &p2,int l,int r,int fl,int fr){ if(!p1 or fl>r or fr<l) return; if(fl<=l and r<=fr){ p2=p1,p1=0; return; } if(!p2) p2=++tot; int mid=l+r>>1; if(fl<=mid) split(tree[p1].lc,tree[p2].lc,l,mid,fl,fr); if(fr>mid) split(tree[p1].rc,tree[p2].rc,mid+1,r,fl,fr); tree[p1].sum=tree[tree[p1].lc].sum+tree[tree[p1].rc].sum; tree[p2].sum=tree[tree[p2].lc].sum+tree[tree[p2].rc].sum; } int kth(int p,int l,int r,int k){ if(l==r)return l; int mid=l+r>>1,lsum=tree[tree[p].lc].sum; if(lsum>=k)return kth(tree[p].lc,l,mid,k); return kth(tree[p].rc,mid+1,r,k-lsum); } signed main(){ n=read();m=read(); for(int i=1;i<=n;i++){ int x=read(); add(root[1],1,n,i,x); } for(int i=1;i<=m;i++){ int opt=read(),p=read(); if(!opt){ int x=read(),y=read(); split(root[p],root[++all],1,n,x,y); } else if(opt==1){ int t=read(); root[p]=merge(root[p],root[t]); } else if(opt==2){ int x=read(),q=read(); add(root[p],1,n,q,x); } else if(opt==3){ int x=read(),y=read(); write(ask(root[p],1,n,x,y)); putchar(10); } else{ int k=read(); if(ask(root[p],1,n,1,n)<k)puts("-1"); else write(kth(root[p],1,n,k)),putchar(10); } } return 0; } :::
可持久化数据结构
应用较多，基本是 可持久化线段树 或者 以可持久化数组为基础的其他数据结构。
可持久化线段树
基于动态开点线段树利用 前缀和 的思想 用单 $$$\log$$$ 时间复杂度 解决 只查询、有可减性 的问题。
涉及 在上一个版本增加得到本版本 和 在 $$$版本 a - 版本 b$$$ 中计算答案 这两个操作。
注意哪些编号是 $$$x$$$，哪些编号是 $$$root[x]$$$ 。
注意离散化的还原。
因为是动态开点线段树，所以注意空间开大。
:::success[代码] cpp const int N=2e6+5; int n,m,tot,a[N],b[N],root[N]; struct node{ int lc,rc,sum; }tree[N<<4]; int add(int f,int l,int r,int x){ int p=++tot; tree[p]=tree[f]; ++tree[p].sum; if(l==r) return p; int mid=l+r>>1; if(x<=mid) tree[p].lc=add(tree[f].lc,l,mid,x); else tree[p].rc=add(tree[f].rc,mid+1,r,x); return p; } int ask(int p1,int p2,int l,int r,int k){//在p1-p2中查询第k小 if(l==r) return l; int mid=l+r>>1,lsz=tree[tree[p1].lc].sum-tree[tree[p2].lc].sum; if(lsz>=k) return ask(tree[p1].lc,tree[p2].lc,l,mid,k); else return ask(tree[p1].rc,tree[p2].rc,mid+1,r,k-lsz); } int tsp,rep[N]; unordered_map<int,int> mp; signed main(){ n=read(),m=read(); for(int i=1;i<=n;++i) a[i]=b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;++i) if(i==1 or b[i]!=b[i-1]) mp[b[i]]=++tsp, rep[tsp]=b[i]; for(int i=1;i<=n;++i) a[i]=mp[a[i]]; for(int i=1;i<=n;++i) root[i]=add(root[i-1],1,n,a[i]); for(int i=1;i<=m;++i){ int l=read(),r=read(),k=read(); write(rep[ask(root[r],root[l-1],1,n,k)]), putchar(10); } return 0; } :::
可持久化并查集
动态维护并查集，考虑 对 $$$fa$$$ 数组进行可持久化维护。
注意，**我们不能使用路径压缩优化并查集，因为我们要求相邻版本变化小**。
于是考虑使用 按稚合并 优化并查集。
具体地，可以 按树高合并，额外维护 $$$h$$$ ，或者 按大小合并，额外维护 $$$sz$$$，或者 随即合并，无需额外维护。
:::success[代码] cpp const int M=2e7+5,N=1e6+5; int n,m,tot,root[N]; struct node{ int lc,rc,fa,dep; }tree[M]; int build(int l,int r){ int p=++tot; if(l==r){ tree[p].fa=l; return p; } int mid=l+r>>1; tree[p].lc=build(l,mid); tree[p].rc=build(mid+1,r); return p; } int ask(int p,int l,int r,int x){//返回编号 if(l==r)return p; int mid=l+r>>1; if(x<=mid)return ask(tree[p].lc,l,mid,x); return ask(tree[p].rc,mid+1,r,x); } int get(int t,int x){//返回父亲编号 int f=ask(root[t],1,n,x); if(tree[f].fa==x)return f; return get(t,tree[f].fa); } int add(int q,int l,int r,int x,int c){ int p=++tot; tree[p]=tree[q]; if(l==r){ tree[p].fa=c; return p; } int mid=l+r>>1; if(x<=mid)tree[p].lc=add(tree[q].lc,l,mid,x,c); else tree[p].rc=add(tree[q].rc,mid+1,r,x,c); return p; } int change(int q,int l,int r,int x){ int p=++tot; tree[p]=tree[q]; if(l==r){ tree[p].dep++; return p; } int mid=l+r>>1; if(x<=mid)tree[p].lc=change(tree[p].lc,l,mid,x); else tree[p].rc=change(tree[p].rc,mid+1,r,x); return p; } int main(){ cin>>n>>m; root[0]=build(1,n); for(int i=1;i<=m;i++){ int opt,x,y;cin>>opt>>x; if(opt==1){ cin>>y; //在i时刻合并x,y root[i]=root[i-1]; int fx=get(i-1,x),fy=get(i-1,y);//在i-1时刻查fa[x],fa[y] if(tree[fx].fa==tree[fy].fa)continue; if(tree[fx].dep>tree[fy].dep)swap(fx,fy); root[i]=add(root[i-1],1,n,tree[fx].fa,tree[fy].fa);//在i-1时刻的基础上把tree[fx].fa改成fy if(tree[fx].dep==tree[fy].dep) root[i]=change(root[i],1,n,tree[fy].fa);//把i时刻的fy深度增加 } if(opt==2)root[i]=root[x]; if(opt==3){ cin>>y; int fx=get(i-1,x),fy=get(i-1,y);//在i-1时刻查fa[x],fa[y] cout<<(tree[fx].fa==tree[fy].fa)<<'\n'; root[i]=root[i-1]; } } return 0; } :::
线段树分治
离线算法。
通过 时间轴，把 删除操作 变成 对增加操作的撤销，提高 可作性，时间复杂度 ** 双 $$$\log$$$ **。
通常使用 $$$dfs$$$ 遍历时间轴，到达叶节点后统计答案。
动态图连通性
列出时间轴，每次在时间 $$$[l,r]$$$ 加入一条边的影响。
我们记录每一次对 $$$fa$$$ 的操作存入栈中，结束后由栈顶一次撤销即可。
进阶地，把每次询问看成一个新的时间节点优化效率。
进阶地，使用 $$$lst[],tim$$$ 优化树状数组提高效率。
:::success[代码] cpp const int N=5e3+5,M=5e5+5; int n,m,lst[N][N],top,h[N],fa[N],tot,tim,query[M]; vector<pair<int,int> >v[M<<2]; struct work{int opt,x,y;}s[M]; struct node{int x,y,high;}st[M]; struct EDGE{int x,y,l,r;} e[M]; constexpr int MAXSIZE=2e6; char buf[MAXSIZE],*p1,*p2; #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++) inline int read(){ int ans=0,j=1;char c=gc(); while(c>'9' or c<'0'){if(c=='-')j=-1;c=gc();} while(c>='0' and c<='9'){ans=(ans<<1)+(ans<<3)+(c^48);c=gc();} return ans*j; }inline void write(int x){ if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar('0'+x%10); }inline void upd(int p,int l,int r,int fl,int fr,pair<int,int> idx){ if(fl>fr)return; if(fl<=l and r<=fr){v[p].push_back(idx);return;} int mid=l+r>>1; if(fl<=mid)upd(p<<1,l,mid,fl,fr,idx); if(fr>mid)upd(p<<1|1,mid+1,r,fl,fr,idx); }inline int ask(int x){ if(x==fa[x])return x; return ask(fa[x]); }void dfs(int p,int l,int r){ if(l>r)return; int now=top,mid=l+r>>1; for(int i=0;i<v[p].size();++i){ int x=v[p][i].first,y=v[p][i].second; int fx=ask(x),fy=ask(y); if(fx==fy)continue; if(h[fx]<h[fy])swap(fx,fy); st[++top]={fx,fy,h[fx]}; fa[fy]=fx,h[fx]+=(h[fx]==h[fy]); } if(l==r)puts(ask(s[query[l]].x)==ask(s[query[l]].y)?"Y":"N"); else dfs(p<<1,l,mid),dfs(p<<1|1,mid+1,r); while(top>now){ fa[st[top].y]=st[top].y; h[st[top].x]=st[top].high; top--; } }int main(){ n=read(),m=read(); for(int i=1;i<=n;++i)fa[i]=i; for(int i=1;i<=m;++i){ s[i].opt=read(),s[i].x=read(),s[i].y=read(); if(s[i].x>s[i].y)swap(s[i].x,s[i].y); }for(int i=1;i<=m;++i) if(!s[i].opt){ e[++tot]={s[i].x,s[i].y,tim+1,-1}; lst[s[i].x][s[i].y]=tot; } else if(s[i].opt==1) e[lst[s[i].x][s[i].y]].r=tim; else query[++tim]=i; for(int i=1;i<=tot;++i){ if(e[i].r==-1) e[i].r=tim; upd(1,1,tim,e[i].l,e[i].r,make_pair(e[i].x,e[i].y)); } dfs(1,1,tim); return 0; } :::
最小 mex 生成树
显然答案 $\le n$，考虑从小到大检查是否成为答案。
在 $$$t$$$ 时刻让所有边权为 $$$t$$$ 的边删除，每次检查 $$$1$$$ 号节点所在连通块大小是否为 $$$n$$$ 即可判断。
:::success[代码] cpp const int N=1e6+5; int n,m,k,fa[N],sz[N],top,out=1e6;bool vis[N]; vector<int>b[N<<1],v[N<<2],vec[N<<1]; struct edge{int x,y,val;}e[N<<1]; struct node{int x,y,sz;}s[N]; inline void upd(int p,int l,int r,int fl,int fr,int idx){ if(fl<=l and r<=fr){v[p].push_back(idx);return;} int mid=l+r>>1; if(fl<=mid)upd(p<<1,l,mid,fl,fr,idx); if(fr>mid)upd(p<<1|1,mid+1,r,fl,fr,idx); }inline int get(int x){return x==fa[x]?x:get(fa[x]);} void dfs(int p,int l,int r){ if(l>r)return; int now=top,mid=l+r>>1; for(int i=0;i<v[p].size();++i){ int fx=get(e[v[p][i]].x),fy=get(e[v[p][i]].y); if(fx==fy)continue;if(sz[fx]<sz[fy])swap(fx,fy); s[++top]={fx,fy,sz[fx]};sz[fx]+=sz[fy],fa[fy]=fx; }if(l==r){if(!vec[l].size() or sz[get(1)]==n){cout<<l;exit(0);}} else dfs(p<<1,l,mid);dfs(p<<1|1,mid+1,r); while(top>now)fa[s[top].y]=s[top].y,sz[s[top].x]=s[top].sz,top--; }int main(){ n=read(),m=read(); for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1; for(int i=1;i<=m;++i){ e[i]={read(),read()};int x=read();vec[x].push_back(i);vis[x]=1; if(e[i].x>e[i].y)swap(e[i].x,e[i].y); }for(int i=0;i<=n;i++) if(!vis[i]){out=i;break;} for(int i=0;i<=out;++i) for(int j=0;j<vec[i].size();++j)b[vec[i][j]].push_back(i); for(int i=1;i<=m;++i){int l=0,r=-1; for(int j=0;j<b[i].size();++j){ r=b[i][j]-1;if(r>out)break; if(l<=r)upd(1,0,out,l,r,i); l=r+2; }if(l<=out)upd(1,0,out,l,out,i); }dfs(1,0,out);cout<<out; return 0; } :::
二维数据结构
在维度上的改变。
以双 $$$\log$$$ 的时间复杂度解决二维动态维护问题。
二维线段树在解决问题时 常数大，空间 $$$M \log ^2$$$
二维树状数组在解决问题时 常数小，空间 $$$N^2$$$
通常来讲 二维线段树和线段树套树状数组 的使用频率更高。
二维区修区查
类似于一维树状数组，$sum1_{i,j}\to b_{i,j},~{i,j}\to b_{i,j}\times i,~{i,j}\to b_{i,j}\times j,~{i,j}\to b_{i,j}\times i\times j$。
注意容斥边界 $$$+-1$$$ 问题！
:::success[二维树状数组参考代码] cpp const int N=2055; int n,m,op,t[N][N][4]; void ins(int x,int y,int z){ for(int i=x;i<=n;i+=-x&i) for(int j=y;j<=n;j+=-j&j) t[i][j][1]+=z*x*y, t[i][j][2]+=z*x, t[i][j][3]+=z*y, t[i][j][4]+=z; } void add(int a,int b,int c,int d,int z){ ins(a,b,z), ins(a,d+1,-z), ins(c+1,b,-z), ins(c+1,d+1,z); } int query(int x,int y){ int ret=0; for(int i=x;i;i-=-i&i) for(int j=y;j;j-=-j&j) ret+=t[i][j][1], ret-=t[i][j][2]*(y+1), ret-=t[i][j][3]*(x+1), ret+=t[i][j][4]*(x+1)*(y+1); return ret; } int ask(int a,int b,int c,int d){ return query(c,d)-query(a-1,d) -query(c,b-1)+query(a-1,b-1); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; while(cin>>op){ int a,b,c,d; cin>>a>>b>>c>>d; if(op==1){ int x; cin>>x; add(a,b,c,d,x); }else cout<<ask(a,b,c,d)<<'\n'; } return 0; } :::
二维线段树空间 $\frac{(2048\times \log _2^{2048})^2\times 8}{1024^2}=3872MB>512MB$，炸空间，不可做！
陌上花开
三维偏序问题。
通过排序将其变为二维区间查询问题。
注意第一层与第二层的节点应共用同一个编号系统 $tot$，否则会导致节点编号混乱，重复使用。
注意计算空间要 $$$\times 4$$$ 或 $\times 8$，如果超过，考虑将必要位置开 long long，别漏掉。
:::success[二维线段树参考代码] cpp const int N=2e5+5; int n,k,tot,rt[N*128],f[N*128]; struct node{ int a,b,c; bool operator<(const node &p)const{ if(a!=p.a)return a<p.a; if(b!=p.b)return b<p.b; return c<p.c; } }s[N*128]; struct edge{ int lc,rc,sum; }tree[N*128]; void addX(int &p,int l,int r,int x,int y){ if(!p)p=++tot; addY(rt[p],1,k,y); if(l==r)return; int mid=l+r>>1; if(x<=mid)addX(tree[p].lc,l,mid,x,y); else addX(tree[p].rc,mid+1,r,x,y); } int askY(int s,int l,int r,int ay,int by){ if(ay<=l and r<=by)return tree[s].sum; int mid=l+r>>1,ret=0; if(ay<=mid)ret+=askY(tree[s].lc,l,mid,ay,by); if(by>mid)ret+=askY(tree[s].rc,mid+1,r,ay,by); return ret; } int askX(int p,int l,int r,int ax,int ay,int bx,int by){ if(ax<=l and r<=bx)return askY(rt[p],1,k,ay,by); int mid=l+r>>1,ret=0; if(ax<=mid)ret+=askX(tree[p].lc,l,mid,ax,ay,bx,by); if(bx>mid)ret+=askX(tree[p].rc,mid+1,r,ax,ay,bx,by); return ret; } int main(){ n=read(),k=read(); for(int i=1;i<=n;++i){ int a=read(),b=read(),c=read(); s[i]={a,b,c}; } sort(s+1,s+n+1); int root=0,lst=1; for(int i=1;i<=n;i++){ addX(root,1,k,s[i].b,s[i].c); if(s[i].a!=s[i+1].a){ for(int j=lst;j<=i;++j){ int x=askX(root,1,k,1,1,s[j].b,s[j].c)-1; if(x>=0)f[x]++; } lst=i+1; } } for(int i=0;i<n;++i)write(f[i]),putchar(10); return 0; } :::
分治离线批处理算法
CDQ 分治
$$$CDQ$$$ 分治在归并排序的合并过程前处理信息。
贡献分为 $[l,mid]\to [l,mid]$、$[mid+1,r]\to [mid+1,r]$、$[l,mid]\to [mid+1,r]$。
前两个递归处理，最后一个用数据结构处理。
具体来说，$CDQ$ 分治处理 $$$[l,r]$$$ 的“前对后贡献”时，先处理所有 $$$[l,mid]$$$ 的“前对后贡献”和所有 $$$[mid+1,r]$$$ 的所有“前对后”贡献，最后拿到 $$$[l,mid],[mid+1,r]$$$ 按 $$$b$$$ 排序，$a[l,mid]<a[mid+1,r]$，利用两边排序的性质处理 $$$[l,mid]\to [mid+1,r]$$$ 的贡献。
挂一张我曾经的评论帮助理解。
陌上花开
三维偏序，$CDQ$ 模板。
先对 $$$a$$$ 排序，然后 $$$CDQ$$$ 处理。
$$$cdq$$$ 流程如下。
:::success[伪代码] cpp cdq(l,r){ l==r: return cdq(l,mid)//分治处理[l,mid]对[l,mid]的贡献 cdq(mid+1,r)//分治处理[mid+1,r]对[mid+1,r]的贡献 calc(l,mid, mid+1,r)//用数据结构处理[l,mid]对[mid+1,r]的贡献 merge(l,mid, mid+1,r)//正常归并排序最后的合并 } :::
注意重复元素：在 $$$node$$$ 中记录重复出现次数，在排序时设置优先级
:::success[代码] cpp const int N=2e5+5; int n,k,t,f[N]; struct node{ int a,b,c; int cnt;//重复出现次数 int ans; }s[N],g[N]; bool cmp1(node a,node b){ if(a.a!=b.a)return a.a<b.a; if(a.b!=b.b)return a.b<b.b; return a.c<b.c; } bool cmp2(node a,node b){ if(a.b!=b.b)return a.b<b.b; return a.c<b.c; } int tree[N],lst[N],idx; inline void add(int x,int y){ while(x<=k){ if(lst[x]!=idx)tree[x]=0; tree[x]+=y; lst[x]=idx; x+=(x&(-x)); } } inline int ask(int x){ int ret=0; while(x){ if(lst[x]!=idx)tree[x]=0; ret+=tree[x]; x-=(x&(-x)); } return ret; } inline void cdq(int l,int r){ if(l==r)return; int mid=l+r>>1; cdq(l,mid); cdq(mid+1,r); int i=l,j=mid+1; while(j<=r){ while(i<=mid and s[i].b<=s[j].b){ add(s[i].c,s[i].cnt); ++i; } s[j].ans+=ask(s[j].c); ++j; } ++idx; i=l,j=mid+1; int tmp=l; while(i<=mid and j<=r){ if(s[i].b<s[j].b)g[tmp++]=s[i++]; else g[tmp++]=s[j++]; } while(i<=mid)g[tmp++]=s[i++]; while(j<=r)g[tmp++]=s[j++]; for(i=l;i<=r;++i)s[i]=g[i]; } int main(){ n=read();k=read(); for(int i=1;i<=n;++i)s[i]={read(),read(),read(),1}; sort(s+1,s+n+1,cmp1); for(int i=1;i<=n;++i){ if(s[i].a==s[i-1].a and s[i].b==s[i-1].b and s[i].c==s[i-1].c)++s[t].cnt; else s[++t]=s[i]; } cdq(1,t); for(int i=1;i<=t;++i)f[s[i].ans+s[i].cnt-1]+=s[i].cnt; for(int i=0;i<n;++i)write(f[i]),putchar(10); return 0; :::
整体二分
带着所有查询一起二分。
$$$dfs$$$ 函数同时记录答案区间 $$$[l,r]$$$ 与下标区间 $$$[fl,fr]$$$，$$$l=r$$$ 时记录答案。
$$$\forall i\in[1,n]$$$ 有插入次数 $\le \log _2^{n}$，得总时间复杂度为 $O(N \log ^2)$。
整体二分
静态查询区间第 $$$k$$$ 小。
可用 主席树 完成，但 内存超限（限 30MB）。
:::warning[PAC代码] cpp const int N=1e6+5,M=1.7e7+5; unordered_map<int,int>mp; int n,m,all,tot,root[N],a[N],b[N]; struct node{int lc,rc,sum;}tree[M]; int add(int f,int l,int r,int x){ int p=++tot; tree[p].lc=tree[f].lc; tree[p].rc=tree[f].rc; tree[p].sum=tree[f].sum+1; if(l==r)return p; int mid=l+r>>1; if(x<=mid)tree[p].lc=add(tree[f].lc,l,mid,x); else tree[p].rc=add(tree[f].rc,mid+1,r,x); return p; }int ask(int p1,int p2,int l,int r,int k){//在线段树p1-p2中查询第k小 if(l==r)return l; int mid=l+r>>1,lsz=tree[tree[p1].lc].sum-tree[tree[p2].lc].sum; if(lsz>=k)return ask(tree[p1].lc,tree[p2].lc,l,mid,k); else return ask(tree[p1].rc,tree[p2].rc,mid+1,r,k-lsz); }int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+n+1); for(int i=1;i<=n;i++) if(b[i]!=b[i-1] or i==1)mp[b[i]]=++all; for(int i=1;i<=n;i++){ b[mp[a[i]]]=a[i]; a[i]=mp[a[i]]; }for(int i=1;i<=n;i++)root[i]=add(root[i-1],1,all,a[i]); for(int i=1;i<=m;i++){ int l,r,k;cin>>l>>r>>k; cout<<b[ask(root[r],root[l-1],1,all,k)]<<'\n'; }return 0; } :::
考虑整体二分。
对于 $$$dfs(l,r,fl,fr)$$$，遍历 $$$[fl,fr]$$$ 维护当前已进行的修改操作，每个查询操作在当前维护的树状数组内计算。
将数据分成两部分后继续递归，直至无查询或答案区间长度为 $$$1$$$ 并记录答案。
:::success[代码] ```cpp const int N=2e5+5;
int n,m,tree[N]; inline int ask(int x){ int ret=0; while(x){ ret+=tree[x]; x-=(-x)&x; } return ret; } inline void add(int x,int c){ while(x<=n){ tree[x]+=c; x+=(-x)&x; } }
int ans[N]; struct node{ int l,r,k,id,type; }q[N<<1],q1[N<<1],q2[N<<1]; inline void dfs(int l,int r,int fl,int fr){//答案区间[l,r]下标区间[fl,fr] if(fl>fr)return; if(l==r){ for(int i=fl;i<=fr;++i) if(q[i].type==2)ans[q[i].id]=l; return; } int mid=l+r>>1,cnt1=0,cnt2=0; for(int i=fl;i<=fr;++i){ if(q[i].type==1){ if(q[i].l<=mid){ q1[++cnt1]=q[i]; add(q[i].id,1); } else q2[++cnt2]=q[i]; }else{ int x=ask(q[i].r)-ask(q[i].l-1); if(x>=q[i].k)q1[++cnt1]=q[i]; else{ q[i].k-=x; q2[++cnt2]=q[i]; } } } for(int i=fl;i<=fr;++i) if(q[i].type==1 and q[i].l<=mid)add(q[i].id,-1); for(int i=1;i<=cnt1;++i)q[i+fl-1]=q1[i]; for(int i=1;i<=cnt2;++i)q[cnt1+i+fl-1]=q2[i]; dfs(l,mid,fl,cnt1+fl-1); dfs(mid+1,r,cnt1+fl,fr); } int all,tot,toraw[N],tmp[N]; struct pub{ int x,id; bool operator<(const pub &p){ return x<p.x; } }work[N]; bool cmp1(pub a,pub b){return a.id<b.id;} int main(){ n=read();m=read(); for(int i=1;i<=n;++i)work[i]={read(),i}; sort(work+1,work+n+1); for(int i=1;i<=n;++i){ if(i==1 or work[i].x!=work[i-1].x)++all; tmp[work[i].id]=all; toraw[all]=work[i].x; } for(int i=1;i<=n;++i) q[++tot]={tmp[i],EOF,EOF,i,1}; for(int i=1;i<=m;++i){ int l=read(),r=read(),k=read(); q[++tot]={l,r,k,i,2}; } dfs(0,all+1,1,tot); for(int i=1;i<=m;++i)write(toraw[ans[i]]),putchar(10); return 0; } ``` :::
平衡树
重点学习 $$$\text{pbds}$$$ 库以提高代码编写效率。
考时可用！
库与命名空间
头文件 #include<bits/extc++.h>//extend扩展
命名空间 using namespace __gnu_pbds;
注意在 DevC++ 无法过编。
声明
tree<数据类型,映射方式,排序方式,树类型,更新方式>名称;
常见声明方式 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>t;
数据类型 int,long long,pair<int,int>,node
映射方式 null_type 表示无映射 ($$$\text{set}$$$)，填入其他类型则表示存在映射 ($$$\text{map}$$$)
排序方式 $$$less$$$ 从小到大 $$$greater$$$ 从大到小
树类型 rb_tree,splay_tree,tree_tag,rb_tree_tag 等，通常使用 rb_tree 因为速度快
更新方式 除非自己写否则用 tree_order_statistics_node_update 。
成员
插入元素 t.insert(x);//插入x
删除元素 t.erase(x);//删除x
查询排名 t.order_of_key(x);//返回x的排名
查询第 $$$k$$$ 小 t.find_by_order(x);//返回第x小的值的迭代器
lower_bound t.lower_bound(x);//第一个>=x的迭代器
upper_bound t.upper_bound(x);//第一个>x的迭代器
树的合并 t.join(s);//将s树合并到当前树t，s将被清空，相当于merge
树的分裂 t.split(x,s);//只保留值<=x的元素，其余分裂到s中
注意
需要将上述内容背下来，因为小熊猫 C++ 对成员没有补全。
红黑树会自动去重，所以通常使用 long long 类型配合左移、右移实现。
尽量不要 define int long long 或在声明后 define。
普通平衡树
同 序列维护 使用 值域线段树 可完成。
使用 $$$\text{pbds}$$$ 解决：
:::success[代码] cpp #include<bits/stdc++.h> #include<bits/extc++.h> using namespace std; using namespace __gnu_pbds; typedef long long ll; int n; tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> tre; int main(){ cin>>n; for(int i=1;i<=n;i++){ ll op,k;cin>>op>>k; if(op==1) tre.insert((k<<20)+i); else if(op==2) tre.erase(tre.lower_bound(k<<20)); else if(op==3) printf("%lld\n",tre.order_of_key(k<<20)+1); else if(op==4) printf("%lld\n",(*tre.find_by_order(k-1))>>20); else if(op==5) printf("%lld\n",(*--tre.lower_bound(k<<20))>>20); else printf("%lld\n",(*tre.upper_bound((k<<20)+n))>>20); } return 0; } :::
