3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 3595 Solved: 2029
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
splay的序列操作
操作[l,r]，l-1splay到根，r+1splay到根的rc，r+1的lc就是我们要操作的序列了
反转操作打一个flp标记
kth和print时(用到孩子时)都要pushDown标记
用到了build函数
注意：
1.1和n+2是虚拟节点，否则[1,n]区间要特判
2.本题节点下标就是v了，一个序列嘛
关于标记
kth中pushDown了，splay操作时已经是pushDown过了的了
[2016-12-24]
注意此处标记的定义是x没有进行标记操作
也可以按照进行标记操作了来写，见下面
// // main.cpp // 文艺平衡树 // // Created by Candy on 28/11/2016. // Copyright © 2016 Candy. All rights reserved. // #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define pa t[x].fa #define lc t[x].ch[0] #define rc t[x].ch[1] const int N=1e5+5; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node{ int ch[2],fa,w,size; int flp; }t[N]; int cnt,root; inline int wh(int x){return t[pa].ch[1]==x;} inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;} inline void pushDown(int x){ if(t[x].flp){ swap(lc,rc); t[lc].flp^=1;t[rc].flp^=1; t[x].flp=0; } } int build(int l,int r){ if(l>r) return 0; int x=(l+r)>>1; lc=build(l,x-1);rc=build(x+1,r); t[lc].fa=t[rc].fa=x; t[x].w=1;t[x].flp=0; update(x); return x; } void rotate(int x){ int f=t[x].fa,g=t[f].fa,c=wh(x); if(g) t[g].ch[wh(f)]=x; t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f;t[f].fa=x; t[x].fa=g; update(f);update(x); } void splay(int x,int tar){ for(;t[x].fa!=tar;rotate(x)) if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x); if(tar==0) root=x; } int kth(int k){ int x=root,ls=0; while(x!=0){ pushDown(x); int _=ls+t[lc].size; if(_<k&&k<=_+t[x].w) return x; if(k<=_) x=lc; else ls=_+t[x].w,x=rc; } return -1; } int n,m,l,r; void print(int x){ if(x==0) return; pushDown(x); if(lc) print(lc); if(x!=1&&x!=n+2) printf("%d ",x-1); if(rc) print(rc); } int main(int argc, const char * argv[]) { n=read();m=read(); root=build(1,n+2); while(m--){ l=read();r=read(); splay(kth(l),0); int x=kth(r+2); splay(x,root); t[lc].flp^=1; } print(root); return 0; }
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define pa t[x].fa #define lc t[x].ch[0] #define rc t[x].ch[1] const int N=1e5+5; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node{ int ch[2],fa,w,size; int flp; }t[N]; int cnt,root; inline int wh(int x){return t[pa].ch[1]==x;} inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;} inline void paint(int x){ t[x].flp^=1; swap(lc,rc); } inline void pushDown(int x){ if(t[x].flp){ paint(lc); paint(rc); t[x].flp=0; } } int build(int l,int r){ if(l>r) return 0; int x=(l+r)>>1; lc=build(l,x-1);rc=build(x+1,r); t[lc].fa=t[rc].fa=x; t[x].w=1;t[x].flp=0; update(x); return x; } void rotate(int x){ int f=t[x].fa,g=t[f].fa,c=wh(x); if(g) t[g].ch[wh(f)]=x; t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f;t[f].fa=x; t[x].fa=g; update(f);update(x); } void splay(int x,int tar){ for(;t[x].fa!=tar;rotate(x)) if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x); if(tar==0) root=x; } int kth(int k){ int x=root,ls=0; while(x!=0){ pushDown(x); int _=ls+t[lc].size; if(_<k&&k<=_+t[x].w) return x; if(k<=_) x=lc; else ls=_+t[x].w,x=rc; } return -1; } int n,m,l,r; void print(int x){ if(x==0) return; pushDown(x); if(lc) print(lc); if(x!=1&&x!=n+2) printf("%d ",x-1); if(rc) print(rc); } int main(int argc, const char * argv[]) { n=read();m=read(); root=build(1,n+2); while(m--){ l=read();r=read(); splay(kth(l),0); int x=kth(r+2); splay(x,root); paint(lc); } print(root); return 0; }