首页 > 代码库 > HDU 4286 Data Handler
HDU 4286 Data Handler
题意:
n个数字一开始排成一串 有两个指针L和R 指向了这串数字的一个区间的端点 现在有7种操作
1、使一个指针左移
2、使一个指针右移
3、在L后插入一个数字X
4、在R前插入一个数字X
5、删除L所指元素
6、删除R所指元素
7、翻转[L,R]区间
问 m次操作后 整串数字是什么样的
思路:
splay经典维护区间的操作 区间更新(翻转操作) 删除节点 插入节点
和 http://blog.csdn.net/houserabbit/article/details/37901199 这道Sort的题目类似 有区间翻转一定要注意down的操作
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; #define keytree ch[ch[root][1]][0] #define L(x) ch[x][0] #define R(x) ch[x][1] #define N 1000100 int t,n,m,tot,root; int a[N],ch[N][2],pre[N],size[N],val[N],rev[N]; void newnode(int &u,int fa,int w) { u=++tot; L(u)=R(u)=0; pre[u]=fa; size[u]=1; val[u]=w; rev[u]=0; } void up(int u) { size[u]=size[L(u)]+size[R(u)]+1; } void down(int u) { if(rev[u]) { rev[L(u)]^=1; rev[R(u)]^=1; rev[u]=0; swap(L(u),R(u)); } } void rotate(int u,int kind) { int fa=pre[u]; down(fa); down(u); ch[fa][!kind]=ch[u][kind]; pre[ch[u][kind]]=fa; if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=u; pre[u]=pre[fa]; ch[u][kind]=fa; pre[fa]=u; up(fa); } void splay(int u,int goal) { int fa,kind; down(u); while(pre[u]!=goal) { if(pre[pre[u]]==goal) { down(pre[u]); down(u); rotate(u,L(pre[u])==u); } else { fa=pre[u]; down(pre[fa]); down(fa); down(u); kind=L(pre[fa])==fa; if(ch[fa][kind]==u) { rotate(u,!kind); rotate(u,kind); } else { rotate(fa,kind); rotate(u,kind); } } } up(u); if(goal==0) root=u; } int getkth(int u,int k) { down(u); int s=size[L(u)]+1; if(s==k) return u; if(s>k) return getkth(L(u),k); else return getkth(R(u),k-s); } void build(int &u,int l,int r,int fa) { if(l>r) return ; int mid=(l+r)>>1; newnode(u,fa,a[mid]); build(L(u),l,mid-1,u); build(R(u),mid+1,r,u); up(u); } void init() { root=tot=0; L(root)=R(root)=pre[root]=size[root]=val[root]=rev[root]=0; newnode(root,0,-1); newnode(R(root),root,-1); build(keytree,1,n,R(root)); up(R(root)); up(root); } int getpre(int u) { down(u); u=L(u); down(u); while(R(u)) { u=R(u); down(u); } return u; } void remove() { if(L(root)) { int i=getpre(root); splay(i,root); R(i)=R(root); pre[R(root)]=i; root=L(root); pre[root]=0; up(root); } else { root=R(root); pre[root]=0; } } int output=0; void inorder(int u) { down(u); if(L(u)) inorder(L(u)); if(u!=1&&u!=2) { if(output) putchar(' '); else output=1; printf("%d",val[u]); } if(R(u)) inorder(R(u)); } int main() { //freopen("test.in","r",stdin); //freopen("test.out","w",stdout); int i,left,right; char op[20]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d%d",&left,&right); init(); scanf("%d",&m); while(m--) { scanf("%s",op); if(strcmp(op,"MoveLeft")==0) { scanf("%s",op); if(op[0]=='L') left--; else right--; } else if(strcmp(op,"MoveRight")==0) { scanf("%s",op); if(op[0]=='L') left++; else right++; } else if(strcmp(op,"Insert")==0) { scanf("%s%d",op,&i); if(op[0]=='L') { splay(getkth(root,left),0); splay(getkth(root,left+1),root); } else { splay(getkth(root,right+1),0); splay(getkth(root,right+2),root); } newnode(keytree,R(root),i); right++; } else if(strcmp(op,"Delete")==0) { scanf("%s",op); if(op[0]=='L') splay(getkth(root,left+1),0); else splay(getkth(root,right+1),0); remove(); right--; } else if(strcmp(op,"Reverse")==0) { splay(getkth(root,left),0); splay(getkth(root,right+2),root); rev[keytree]^=1; } } output=0; inorder(root); puts(""); } return 0; }
HDU 4286 Data Handler
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。