线段树分裂¶
线段树分裂
通常是动态开点的权值线段树
sum 表示权值的个数
将线段树x从 k 处斩断，前 k 小的归 x ，后面的归 y
-
若x为空，则返回
-
对 y 动态开点
-
递归分裂左子树，把x的右子树给 y, x 的右子树= 0
-
递归分裂右子树，注意 k要减去s
-
更新 y,x 的权值个数
步骤和平衡树里的getk很像
void split(int x,int &y,int k){
//分裂线段树，前k大的归x，否则归y
if(!x)return ;
y=++tot;//动态开点
int s=sum[ls[x]];
if(k<=s)split(ls[x],ls[y].k)swap(rs[x],rs[y]);
else split(rs[x],ry[x].k-s);
sum[y]=sum[x]-k;
sum[x]=k;
}
题目¶
给出一个可重集 \(a\)（编号为 \(1\)），它支持以下操作：
0 p x y：将可重集 \(p\) 中大于等于 \(x\) 且小于等于 \(y\) 的值移动到一个新的可重集中（新可重集编号为从 \(2\) 开始的正整数，是上一次产生的新可重集的编号+1）。
1 p t：将可重集 \(t\) 中的数放入可重集 \(p\)，且清空可重集 \(t\)（数据保证在此后的操作中不会出现可重集 \(t\)）。
2 p x q：在 \(p\) 这个可重集中加入 \(x\) 个数字 \(q\)。
3 p x y：查询可重集 \(p\) 中大于等于 \(x\) 且小于等于 \(y\) 的值的个数。
4 p k：查询在 \(p\) 这个可重集中第 \(k\) 小的数，不存在时输出 -1。
对于 \(30\%\) 的数据，\(1\leq n \leq {10}^3\)，\(1 \le m \le {10}^3\)； 对于 \(100\%\) 的数据，\(1 \le n \le 2 \times {10}^5\)，\(1 \le x, y, q \le m \le 2 \times {10}^5\)。保证数据合法。
不开 long long 见祖宗！！
思路¶
很明显维护一个权值线段树。操作0就是分裂线段树，操作1就是合并线段树。操作4可以类比平衡树的操作。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ps second
#define pf first
#define rd read()
int read()
{
int xx=0,ff=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
return xx*ff;
}
void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=3e5+5;
const int M=5e5+5;
const int INF=1e9+5;
const int base=23;
const int MOD=19260817;
int n,m,tot,cnt,seq=1,bac[N<<5];
int s[N<<5][2],rt[N],tr[N<<5];
namespace SGT{
int newnode () {
if(cnt)return bac[cnt--];//内存回收
return ++tot;
}
void del (int p) {
bac[++cnt]=p,s[p][0]=s[p][1]=tr[p]=0;
return;
}
void modify (int &p,int l,int r,int pos,int v) {
if (!p) {p=newnode();}
tr[p]+=v;
if (l==r) {return;}
int mid=(l+r)>>1;
if (pos<=mid) {modify(s[p][0],l,mid,pos,v);}
else {modify(s[p][1],mid+1,r,pos,v);}
return;
}
int query (int p,int l,int r,int xl,int xr) {
if (xr<l||r<xl) {return 0;}
if (xl<=l&&r<=xr) {return tr[p];}
int mid=(l+r)>>1;
return query(s[p][0],l,mid,xl,xr)+query(s[p][1],mid+1,r,xl,xr);
}
int kth (int p,int l,int r,int k) {
if (l==r) {return l;}
int mid=(l+r)>>1;
if (tr[s[p][0]]>=k) {return kth(s[p][0],l,mid,k);}
else {return kth(s[p][1],mid+1,r,k-tr[s[p][0]]);}
}
int merge (int x,int y) {
if (!x||!y) {return x+y;}
tr[x]+=tr[y];
s[x][0]=merge(s[x][0],s[y][0]);
s[x][1]=merge(s[x][1],s[y][1]);
del(y);
return x;
}
void split (int x,int &y,int k) {
if (x==0) {return;}
y=newnode();
int v=tr[s[x][0]];
if (k>v) {split(s[x][1],s[y][1],k-v);}
else {swap(s[x][1],s[y][1]);}
if (k<v) {split(s[x][0],s[y][0],k);}
tr[y]=tr[x]-k;
tr[x]=k;
return;
}
}
using namespace SGT;
signed main () {
n=rd,m=rd;
for (int i=1;i<=n;i++) {
int x=rd;
modify(rt[1],1,n,i,x);
}
for (int i=1;i<=m;i++) {
int op=rd;
int x,y,z;
if (op==0) {
x=rd,y=rd,z=rd;
int k1=query(rt[x],1,n,1,z),k2=query(rt[x],1,n,y,z);
int tmp=0;
split(rt[x],rt[++seq],k1-k2);
split(rt[seq],tmp,k2);
rt[x]=merge(rt[x],tmp);
} else if (op==1) {
x=rd,y=rd;
rt[x]=merge(rt[x],rt[y]);
} else if (op==2) {
x=rd,y=rd,z=rd;
modify(rt[x],1,n,z,y);
} else if (op==3) {
x=rd,y=rd,z=rd;
printf("%lld\n",query(rt[x],1,n,y,z));
} else if (op==4) {
x=rd,y=rd;
if (tr[rt[x]]<y) {printf("-1\n");continue;}
printf("%lld\n",kth(rt[x],1,n,y));
}
}
return 0;
}
扩展练习¶
紫
黑