首页 > 代码库 > hdu 1890
hdu 1890
区间翻转 一脸Splay。
第一次做区间翻转。一开始懒惰标记表示当前这可子树都需要翻转。这样就有个问题：旋转的状态的不一定是正确的（rotate传的参数不一定正确）。
然后参考ac代码。联系线段树的lazy标记，每次跟新某个区间的时候，该线段区间肯定要先跟新，再在改区间节点打上标记，表示后面的子区间节点需要跟新。所以，翻转标记表示他两个儿子子树需要翻转，但是两个儿子的状态已经是正确的。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define keyTree (ch[ch[root][1]][0]) 5 using namespace std; 6 7 const int maxn=102222; 8 typedef long long LL; 9 10 struct node{ 11 int x; 12 int id; 13 bool operator<(const node &a)const { 14 return x<a.x||x==a.x&&id<a.id; 15 } 16 }; 17 struct SplayTree{ 18 int sz[maxn]; 19 int ch[maxn][2]; 20 int pre[maxn]; 21 int root,top1; 22 23 inline void Rotate(int x,int f){ 24 int y=pre[x]; 25 push_down(y); 26 push_down(x); 27 ch[y][!f]=ch[x][f]; 28 pre[ch[x][f]]=y; 29 pre[x]=pre[y]; 30 if(pre[x])ch[pre[y]][ch[pre[y]][1]==y]=x; 31 ch[x][f]=y; 32 pre[y]=x; 33 push_up(y); 34 } 35 inline void Splay(int x,int goal){ 36 push_down(x); 37 while(pre[x]!=goal){ 38 if(pre[pre[x]]==goal){ 39 push_down(pre[x]); 40 push_down(x); 41 Rotate(x,ch[pre[x]][0]==x); 42 }else{ 43 int y=pre[x],z=pre[y]; 44 int f=(ch[z][0]==y); 45 push_down(z); 46 push_down(y); 47 push_down(x); 48 if(ch[y][f]==x){ 49 Rotate(x,!f),Rotate(x,f); 50 }else{ 51 Rotate(y,f),Rotate(x,f); 52 } 53 } 54 } 55 push_up(x); 56 if(goal==0) root=x; 57 } 58 inline void RotateTo(int k,int goal){ 59 int x=root; 60 push_down(x); 61 while(sz[ch[x][0]]+1!=k){ 62 if(k<=sz[ch[x][0]]){ 63 x=ch[x][0]; 64 }else{ 65 k-=(sz[ch[x][0]]+1); 66 x=ch[x][1]; 67 } 68 push_down(x); 69 } 70 Splay(x,goal); 71 } 72 73 inline void debug(int x){ 74 push_down(x); 75 if(ch[x][0])debug(ch[x][0]); 76 printf("@%d %d ",x,val[x]); 77 if(ch[x][1])debug(ch[x][1]); 78 } 79 inline void NewNode(int &x,int id){ 80 x=id; 81 ++top1; 82 ch[x][0]=ch[x][1]=pre[x]=0; 83 sz[x]=1; 84 85 flip[x]=0; 86 } 87 inline void push_down(int x){ 88 if(flip[x]){ 89 flip[ch[x][0]]=1-flip[ch[x][0]]; 90 flip[ch[x][1]]=1-flip[ch[x][1]]; 91 rever(ch[x][0]); 92 rever(ch[x][1]); 93 flip[x]=0; 94 } 95 } 96 inline void rever(int x){ 97 swap(ch[x][0],ch[x][1]); 98 } 99 inline void push_up(int x){100 sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;101 }102 103 inline void makeTree(int &x,int l,int r,int f){104 if(l>r)return ;105 int m=(l+r)>>1;106 NewNode(x,m);107 makeTree(ch[x][0],l,m-1,x);108 makeTree(ch[x][1],m+1,r,x);109 pre[x]=f;110 if(f==0)root=x;111 push_up(x);112 }113 void init(int n){114 ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;115 116 root=top1=0;117 118 for(int i=1;i<=n;i++){119 scanf("%d",&a[i].x);120 a[i].id=i;121 }122 sort(a+1,a+n+1);123 for(int i=1;i<=n;i++){124 pos[i]=a[i].id;125 //cout<<pos[i]<<" ";126 val[pos[i]]=i;127 }128 //cout<<endl;129 makeTree(keyTree,1,n,0);130 131 }132 /*void update(int l,int r,LL c){133 RotateTo(l-1,0);134 RotateTo(r+1,root);135 136 val[keyTree]+=c;137 sum[keyTree]+=c*sz[keyTree];138 add[keyTree]+=c;139 push_up(ch[root][1]);140 push_up(root);141 }*/142 int dfs(int x){143 push_down(x);144 if(ch[x][0]==0)return x;145 146 return dfs(ch[x][0]);147 }148 void query(int n){149 150 for(int i=1;i<n;i++){151 Splay(pos[i],0);152 printf("%d ",i+sz[ch[root][0]]);153 rever(ch[root][0]);154 flip[ch[root][0]]=1-flip[ch[root][0]];155 156 if(ch[root][1]==0){157 root=ch[root][0];158 pre[root]=0;159 }else{160 int last=dfs(ch[root][1]);161 Splay(last,root);162 ch[last][0]=ch[root][0];163 pre[ch[root][0]]=last;164 root=last;165 pre[root]=0;166 }167 push_up(root);168 }169 printf("%d\n",n);170 }171 int flip[maxn];172 int pos[maxn];173 int val[maxn];174 node a[maxn];175 }spt;176 int main()177 {178 int n;179 180 while(scanf("%d",&n),n){181 spt.init(n);182 spt.query(n);183 }184 return 0;185 }
hdu 1890
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。