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.↵
↵
# 群论↵
↵
将信息进行分类。↵
↵
**半群信息**↵
↵
满足结合律的信息。↵
↵
即满足 $(a\oplus b)\oplus c=a\oplus(b\oplus c)$，其中 $\oplus$ 为信息运算。↵
↵
比如 $\max$ 运算就是半群，因为 $\max(\max(a,b),c)=\max(a,\max(b,c))$，$\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$ 的值。↵
↵
而不是群的运算做不到，比如 $\max$，我告诉你 $\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;//记录从属块编号↵
}↵
```↵
:::↵
↵
## [区间开方求和](http://bbcoj.cn/problem/BL103)↵
↵
区间开方，区间求和，$n\le 5\times 10^4,a_i\le 2\times 10^9$ 。↵
↵
**思路：**↵
↵
$\texttt{Trick}$：数据范围内所有数开根 $\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;↵
}↵
```↵
:::↵
↵
## [区间加乘](http://bbcoj.cn/problem/BL104)↵
↵
区间加法，区间乘法， $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;↵
}↵
```↵
:::↵
↵
## [区间众数](http://bbcoj.cn/problem/BL108)↵
↵
无修改，查询区间值最小的众数。↵
↵
**思路：**↵
↵
求众数随机算法：在区间内随机选择 $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~~j,2026-03-21\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;↵
}↵
```↵
:::↵
↵
## [区修单查](http://bbcoj.cn/problem/BL22G2)↵
↵
考虑维护差分数组，区修单查 $\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;↵
}↵
```↵
:::↵
↵
## [区修区查](http://bbcoj.cn/problem/BL2GOA)↵
↵
显然区查 $\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,~sum2_i,2026-03-21\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;↵
}↵
```↵
:::↵
↵
## [二维区修区查](http://bbcoj.cn/problem/BL2ZKR)↵
↵
类似于一维，$sum1_{i,j}\to b_{i,j},~~sum2_,2026-03-21{i,j}\to b_{i,j}\times i,~~sum3_,2026-03-21{i,j}\to b_{i,j}\times j,~~sum4_,2026-03-21{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;↵
}↵
```↵
:::↵
↵
## [逆序对](http://bbcoj.cn/problem/BA202)↵
↵
**注意逆序对个数是 $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](http://bbcoj.cn/problem/BL3LOR)↵
↵
区修区查。↵
↵
注意，线段树 **开 $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](http://bbcoj.cn/problem/BL3183)↵
↵
区间加乘，单点查询。↵
↵
**注意预处理乘法标记为 $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;↵
}↵
```↵
:::↵
↵
## [区间最大公约数](http://bbcoj.cn/problem/BL3C04)↵
↵
**一个很重要的 $\text{Trick}$：$\gcd (a,b,c)= \gcd (a,b-a,c-b)$。**↵
↵
所以 $\gcd (a_i)~i,2026-03-21\in[l,r]= \gcd (a_l, \gcd (a_i-a_{i-1})~i,2026-03-21\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;↵
} ↵
```↵
:::↵
↵
## [区间最大连续子段和](http://bbcoj.cn/problem/BL3223)↵
↵
维护 $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$**↵
↵
代码略长，慢写细调。↵
↵
## [序列维护](http://bbcoj.cn/problem/BL4ZBF)↵
↵
插入删除、前驱后继、查询排名、值域元素个数。考虑动态开点。↵
↵
**注意动态开点空间不再是 $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;↵
}↵
```↵
:::↵
↵
## [长序列区修区查](http://bbcoj.cn/problem/BL412F)↵
↵
**注意在 $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;↵
}↵
```↵
:::↵
↵
# 线段树分裂与合并↵
↵
**极不常见**，基本会模板就行。↵
↵
## [线段树合并 & 分裂](http://bbcoj.cn/problem/BL5AF9)↵
↵
注意对 $-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;↵
}↵
```↵
:::↵
↵
# 可持久化数据结构↵
↵
应用较多，基本是 **可持久化线段树** 或者 **以可持久化数组为基础的其他数据结构**。↵
↵
## [可持久化线段树](http://bbcoj.cn/problem/BL6SIQ)↵
↵
基于动态开点线段树利用 **前缀和** 的思想 **用单 $\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;↵
}↵
```↵
:::↵
↵
## [可持久化并查集](http://bbcoj.cn/problem/BL6RMO)↵
↵
动态维护并查集，考虑 **对 $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$ 遍历时间轴，到达叶节点后统计答案。↵
↵
## [动态图连通性](http://bbcoj.cn/problem/BL701)↵
↵
列出时间轴，每次在时间 $[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 生成树](http://bbcoj.cn/problem/BL7IYC)↵
↵
显然答案 $\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$**↵
↵
通常来讲 **二维线段树和线段树套树状数组** 的使用频率更高。↵
↵
## [二维区修区查](http://bbcoj.cn/problem/BL2ZKR)↵
↵
类似于一维树状数组，$sum1_{i,j}\to b_{i,j},~~sum2_,2026-03-21{i,j}\to b_{i,j}\times i,~~sum3_,2026-03-21{i,j}\to b_{i,j}\times j,~~sum4_,2026-03-21{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$，炸空间，不可做！↵
↵
## [陌上花开](http://bbcoj.cn/problem/BL8NM8)↵
↵
三维偏序问题。↵
↵
**通过排序将其变为二维区间查询问题**。↵
↵
**注意第一层与第二层的节点应共用同一个编号系统 $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]$ 的贡献。↵
↵
挂一张我曾经的评论帮助理解。↵
↵
↵
↵
## [陌上花开](http://bbcoj.cn/problem/BL9NM8)↵
↵
三维偏序，$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)$。↵
↵
## [整体二分](http://bbcoj.cn/problem/BL9K9R)↵
↵
静态查询区间第 $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`**。↵
↵
## [普通平衡树](http://bbcoj.cn/training/133/problem/BLAS0G)↵
↵
同 [序列维护](http://bbcoj.cn/problem/BL4ZBF) 使用 **值域线段树** 可完成。↵
↵
[值域线段树参考代码](http://bbcoj.cn/submission-detail/205287)↵
↵
使用 $\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;↵
}↵
```↵
:::
↵
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.↵
↵
# 群论↵
↵
将信息进行分类。↵
↵
**半群信息**↵
↵
满足结合律的信息。↵
↵
即满足 $(a\oplus b)\oplus c=a\oplus(b\oplus c)$，其中 $\oplus$ 为信息运算。↵
↵
比如 $\max$ 运算就是半群，因为 $\max(\max(a,b),c)=\max(a,\max(b,c))$，$\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$ 的值。↵
↵
而不是群的运算做不到，比如 $\max$，我告诉你 $\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;//记录从属块编号↵
}↵
```↵
:::↵
↵
## [区间开方求和](http://bbcoj.cn/problem/BL103)↵
↵
区间开方，区间求和，$n\le 5\times 10^4,a_i\le 2\times 10^9$ 。↵
↵
**思路：**↵
↵
$\texttt{Trick}$：数据范围内所有数开根 $\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;↵
}↵
```↵
:::↵
↵
## [区间加乘](http://bbcoj.cn/problem/BL104)↵
↵
区间加法，区间乘法， $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;↵
}↵
```↵
:::↵
↵
## [区间众数](http://bbcoj.cn/problem/BL108)↵
↵
无修改，查询区间值最小的众数。↵
↵
**思路：**↵
↵
求众数随机算法：在区间内随机选择 $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~~j,2026-03-21\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;↵
}↵
```↵
:::↵
↵
## [区修单查](http://bbcoj.cn/problem/BL22G2)↵
↵
考虑维护差分数组，区修单查 $\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;↵
}↵
```↵
:::↵
↵
## [区修区查](http://bbcoj.cn/problem/BL2GOA)↵
↵
显然区查 $\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,~sum2_i,2026-03-21\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;↵
}↵
```↵
:::↵
↵
## [二维区修区查](http://bbcoj.cn/problem/BL2ZKR)↵
↵
类似于一维，$sum1_{i,j}\to b_{i,j},~~sum2_,2026-03-21{i,j}\to b_{i,j}\times i,~~sum3_,2026-03-21{i,j}\to b_{i,j}\times j,~~sum4_,2026-03-21{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;↵
}↵
```↵
:::↵
↵
## [逆序对](http://bbcoj.cn/problem/BA202)↵
↵
**注意逆序对个数是 $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](http://bbcoj.cn/problem/BL3LOR)↵
↵
区修区查。↵
↵
注意，线段树 **开 $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](http://bbcoj.cn/problem/BL3183)↵
↵
区间加乘，单点查询。↵
↵
**注意预处理乘法标记为 $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;↵
}↵
```↵
:::↵
↵
## [区间最大公约数](http://bbcoj.cn/problem/BL3C04)↵
↵
**一个很重要的 $\text{Trick}$：$\gcd (a,b,c)= \gcd (a,b-a,c-b)$。**↵
↵
所以 $\gcd (a_i)~i,2026-03-21\in[l,r]= \gcd (a_l, \gcd (a_i-a_{i-1})~i,2026-03-21\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;↵
} ↵
```↵
:::↵
↵
## [区间最大连续子段和](http://bbcoj.cn/problem/BL3223)↵
↵
维护 $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$**↵
↵
代码略长，慢写细调。↵
↵
## [序列维护](http://bbcoj.cn/problem/BL4ZBF)↵
↵
插入删除、前驱后继、查询排名、值域元素个数。考虑动态开点。↵
↵
**注意动态开点空间不再是 $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;↵
}↵
```↵
:::↵
↵
## [长序列区修区查](http://bbcoj.cn/problem/BL412F)↵
↵
**注意在 $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;↵
}↵
```↵
:::↵
↵
# 线段树分裂与合并↵
↵
**极不常见**，基本会模板就行。↵
↵
## [线段树合并 & 分裂](http://bbcoj.cn/problem/BL5AF9)↵
↵
注意对 $-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;↵
}↵
```↵
:::↵
↵
# 可持久化数据结构↵
↵
应用较多，基本是 **可持久化线段树** 或者 **以可持久化数组为基础的其他数据结构**。↵
↵
## [可持久化线段树](http://bbcoj.cn/problem/BL6SIQ)↵
↵
基于动态开点线段树利用 **前缀和** 的思想 **用单 $\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;↵
}↵
```↵
:::↵
↵
## [可持久化并查集](http://bbcoj.cn/problem/BL6RMO)↵
↵
动态维护并查集，考虑 **对 $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$ 遍历时间轴，到达叶节点后统计答案。↵
↵
## [动态图连通性](http://bbcoj.cn/problem/BL701)↵
↵
列出时间轴，每次在时间 $[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 生成树](http://bbcoj.cn/problem/BL7IYC)↵
↵
显然答案 $\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$**↵
↵
通常来讲 **二维线段树和线段树套树状数组** 的使用频率更高。↵
↵
## [二维区修区查](http://bbcoj.cn/problem/BL2ZKR)↵
↵
类似于一维树状数组，$sum1_{i,j}\to b_{i,j},~~sum2_,2026-03-21{i,j}\to b_{i,j}\times i,~~sum3_,2026-03-21{i,j}\to b_{i,j}\times j,~~sum4_,2026-03-21{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$，炸空间，不可做！↵
↵
## [陌上花开](http://bbcoj.cn/problem/BL8NM8)↵
↵
三维偏序问题。↵
↵
**通过排序将其变为二维区间查询问题**。↵
↵
**注意第一层与第二层的节点应共用同一个编号系统 $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]$ 的贡献。↵
↵
挂一张我曾经的评论帮助理解。↵
↵
↵
↵
## [陌上花开](http://bbcoj.cn/problem/BL9NM8)↵
↵
三维偏序，$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)$。↵
↵
## [整体二分](http://bbcoj.cn/problem/BL9K9R)↵
↵
静态查询区间第 $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`**。↵
↵
## [普通平衡树](http://bbcoj.cn/training/133/problem/BLAS0G)↵
↵
同 [序列维护](http://bbcoj.cn/problem/BL4ZBF) 使用 **值域线段树** 可完成。↵
↵
[值域线段树参考代码](http://bbcoj.cn/submission-detail/205287)↵
↵
使用 $\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;↵
}↵
```↵
:::
