LGP5494 [LG TPLT] 线段树分裂 学习笔记

LGP5494 [LG TPLT] 线段树分裂 学习笔记

\(\texttt{Luogu Link}\)

前言

\(\texttt{Q:}\) 有什么数据结构是支持用合并&分裂查询答案信息的呢？
\(\texttt{A:}\) \(\text{FHQ-Treap}\)。
\(\texttt{Q:}\) 还有吗？
\(\texttt{A:}\) 线段树。

—— \(\texttt{cyffff}\)

所以，来都来了，练了线段树合并，就也写一下线段树分裂吧。

因为实际上，一个能合并能分裂的 \(\text{SegTrees}\) 在功能上与一棵 \(\text{FHQ-Treap}\) 确实就相差的不太多了（来源请求）。

题意简述

给出一个可重集，编号为 \(1\)，请支持以下五种操作：

• 0 p x y：将 \(p\) 号可重集中所有 \([x,y]\) 范围的值移到一个新可重集（其编号等于之前生成过的可重集数量加一）中。
• 1 p t：将 \(t\) 号可重集中的所有数放入 \(p\) 号可重集中，删除 \(t\)。
• 2 p x k：往 \(p\) 号可重集中加入 \(x\) 个数字 \(k\)。
• 3 p x y：查询 \(p\) 号可重集中值域在 \([x,y]\) 范围的数的个数。
• 4 p k：查询 \(p\) 号可重集中第 \(k\) 小的数，若不存在则输出 -1。

\(n,x,y,k,q,m\le 2\times 10^5\)。保证数据合法。

做法解析

如果没有 \(0\) 操作就是线段树合并（或平衡树）板子。所以这里只讲解 \(0\) 操作。

其实也很简单。我们把一只线段树按值域分成两半是很容易的，那把 \([x,y]\) 给 split 出去也不难，就是劈两刀再把两边的拼回去。

哦为了空间不爆炸，记得回收用完的结点。

直接看代码吧。

代码实现

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=2e5+5;
int N,M,X,Opt,Y,Z;
int srt[MaxN],tcnt;
struct SegTrees{lolo sum[MaxN<<5];int ls[MaxN<<5],rs[MaxN<<5],tot;int pol[MaxN<<5],pcnt;void init(int n){for(int i=1;i<=n;i++)srt[i]=++tot;}int newnode(){return pcnt?pol[pcnt--]:++tot;}void delnode(int u){pol[++pcnt]=u,ls[u]=rs[u]=sum[u]=0;}void pushup(int u){sum[u]=sum[ls[u]]+sum[rs[u]];}void modify(int &u,int cl,int cr,int dd,int x){if(!u)u=newnode();if(cl==cr){sum[u]+=x;return;}int cmid=(cl+cr)>>1;if(dd<=cmid)modify(ls[u],cl,cmid,dd,x);else modify(rs[u],cmid+1,cr,dd,x);pushup(u);}lolo getsum(int u,int cl,int cr,int dl,int dr){if(dl<=cl&&cr<=dr)return sum[u];int cmid=(cl+cr)>>1;lolo res=0;if(dl<=cmid)res+=getsum(ls[u],cl,cmid,dl,dr);if(dr>cmid)res+=getsum(rs[u],cmid+1,cr,dl,dr);return res;}int qkth(int u,int cl,int cr,lolo k){if(cl==cr)return cl;int cmid=(cl+cr)>>1;if(sum[ls[u]]>=k)return qkth(ls[u],cl,cmid,k);else return qkth(rs[u],cmid+1,cr,k-sum[ls[u]]);}int merge(int u,int v){if(!u||!v)return u|v;sum[u]+=sum[v];ls[u]=merge(ls[u],ls[v]);rs[u]=merge(rs[u],rs[v]);delnode(v);return u;}void split(int u,int &v,lolo ck){if(!u)return;v=newnode();lolo lk=sum[ls[u]];if(ck>lk)split(rs[u],rs[v],ck-lk);else swap(rs[u],rs[v]);if(ck<lk)split(ls[u],ls[v],ck);sum[v]=sum[u]-ck,sum[u]=ck;}
}SgS;
int main(){readis(N,M);SgS.init(N),tcnt=1;for(int i=1;i<=N;i++)readi(X),SgS.modify(srt[1],1,N,i,X);for(int i=1;i<=M;i++){readi(Opt);if(Opt==0){readis(X,Y,Z);int tmp=0;lolo s1=Y>1?SgS.getsum(srt[X],1,N,1,Y-1):0;lolo s2=SgS.getsum(srt[X],1,N,Y,Z);SgS.split(srt[X],srt[++tcnt],s1);SgS.split(srt[tcnt],tmp,s2);srt[X]=SgS.merge(srt[X],tmp);}if(Opt==1)readis(X,Y),srt[X]=SgS.merge(srt[X],srt[Y]);if(Opt==2)readis(X,Y,Z),SgS.modify(srt[X],1,N,Z,Y);if(Opt==3)readis(X,Y,Z),writil(SgS.getsum(srt[X],1,N,Y,Z));if(Opt==4)readis(X,Y),writil(SgS.sum[srt[X]]>=Y?SgS.qkth(srt[X],1,N,Y):-1);}return 0;
}