正題

題目鏈接:https://www.luogu.com.cn/problem/P5494

---

題目大意

給出一個可重集合要求支持

• 將集合$p$中在$[l,r]$的數放到一個新的集合中
• 將集合$t$的所有數放入集合$p$中
• 在集合$p$中放入$x$個$p$
• 查詢集合$p$中在$[l,r]$區間的數
• 查詢集合$p$中第$k$小的數

$1\le n,m\le 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; }

總結

以上是生活随笔為你收集整理的P5494-[模板]线段树分裂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。