深圳市住房和城乡建设局网站首页,信誉好的网站建设,北京网页设计制作,网站怎样做优惠卷此为平衡树系列第二道#xff1a;文艺平衡树您需要写一种数据结构#xff0c;来维护一个有序数列#xff0c;其中需要提供以下操作#xff1a; 翻转一个区间#xff0c;例如原有序序列是5 4 3 2 1#xff0c;翻转区间是[2,4]的话#xff0c;结果是5 2 3 4 1 输入 第一行…此为平衡树系列第二道文艺平衡树您需要写一种数据结构来维护一个有序数列其中需要提供以下操作 翻转一个区间例如原有序序列是5 4 3 2 1翻转区间是[2,4]的话结果是5 2 3 4 1 输入 第一行为n,m n表示初始序列有n个数这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1lrn 输出 输出一行n个数字表示原始序列经过m次变换后的结果 样例输入 5 3 1 3 1 3 1 4 样例输出 4 3 2 1 5 提示 n,m100000 非旋转treap相比于旋转treap支持区间操作所以对于这道题只需要每次把树拆成[1~l-1]、[l~r]、[r1~tot]三段然后把[l~r]打上标记进行翻转再把三段区间合并就行了。对于打标记的点只有在查到这个点时才翻转如果一个点被打了两次标记就相当于不翻转。 最后附上代码. 指针版 #includeset
#includemap
#includequeue
#includestack
#includecmath
#includecstdio
#includevector
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1p2(p2(p1buf)fread(buf,1,100000,stdin),p1p2)?EOF:*p1)
int rd() {int x0,f1; char cnc(); while(!isdigit(c)) {if(c-) f-1; cnc();} while(isdigit(c)) x(((x2)x)1)(c^48),cnc(); return x*f;}
ll rd2() {ll x0,f1; char cnc(); while(!isdigit(c)) {if(c-) f-1; cnc();} while(isdigit(c)) x(((x2)x)1)(c^48),cnc(); return x*f;}
int n,m;
int L,R;
struct treap
{int size;int rnd;int val;int rev;treap *ls,*rs;treap(){}treap(int k,treap *son){size1;rndrand();valk;lsrsson;rev0;}void pushup(){sizels-sizers-size1;}void pushdown(){if(rev){rev^1;ls-rev^1;rs-rev^1;swap(ls,rs);}}
}tr[100010],nil;
typedef treap* node;
node root,cnt,null;
void init()
{niltreap(0,NULL);nullnil;null-lsnull-rsnull;null-size0;rootnull;cnttr;
}
node build(int x)
{*cnttreap(x,null);return cnt;
}
node merge(node x,node y)
{if(xnull){return y; }if(ynull){return x;}x-pushdown();y-pushdown();if(x-rndy-rnd){x-rsmerge(x-rs,y);x-pushup();return x;}else{y-lsmerge(x,y-ls);y-pushup();return y;}
}
void split(node rt,node x,node y,int k)
{if(rtnull){xynull;return ;}rt-pushdown();if(rt-ls-sizek){yrt;split(rt-ls,x,y-ls,k);rt-pushup();}else{xrt;split(rt-rs,x-rs,y,k-rt-ls-size-1);rt-pushup();}
}
void print(node rt)
{rt-pushdown();if(rt-ls!null){print(rt-ls);}printf(%d,rt-val);if(--n!0){printf( );}if(rt-rs!null){print(rt-rs);}
}
node build_tree(int l,int r)
{if(lr){return build(l);}int mid(lr)1;return merge(build_tree(l,mid),build_tree(mid1,r));
}
int main()
{init();nrd();mrd();rootbuild_tree(1,n);while(m--){Lrd();Rrd();node x,y,z;split(root,y,z,R);split(y,x,y,L-1);y-rev^1;rootmerge(merge(x,y),z);}print(root);
}非指针版 #includecstdio
#includealgorithm
#includecmath
#includeiostream
#includecstring
using namespace std;
int n,m;
int r[100010];
int v[100010];
int s[100010][3];
int size[100010];
bool d[100010];
int root;
int tot;
int L,R;
int x,y,z;
int flag;
void pushup(int x)
{size[x]size[s[x][0]]size[s[x][1]]1;
}
int build(int x)
{v[tot]x;r[tot]rand();size[tot]1;return tot;
}
void pushdown(int x)
{swap(s[x][0],s[x][1]);if(s[x][0]){d[s[x][0]]^1;}if(s[x][1]){d[s[x][1]]^1;}d[x]0;
}
int merge(int x,int y)
{if(!x||!y){return xy;}if(r[x]r[y]){if(d[x]){pushdown(x);}s[x][1]merge(s[x][1],y);pushup(x);return x;}else{if(d[y]){pushdown(y);}s[y][0]merge(x,s[y][0]);pushup(y);return y;}
}
void split(int i,int k,int x,int y)
{if(!i){xy0;return ;}if(d[i]){pushdown(i);}if(size[s[i][0]]k){xi;split(s[i][1],k-size[s[i][0]]-1,s[i][1],y);}else{yi;split(s[i][0],k,x,s[i][0]);}pushup(i);
}
void print(int x)
{if(!x){return ;}if(d[x]){pushdown(x);}print(s[x][0]);if(flag0){printf(%d,v[x]);flag1;}else{printf( %d,v[x]);}print(s[x][1]);
}
int main()
{srand(12378);scanf(%d%d,n,m);for(int i1;in;i){rootmerge(root,build(i));}for(int i1;im;i){scanf(%d%d,L,R);split(root,L-1,x,y);split(y,R-L1,y,z);d[y]^1;rootmerge(merge(x,y),z);}print(root);return 0;
} 转载于:https://www.cnblogs.com/Khada-Jhin/p/9090646.html
