正题

题目链接:https://www.luogu.com.cn/problem/P5494

题目大意

给出一个可重集合要求支持

• 将集合\(p\)中在\([l,r]\)的数放到一个新的集合中
• 将集合\(t\)的所有数放入集合\(p\)中
• 在集合\(p\)中放入\(x\)个\(p\)
• 查询集合\(p\)中在\([l,r]\)区间的数
• 查询集合\(p\)中第\(k\)小的数

\(1\leq n,m\leq 2\times 10^5\)

解题思路

考虑怎么分裂，就照着一个位置\(pos\)做下去顺路一直开新节点，往左走时把右节点给新的节点就好了。

然后分裂两次再把左右合并就好了。

时间复杂度\(O(n\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+10,M=N<<5;
ll n,m,tot,rt[N];
ll cnt,w[M],ls[M],rs[M];
void Change(ll &x,ll L,ll R,ll pos,ll val){
if(!x)x=++cnt;
if(L==R){w[x]+=val;return;}
ll mid=(L+R)>>1;
if(pos<=mid)Change(ls[x],L,mid,pos,val);
else Change(rs[x],mid+1,R,pos,val);
w[x]=w[ls[x]]+w[rs[x]];return;
}
ll Ask(ll x,ll L,ll R,ll l,ll r){
if(!x)return 0;
if(L==l&&R==r){return w[x];}
ll mid=(L+R)>>1;
if(r<=mid)return Ask(ls[x],L,mid,l,r);
if(l>mid)return Ask(rs[x],mid+1,R,l,r);
return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);
}
ll Bsk(ll x,ll L,ll R,ll k){
if(L==R)return L;
ll mid=(L+R)>>1;
if(w[ls[x]]>=k)return Bsk(ls[x],L,mid,k);
return Bsk(rs[x],mid+1,R,k-w[ls[x]]);
}
ll Merge(ll x,ll y){
if(!x||!y)return x+y;
ls[x]=Merge(ls[x],ls[y]);
rs[x]=Merge(rs[x],rs[y]);
w[x]=w[x]+w[y];
return x;
}
ll Split(ll x,ll L,ll R,ll pos){
if(!x)return 0;
ll y=++cnt,mid=(L+R)>>1;
if(L==R)return y;
if(pos<=mid)swap(rs[x],rs[y]);
if(L==R)return y;
if(pos<=mid)ls[y]=Split(ls[x],L,mid,pos);
else rs[y]=Split(rs[x],mid+1,R,pos);
w[x]=w[ls[x]]+w[rs[x]];w[y]=w[ls[y]]+w[rs[y]];
return y;
}
signed main()
{
scanf("%lld%lld",&n,&m);tot=1;
for(ll i=1;i<=n;i++){
ll x;scanf("%lld",&x);
if(x)Change(rt[1],0,n,i,x);
}
while(m--){
ll op;scanf("%lld",&op);
if(op==0){
ll p,x,y;scanf("%lld%lld%lld",&p,&x,&y);
++tot;rt[tot]=rt[p];
rt[p]=Split(rt[p],0,n,x-1);
rt[tot]=Merge(rt[tot],Split(rt[p],0,n,y));
swap(rt[p],rt[tot]);
}
else if(op==1){
ll p,t;scanf("%lld%lld",&p,&t);
rt[p]=Merge(rt[p],rt[t]);
}
else if(op==2){
ll p,x,q;scanf("%lld%lld%lld",&p,&x,&q);
Change(rt[p],0,n,q,x);
}
else if(op==3){
ll p,x,y;scanf("%lld%lld%lld",&p,&x,&y);
printf("%lld\n",Ask(rt[p],0,n,x,y));
}
else if(op==4){
ll p,k;scanf("%lld%lld",&p,&k);
if(w[rt[p]]<k){puts("-1");continue;}
printf("%lld\n",Bsk(rt[p],0,n,k));
}
}
return 0;
}