本文共 3130 字，大约阅读时间需要 10 分钟。
题意：
给定一数组，完成两种操作：
CUT a b c 将区间[a,b]的数删除，并接到新数列的第c个数后面
FLIP a b 将区间[a,b]的数翻转顺序
输出最终的序列
题解：
伸展树的基本操作。
#includeusing namespace std;#define keyv ch[ch[root][1]][0]#define ddd puts("111");const int maxn = 3e5+99;int n,q;int pre[maxn],ch[maxn][2],rev[maxn],sz[maxn],key[maxn],root,tot1;void update(int r){ if(r==0)return; swap(ch[r][0],ch[r][1]); rev[r]^=1;}void pushdown(int r){ if(rev[r]) { update(ch[r][0]); update(ch[r][1]); rev[r] = 0; }}void pushup(int r){ sz[r] = 1 + sz[ch[r][0]] + sz[ch[r][1]];}void newnode(int &r,int fa,int k){ r = ++tot1; pre[r] = fa; key[r] = k; rev[r] = ch[r][0] = ch[r][1] = 0; sz[r] = 1;}void build(int &x,int l,int r,int fa){ if(l>r)return; int m = (l+r)>>1; newnode(x,fa,m); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); pushup(x);}void init(){ root = tot1 =0; key[root] = ch[root][0] = ch[root][1] =sz[root] = rev[root] = pre[root] = 0; newnode(root,0,-1); newnode(ch[root][1],root,-1); build(keyv,1,n,ch[root][1]); pushup(ch[root][1]); pushup(root);}void rotate(int x,int d){ int y = pre[x]; pushdown(y); pushdown(x); ch[y][!d] = ch[x][d];///先搞y pre[ch[x][d]] = y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;///搞x pre[x] = pre[y]; ch[x][d] = y; pre[y] = x; pushup(y);}void splay(int r,int goal){ while(pre[r] != goal) { if(pre[pre[r]]==goal) rotate(r,ch[pre[r]][0]==r); else { int y = pre[r]; int d = ch[pre[y]][0]==y; if(ch[y][d]==r) { rotate(r,!d); rotate(r,d); } else { rotate(y,d); rotate(r,d); } } } pushup(r); if(goal == 0 )root = r;}int kth(int r,int k){ pushdown(r); int t = sz[ch[r][0]]; if(k==t+1) return r; else if(k <= t)return kth(ch[r][0],k); else return kth(ch[r][1],k-t-1);}/**本题操作*/void cut(int a,int b,int c){ splay(kth(root,a),0);//a-1后 splay(kth(root,b+2),root);//b+1前 int tmp = keyv; keyv = 0; pushup(ch[root][1]); pushup(root); splay(kth(root,c+1),0);//c后 splay(kth(root,c+2),root);//c+1前 keyv = tmp; pre[keyv] = ch[root][1]; pushup(ch[root][1]); pushup(root);}void reverse(int l,int r){ splay(kth(root,l),0); splay(kth(root,r+2),root); update(keyv); pushup(ch[root][1]); pushup(root);}int cnt;void print(int r){ if(r==0)return; pushdown(r); print(ch[r][0]); if(cnt 0)///注意加的边界值。 { cnt++; printf("%d%c",key[r],cnt==n?'\n':' '); } print(ch[r][1]);}int main(){ while(scanf("%d%d",&n,&q)==2) { if(n<0 && q<0)break; init(); char op[11]; int x,y,z; while(q--) { scanf("%s",op); if(op[0]=='C') { scanf("%d%d%d",&x,&y,&z); cut(x,y,z); } else if(op[0]=='F') { scanf("%d%d",&x,&y); reverse(x,y); } cnt=0; } print(root); }}
转载地址：http://ibyci.baihongyu.com/