题目链接HDU3487
【题意】给出一个长度为n的序列,初始化为{1,2,3…n}
有两种操作:
CUT a b c :把[a,b]剪切出来,[1,a-1]+[b+1,n]合并起来形成新序列,把剪切出来的[a,b]放在新序列的第c个后面;
FLIP a b :倒转[a,b]
最后输出最终序列;
【分析】标准的splay,加上lazy标记就好了。
【AC CODE】499ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <map> //#include <unordered_map> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 3*100000+10; /* 从下往上伸展的splay */ struct NODE{ NODE *ch[2], *fa; int sz,v;//sz-当前子树有多少个结点,v-结点值 bool f;//lazy标记 int chd(){//当前结点是左儿子还是右儿子,返回0-左儿子,1-右儿子 return this == fa->ch[1]; } void push_up(){ sz = ch[0]->sz+ch[1]->sz+1; } void push_down(){ if(f){ f = false; swap(ch[0],ch[1]); ch[0]->f ^= 1; ch[1]->f ^= 1; } } }; NODE *null = new NODE; inline void setch(NODE *fa, NODE *u, int p)//重置关联的儿子和父亲,p=0表示u是fa的左儿子1是右儿子 { fa->ch[p] = u, u->fa = fa; } void rot(NODE *u)//旋转 { NODE*y = u->fa; int d = u->chd();//决定是左旋还是右旋d=0左儿子对应右旋,d=1右儿子对应左旋 setch(y->fa,u,y->chd());//把y的父亲(就是u父亲的父亲)的y儿子变为u =====把u放到当前根 setch(y,u->ch[d^1],d);//把u的对应儿子放到u所在位置(此时变成两颗树了 y成另外一颗树的根) setch(u,y,d^1);//把y放到u的对应儿子 y->push_up(), u->push_up();//先更新y再更新u(y在u下面了) } /* =================== splay1->start ===========================================*/ void dfs_down(NODE *x)//先把根到x所用到的所有的标记下放 { if(x == null)return; dfs_down(x->fa); x->push_down();//保证从上往下push_down } void splay(NODE* &rt,NODE *x, NODE *p)//把rt树的x节点伸展到p下方(即p的儿子),从下往上伸展 { dfs_down(x); if(x == p) return; while(x->fa != p) { NODE *y = x->fa; if(x->fa->fa != p && x->chd() == y->chd()) rot(y); rot(x); } if(p == null) rt = x; } /* =================== splay1->end ===========================================*/ /* =================== splay2->start ===========================================*/ NODE* find_kth(NODE *u, int k)//寻找第k小的结点(数列从左往右第k个),u为splay的根 { u->push_down(); int d = k - u->ch[0]->sz; if(1 == d) return u;//找到 if(d <= 0) return find_kth(u->ch[0],k);//往左 return find_kth(u->ch[1],k-u->ch[0]->sz-1);//往右 } void splay(NODE* &rt,int k, NODE *p)//把rt树第k大结点(数列从左往右第k个)伸展到p下面 { NODE *x = find_kth(rt,k); if(x == p) return; while(x->fa != p) { NODE *y = x->fa; if(x->fa->fa != p && x->chd() != y->chd()) rot(y); rot(x); } if(p == null) rt = x; } /* =================== splay2->end ===========================================*/ void del(NODE* &rt,NODE *x)//删除rt树的结点x { NODE *u = x->ch[0], *v = x->ch[1]; if(null == u) setch(null,v,1);//如果没有左儿子就把右儿子设为根 else if(null == v) setch(null,u,1);//没有左儿子就把左儿子设为根,左右都没的话就变成空树了 else { //左右儿子都存在时分别找出x左边和x右边的结点 u->push_down(), v->push_down(); while(u->ch[1] != null){u = u->ch[1], u->push_down();} while(v->ch[0] != null){v = v->ch[0], v->push_down();} //把x左边的u伸展到根,把x右边的v伸展到u下面 splay(rt,u,null), splay(rt,v,u); v->ch[0] = null; } } /*合并left和right,假定left所有元素都比right小;right可以是NULL,但left不可以*/ NODE* merge(NODE *left, NODE *right) { splay(left,left->sz,null);//把left中序顺序最后一个结点 伸展到根,这样left就没有右子树了 setch(left,right,1);//把right接到left的右子树 left->push_up();//更新根节点需要维护的值 return left; } /*分裂rt,把rt前k小结点放在left,其他放在right; 1<= k <=rt->sum当k==rt->sum时right=NULL,rt不能空*/ void split(NODE* &rt, int k, NODE* &left, NODE* &right) { splay(rt,k,null);//把rt的第k小的结点伸展到u的根 right = rt->ch[1];//rt的右儿子就是right right->fa = null;//right的fa需要变为null left = rt;//rt的左儿子以及rt就是left,右儿子改为null rt->ch[1] = null; left->push_up();//只需要更新左儿子,右儿子不需要更新 } /*修改[x,y]的值,lazy标记,rt != NULL,把x-1伸展到根,y+1伸展到根的右儿子,那么根的右儿子的左儿子就是区间[x,y],这里左右各增加了一个虚拟节点方便处理*/ void update(NODE* &rt, int x, int y) { splay(rt,x-1,null); splay(rt,y+1,rt); rt->ch[1]->ch[0]->f ^= 1; } struct SplayTree{ NODE node[MAXN]; NODE *rt; void bulid(NODE* &u, int x, int y, NODE *fa) { if(x > y) { u = null; return; } int m = (x+y)>>1; u = &node[m]; u->f = 0; u->fa = fa; u->v = m; bulid(u->ch[0],x,m-1,u); bulid(u->ch[1],m+1,y,u); u->push_up(); } void init(int sz) { null->sz = 0; null->fa = NULL; bulid(rt,0,sz+1,null);//这里左右各加了一个虚拟结点 } }s; void debug(NODE *u) { if(u == null) return; u->push_down(); debug(u->ch[0]); printf("%d\n", u->v); debug(u->ch[1]); } vector<int> ans; void pt(NODE *u) { if(u == null) return; u->push_down(); pt(u->ch[0]); ans.push_back(u->v); pt(u->ch[1]); } int main() { #ifdef SHY freopen("e:\\1.txt", "r", stdin); #endif int n,m; while(~scanf("%d %d%*c", &n, &m) && ~n) { char op[10]; int a,b; s.init(n); rep(i,0,m) { scanf("%s %d %d%*c", op, &a, &b); if('C' == op[0]) { int c; scanf("%d%*c", &c); NODE *left,*mid,*right,*u; //剪切出[a,b] split(s.rt,a,left,u); split(u,b-a+1,mid,right); //合并出新序列 u = merge(left,right); //把[a,b]插入第c个后面 split(u,c+1,left,right); s.rt = merge(merge(left,mid),right); } else update(s.rt,a+1,b+1); } ans.clear(); pt(s.rt); printf("%d", ans[1]); repe(i,2,n) printf(" %d", ans[i]); putchar('\n'); } return 0; }