线段树动态开点 - - - ＞ 线段树合并

逆序对

代码

P3224 [HNOI2012]永无乡 并查集+线段树合并       ​​​​

代码

P5494 【模板】线段树分裂

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<queue> #include<set> using namespace std;typedef long long LL; typedef pair<int,int> PII;const int N=3e5+10; int rt[N],ls[N<<4],rs[N<<4],idx,id; // rt 是具体某些树的根节点，还有其他的不需要记录在内，比如分裂的时候的tmp； LL val[N<<4]; // 空间管理； int rub[N<<4],cnt; void del(int &u){rub[cnt++]=u;val[u]=0;u=ls[u]=rs[u]=0;return;} void newnode(int &u){u=cnt?rub[--cnt]:++idx;} // end // 单点修改 void modify(int &u,int l,int r,int num,int time) {if(!u)newnode(u);val[u]+=time;if(l==r)return ; // 结束条件 int mid=l+r>>1;if(num<=mid)modify(ls[u],l,mid,num,time);else modify(rs[u],mid+1,r,num,time); } // 查询第 x 大的元素 查询的时候不会遍历到空节点； int quary(int u,int l,int r,LL x) {if(l==r)return l;// 结束条件 int mid=l+r>>1;LL t=val[ls[u]];return x>t? quary(rs[u],mid+1,r,x-t):quary(ls[u],l,mid,x); } // 区间和 LL quary(int u,int l,int r,int L,int R) {if(!u)return 0; // 空节点不访问 if(L<=l&&R>=r)return val[u];int mid=l+r>>1;LL sum=0;if(L<=mid) sum=quary(ls[u],l,mid,L,R);if(R>mid)sum+=quary(rs[u],mid+1,r,L,R);return sum; } // 合并 void merge(int &a,int &b) {if(!a||!b){a+=b;return ;}val[a]+=val[b];merge(ls[a],ls[b]);merge(rs[a],rs[b]);del(b); } // 分裂 a中保留前 x 个元素 其余给 b； void split(int &a,int &b,LL x) {if(!a)return ;newnode(b);LL t=val[ls[a]];if(x>t)split(rs[a],rs[b],x-t); // 那就把a的右半部分分割给 b else swap(rs[b],rs[a]); // 否则右半部分直接给 b if(x<t)split(ls[a],ls[b],x); // 需要分科左半部分 val[b]=val[a]-x; // 计算剩余元素 val[a]=x;return ; }int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1,x;i<=n;i++)scanf("%d",&x),modify(rt[1],1,n,i,x);id++;while(m--){int f,p,x,y,t,q,k;scanf("%d",&f);if(!f){scanf("%d%d%d",&p,&x,&y);LL l=quary(rt[p],1,n,1,y),r=quary(rt[p],1,n,x,y);int tmp=0;split(rt[p],tmp,l); split(rt[p],rt[++id],l-r); merge(rt[p],tmp);}else if(f==1){scanf("%d%d",&p,&t);merge(rt[p],rt[t]);}else if(f==2){scanf("%d%d%d",&p,&x,&q);modify(rt[p],1,n,q,x);}else if(f==3){scanf("%d%d%d",&p,&x,&y);printf("%lld\n",quary(rt[p],1,n,x,y));}else {scanf("%d%lld",&p,&k);printf("%d\n",val[rt[p]]>=k?quary(rt[p],1,n,k):-1);}}return 0; }

总结

以上是生活随笔为你收集整理的线段树动态开点 - - - ＞ 线段树合并的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。