ZOJ 3765 Lights （zju March I）伸展树Splay
ZJU 三月月赛题，当时见这个题目没辙，没学过splay，敲了个链表TLE了，所以回来好好学了下Splay，这道题目是伸展树的第二题，对于伸展树的各项操作有了更多的理解，这题不同于上一题的用指针表示整个树，采用纯数组表示，null节点即为0节点，这样就带来一个问题，就是有时候会有事没事就指向0节点，结果把0节点也算在结果里面，弄得我要几个地方都判断下。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 310000 using namespace std; int tot,root,n,m; int ch[N][2],val[N],gcdst[N][2],size[N],sta[N],pre[N]; int num[N],state[N]; int gcd(int a,int b) //这里处理gcd注意下，因为有-1要独判一下 { if (a==-1) return b; if (b==-1) return a; if (a<b) { swap(a,b); } return b==0 ? a : gcd(b,a%b); } void newnode(int &rt,int fa,int v,int s) { rt=++tot; ch[rt][0]=ch[rt][1]=0; val[rt]=v; pre[rt]=fa; gcdst[rt][s]=v; gcdst[rt][s^1]=-1; size[rt]=1; sta[rt]=s; } void pushup(int rt) //为了求不同状态的gcd，索性把每个gcd都求出来。然后再选择正确的状态的作为该点的gcd { int ll=ch[rt][0],rr=ch[rt][1]; size[rt]=1; if (ll) size[rt]+=size[ll]; if (rr) size[rt]+=size[rr]; if (!ll) gcdst[ll][0]=gcdst[ll][1]=-1; if (!rr) gcdst[rr][0]=gcdst[rr][1]=-1; gcdst[rt][0]=gcd(gcdst[ll][0],gcdst[rr][0]); gcdst[rt][1]=gcd(gcdst[ll][1],gcdst[rr][1]); gcdst[rt][sta[rt]]=gcd(gcdst[rt][sta[rt]],val[rt]); } void rotate(int x,int c) { int y=pre[x]; ch[y][!c]=ch[x][c]; if (ch[x][c]) { pre[ch[x][c]]=y; } pre[x]=pre[y]; if (pre[y]) { if (ch[pre[y]][0]==y) ch[pre[y]][0]=x; else ch[pre[y]][1]=x; } ch[x][c]=y; pre[y]=x; pushup(y); if (x) pushup(x); if (root==y) root=x; } void splay(int x,int f) { while (pre[x]!=f) { if (pre[pre[x]]==f) { if (ch[pre[x]][0]==x) { rotate(x,1); } else rotate(x,0); } else { int y=pre[x],z=pre[y]; if (ch[z][0]==y) { if (ch[y][0]==x) { rotate(y,1); rotate(x,1); } else { rotate(x,0); rotate(x,1); } } else { if (ch[y][0]==x) { rotate(x,1); rotate(x,0); } else { rotate(y,0); rotate(x,0); } } } } pushup(x); if (f) pushup(f); } void select(int k,int f) { int x=root; //cout<<"root is "<<x<<" left child is "<<ch[x][0]<<endl; int tmp=0; k++; for (;;) { tmp=0; if (ch[x][0]) tmp=size[ch[x][0]]; // cout<<k<<" "<<tmp<<endl; //int temp; //cin>>temp; if (tmp+1==k) break; if (k<=tmp) x=ch[x][0]; else{ k-=tmp+1; x=ch[x][1]; } } //cout<<"test "<<pre[x]<<" "<<f<<endl; splay(x,f); } void add(int num,int v,int s)//插入操作，把要插入的位置先移到根，再处理即可 { select(num,0); int nt; int x=ch[root][1]; int p=root; while (x) { // cout<<x<<" tianjia "<<val[x]<<endl; p=x; x=ch[x][0]; } //`cout<<x<<" final "<<val[x]<<" "<<p<<" "<<val[p]<<endl; if (p==root) { newnode(ch[p][1],p,v,s); splay(ch[p][1],0); } else { newnode(ch[p][0],p,v,s); splay(ch[p][0],0); } } void deletes(int num) //删除某个点，这个需要考虑下，若左子树或者右子树为空，则可直接消除，否则找到左子树的最大节点移到根，然后被删除的点即在右节点上，删除即可 { select(num,0); if (ch[root][0]==0) { root=ch[root][1]; pre[root]=0; return; } if (ch[root][1]==0) { root=ch[root][0]; pre[root]=0; return; } int rc=ch[root][0]; while (ch[rc][1]) rc=ch[rc][1]; splay(rc,root); ch[rc][1]=ch[root][1]; pre[ch[root][1]]=rc; root=rc; pre[root]=0; pushup(root); } void change(int k) { select(k,0); sta[root]^=1; pushup(root); } void query(int l,int r,int s)//查询某个区间的gcd，只要把区间的前一个节点放在根节点 后一个节点放在根的右节点，则区间必定就在根的右节点的左节点上 { select(l-1,0); // cout<<"pass"<<endl; select(r+1,root); //cout<<"pass"<<endl; int rt=ch[ch[root][1]][0]; //pushup(rt); //cout<<rt<<" "<<gcdst[rt][s]<<" "<<gcdst[rt][1-s]<<endl; printf("%d ",gcdst[rt][s]); } void modify(int k,int v)//修改某个值，这无疑是最简单的操作，移到根节点后直接修改即可 { select(k,0); val[root]=v; pushup(root); } void build(int l,int r,int &rt,int fa)//建树过程 { if (l>r) return; int mid=(l+r)>>1; newnode(rt,fa,num[mid],state[mid]); build(l,mid-1,ch[rt][0],rt); build(mid+1,r,ch[rt][1],rt); pushup(rt); } void init() //初始化过程 { for (int i=1;i<=n;i++) { scanf("%d%d",&num[i],&state[i]); } root=tot=0; ch[0][0]=ch[0][1]=0; pre[0]=size[0]=0;val[0]=-1; gcdst[0][0]=gcdst[0][1]=-1; newnode(root,0,0,-1); newnode(ch[root][1],root,1000,-1); build(1,n,ch[ch[root][1]][0],ch[root][1]); pushup(ch[root][1]); pushup(root); } void test() //测试最终生成的树 { int d=size[root]; for (int i=1;i<d-1;i++) { select(i,0); cout<<i<<" val is "<<val[root]<<" state "<<sta[root]<<" gcd[0] "<<gcdst[root][0]<<" gcd[1] "<<gcdst[root][1]<<endl; } } int main() { char ques[2]; int a,b,c; while (scanf("%d%d",&n,&m)!=EOF) { init(); //cout<<" "<<size[root]<<endl; for (int i=0;i<m;i++) { getchar(); scanf("%s",ques); //puts(ques); if (ques[0]=='Q') { scanf("%d%d%d",&a,&b,&c); //cout<<"pass"<<endl; query(a,b,c); // cout<<"p2"<<endl; } if (ques[0]=='I') { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } if (ques[0]=='D') { scanf("%d",&a); deletes(a); } if (ques[0]=='R') { scanf("%d",&a); change(a); } if (ques[0]=='M') { scanf("%d%d",&a,&b); modify(a,b); } // test(); } } return 0; }