首页 > 代码库 > 线段树合并与分裂
线段树合并与分裂
http://blog.csdn.net/zawedx/article/details/51818475
由于上面这篇文章讲的很清楚了，不打算再讲一遍......骗访问量也要按基本法
利用这种动态开点的值域线段树可以解决一堆有序集合进行合并/分裂/查询k小的问题，最好用的就是在排序问题中。
例1 bzoj4552
m次排序，每次对一个区间升序或降序排序，最后询问一个位置的值。
有一种比较咸鱼的做法是二分答案然后转化为01序列来做，这里就不说了= =
我们可以把排序好的一坨当做一个有序集合，用一个set维护一下这些集合的起止端点，然后排序的时候只要把这些集合全部并在一起就行了。
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <time.h>#include <stdlib.h>#include <string>#include <bitset>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <sstream>#include <stack>#include <iomanip>using namespace std;#define pb push_back#define mp make_pairtypedef pair<int,int> pii;typedef long long ll;typedef double ld;typedef vector<int> vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}#define SZ 666666#define SG 9999999//merge-split seg beginint ss[SG],sn=0,ch[SG][2],s[SG];#define er(x) ss[++sn]=xinline int alc_(){ int x=ss[sn--]; ch[x][0]=ch[x][1]=s[x]=0; return x;}#define alc alc_()//make a seg with only node pvoid build(int& x,int l,int r,int p){ x=alc; s[x]=1; //cout<<"build"<<x<<","<<l<<","<<r<<‘,‘<<p<<"\n"; if(l==r) return; int m=(l+r)>>1; if(p<=m) build(ch[x][0],l,m,p); else build(ch[x][1],m+1,r,p);}//merge t1&t2int merge(int t1,int t2){ if(t1&&t2);else return t1^t2; ch[t1][0]=merge(ch[t1][0],ch[t2][0]); ch[t1][1]=merge(ch[t1][1],ch[t2][1]); s[t1]+=s[t2]; er(t2); return t1;}//split t1 to t1&t2 so that s[t1]=kvoid split(int t1,int&t2,int k){ t2=alc; int ls=s[ch[t1][0]]; if(k>ls) split(ch[t1][1],ch[t2][1],k-ls); else swap(ch[t1][1],ch[t2][1]); if(k<ls) split(ch[t1][0],ch[t2][0],k); s[t2]=s[t1]-k; s[t1]=k;}int ask(int x,int l,int r,int k){ if(l==r) return l; int ls=s[ch[x][0]]; int m=(l+r)>>1; if(k>ls) return ask(ch[x][1],m+1,r,k-ls); return ask(ch[x][0],l,m,k);}void ps(int x,int l,int r,int dep=0){ if(!x) return; for(int i=1;i<=dep;i++) putchar(‘ ‘); cout<<x<<" "<<s[x]<<" "<<l<<","<<r<<" lc"<<ch[x][0]<<"rc"<<ch[x][1]<<"\n"; ps(ch[x][0],l,(l+r)>>1,dep+1); ps(ch[x][1],(l+r)/2+1,r,dep+1);}//seg endbool typ[SZ]; //0< 1>int rots[SZ],rs[SZ]; //i pos store l=iset<int> sol;int n,q,a[SZ];//split x so that rs[x]=svoid sp(int x,int s){ //cout<<"split"<<x<<","<<s<<"\n"; if(s>=rs[x]||s<x) return; if(!typ[x]) split(rots[x],rots[s+1],s-x+1); else { rots[s+1]=rots[x]; split(rots[s+1],rots[x],rs[x]-s); } rs[s+1]=rs[x]; rs[x]=s; sol.insert(s+1); typ[s+1]=typ[x];}//it‘s your task to edit typ[a]!void mg(int a,int b){ //cout<<"mg"<<a<<","<<b<<"\n"; if(a==b) return; sol.erase(b); rots[a]=merge(rots[a],rots[b]); rs[a]=rs[b]; //cout<<a<<","<<rs[a]<<"\n";}int qpos(int x,int k){ k-=x-1; if(!typ[x]) return ask(rots[x],1,n,k); else return ask(rots[x],1,n,rs[x]-x+2-k);}void dbg(){ cout<<sol.size()<<"\n"; for(set<int>::iterator g=sol.begin();g!=sol.end();g++) { cout<<*g<<" "<<rs[*g]<<" "<<typ[*g]<<"\n"; ps(rots[*g],1,n); }}#define ch ____chchar ch,B[1<<15],*S=B,*T=B;#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)#define isd(c) (c>=‘0‘&&c<=‘9‘)int aa,bb;int F(){ while(ch=getc(),!isd(ch)&&ch!=‘-‘);ch==‘-‘?aa=bb=0:(aa=ch-‘0‘,bb=1); while(ch=getc(),isd(ch))aa=aa*10+ch-‘0‘;return bb?aa:-aa;}#define gi F() int main(){ for(int i=SG-1;i>=1;i--) ss[++sn]=i; //scanf("%d%d",&n,&q); n=gi, q=gi; for(int i=1;i<=n;i++) { a[i]=gi; //scanf("%d",a+i); build(rots[i],1,n,a[i]); sol.insert(i); rs[i]=i; } static int tmp[SZ],tn=0; while(q--) { int o=gi,l=gi,r=gi; //scanf("%d%d%d",&o,&l,&r); { set<int>::iterator w=sol.upper_bound(l); sp(*(--w),l-1); w=sol.upper_bound(r); sp(*(--w),r); } set<int>::iterator p1=sol.lower_bound(l), p2=sol.upper_bound(r); --p2; int tg=*p1; if(p1!=p2) { for(set<int>::iterator i=++p1;;++i) { tmp[++tn]=*i; if(i==p2) break; } for(int i=1;i<=tn;i++) mg(tg,tmp[i]); tn=0; } typ[tg]=o; } int r=gi; set<int>::iterator w=sol.upper_bound(r); int x=*(--w); printf("%d\n",qpos(x,r));}
例2 yzoj2753
问题可以被当做是把序列中的一段进行升序/降序排序或者交换两个元素。
同样可以咸鱼一点二分答案之后做，不过这也不是重点...
做法和上一题差不多。
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <time.h>#include <stdlib.h>#include <string>#include <bitset>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <sstream>#include <stack>#include <iomanip>using namespace std;#define pb push_back#define mp make_pairtypedef pair<int,int> pii;typedef long long ll;typedef double ld;typedef vector<int> vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}#define SZ 666666#define SG 7777777//merge-split seg beginint ss[SG],sn=0,ch[SG][2],s[SG];#define er(x) ss[++sn]=xinline int alc_(){ int x=ss[sn--]; ch[x][0]=ch[x][1]=0;//s[x]=0; return x;}#define alc alc_()//make a seg with only node pvoid build(int& x,int l,int r,int p){ x=alc; s[x]=1; if(l==r) return; int m=(l+r)>>1; if(p<=m) build(ch[x][0],l,m,p); else build(ch[x][1],m+1,r,p);}//merge t1&t2int merge(int t1,int t2){ if(t1&&t2);else return t1^t2; ch[t1][0]=merge(ch[t1][0],ch[t2][0]); ch[t1][1]=merge(ch[t1][1],ch[t2][1]); s[t1]+=s[t2]; er(t2); return t1;}//split t1 to t1&t2 so that s[t1]=kvoid split(int t1,int&t2,int k){ t2=alc; if(ch[t1][0]||ch[t1][1]) { int ls=s[ch[t1][0]]; if(k>ls) split(ch[t1][1],ch[t2][1],k-ls); else swap(ch[t1][1],ch[t2][1]); if(k<ls) split(ch[t1][0],ch[t2][0],k); } s[t2]=s[t1]-k; s[t1]=k;}int ask(int x,int l,int r,int k){ if(l==r) return l; int ls=s[ch[x][0]]; int m=(l+r)>>1; if(k>ls) return ask(ch[x][1],m+1,r,k-ls); return ask(ch[x][0],l,m,k);}//seg endtypedef set<int> Set;int R=1e9;Set sol;bool typ[SZ]; //0< 1>int rots[SZ],rs[SZ]; //i pos store l=iint n,q,a[SZ];//split x so that rs[x]=svoid sp(int x,int s){ if(s>=rs[x]||s<x) return; if(!typ[x]) split(rots[x],rots[s+1],s-x+1); else { rots[s+1]=rots[x]; split(rots[s+1],rots[x],rs[x]-s); } rs[s+1]=rs[x]; rs[x]=s; sol.insert(s+1); typ[s+1]=typ[x];}//it‘s your task to edit typ[a]!void mg(int a,int b){ if(a==b) return; sol.erase(b); rots[a]=merge(rots[a],rots[b]); rs[a]=rs[b];}int qpos(int x,int k){ k-=x-1; if(!typ[x]) return ask(rots[x],0,R,k); else return ask(rots[x],0,R,rs[x]-x+2-k);}#define fpos my_fposint fpos(int x){ Set::iterator w=sol.upper_bound(x); return *(--w);}#define ch reader_chchar ch,B[1<<15],*S=B,*T=B;#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)#define isd(c) (c>=‘0‘&&c<=‘9‘)int aa,bb;int F(){ while(ch=getc(),!isd(ch)&&ch!=‘-‘);ch==‘-‘?aa=bb=0:(aa=ch-‘0‘,bb=1); while(ch=getc(),isd(ch))aa=aa*10+ch-‘0‘;return bb?aa:-aa;}#define gi F()void sort(int l,int r,int o){ if(l==r) return; static int tmp[SZ],tn=0; sp(fpos(l),l-1); sp(fpos(r),r); Set::iterator p1=sol.lower_bound(l), p2=sol.upper_bound(r); --p2; int tg=*p1; if(p1!=p2) { for(Set::iterator i=++p1;;++i) { tmp[++tn]=*i; if(i==p2) break; } for(int i=1;i<=tn;i++) mg(tg,tmp[i]); tn=0; } typ[tg]=o;}void qwq(){ sol.clear(); sn=R=0; for(int i=SG-1;i>=1;i--) ss[++sn]=i; n=gi, q=gi; for(int i=1;i<=n+n;i++) R=max(R,a[i]=gi); for(int i=1;i<=n+n;i++) { build(rots[i],0,R,a[i]); sol.insert(i); rs[i]=i; } while(q--) { int o=gi,a=gi,b=gi,c=gi,d=gi; if(o==1) { int p=a*n+b,q=a*n+c; sort(p,q,d); } else { int p=a*n+b,q=c*n+d; sp(fpos(p),p-1); sp(fpos(p),p); sp(fpos(q),q-1); sp(fpos(q),q); swap(rots[p],rots[q]); } } int x_=gi,y_=gi,x=x_*n+y_; printf("%d\n",qpos(fpos(x),x));}int main(){ int T=gi; while(T--) qwq();}
于是好好的安利文就成了贴板子= =如果有比较有趣的题再更新吧
另外不是很懂splay和treap要怎么搞这个东西啊
线段树合并与分裂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。