未經(jīng)博主同意不得轉(zhuǎn)載

?

?

3729: Gty的游戲

Time Limit:?20 Sec??Memory Limit:?128 MB
Submit:?448??Solved:?150

Description

某一天gty在與他的妹子玩游戲。
妹子提出一個(gè)游戲，給定一棵有根樹，每個(gè)節(jié)點(diǎn)有一些石子，每次可以將不多于L的石子移動(dòng)到父節(jié)點(diǎn)，詢問
將某個(gè)節(jié)點(diǎn)的子樹中的石子移動(dòng)到這個(gè)節(jié)點(diǎn)先手是否有必勝策略。
gty很快計(jì)算出了策略。
但gty的妹子十分機(jī)智，她決定修改某個(gè)節(jié)點(diǎn)的石子或加入某個(gè)新節(jié)點(diǎn)。
gty不忍心打擊妹子，所以他將這個(gè)問題交給了你。
另外由于gty十分紳士，所以他將先手讓給了妹子。

Input

第一行兩個(gè)數(shù)字，n和L,n<=5*10^4,L<=10^9
第二行n個(gè)數(shù)字，表示每個(gè)節(jié)點(diǎn)初始石子數(shù)。
接下來n-1行，每行兩個(gè)整數(shù)u和v，表示有一條從u到v的邊。
接下來一行一個(gè)數(shù)m，表示m組操作。
接下來m行，每行第一個(gè)數(shù)字表示操作類型
若為1，后跟一個(gè)數(shù)字v，表示詢問在v的子樹中做游戲先手是否必勝。
若為2，后跟兩個(gè)數(shù)字x，y表示將節(jié)點(diǎn)x的石子數(shù)修改為y。
若為3，后跟三個(gè)數(shù)字u,v,x，表示為u節(jié)點(diǎn)添加一個(gè)兒子v，初始石子數(shù)為x。
在任意時(shí)刻，節(jié)點(diǎn)數(shù)不超過5*10^4。

Output

對于每個(gè)詢問，若先手必勝，輸出"MeiZ",否則輸出"GTY"。
另，數(shù)據(jù)進(jìn)行了強(qiáng)制在線處理，對于m組操作，除了類型名以外，都需要異或之前回答為"MeiZ"的個(gè)數(shù)。

Sample Input

2 1000
0 0
1 2
1
1 1

Sample Output

GTY

HINT

Source

By wangxz

?

【分析】

　　膜奧爺爺啦~~

　　好吧，就是首先，階梯尼姆，很明顯吧。就是把距離根節(jié)點(diǎn)為奇數(shù)層的異或起來就好了。

　　那就是差不多維護(hù)子樹的異或和，但是樹是動(dòng)態(tài)的?！?span style="text-decoration:line-through;">表示動(dòng)態(tài)樹我真的很垃圾，splay忘光，LCT不會(huì)，前面做的題都是離線的【如果離線就很快就會(huì)做了

? ? ?所以接下來要學(xué)學(xué)動(dòng)態(tài)樹了。。

　　用splay維護(hù)dfs序，和之前差不多嘛，一棵樹的子樹的dfs序記錄了st和ed之后，查詢區(qū)間[st,ed]就行了。

　　splay就是能求出鍵值在某范圍里面的東西【具體維護(hù)什么，和啊，最大值啊，都是你決定的】，但實(shí)際splay樹上維護(hù)的是splay樹子樹上的東西。

　　這時(shí)，你只要把st splay到跟，ed splay到根的右兒子，那么ed的做兒子表示的區(qū)間就是[st+1,ed-1]你直接問它的子樹就好了。

　　實(shí)際上，并不需要實(shí)際的dfs序，只要你按順序插入的，那splay樹就是有序的，你記錄每個(gè)點(diǎn)的st和ed，到時(shí)找前驅(qū)后繼就好了。

　　可以選擇看圖：

　　

　　左圖是原樹，右圖是splay樹。紅色是值。splay樹的中序遍歷就是dfs序，splay樹上紅色的兩個(gè)維護(hù)的是子樹內(nèi)dep為奇和偶的點(diǎn)的異或和。

　　有意義的點(diǎn)我打在左端點(diǎn)，右端點(diǎn)的值均為0。

　　splay的時(shí)候upd一下把左右兒子的值跟自己異或一下就能維護(hù)那個(gè)異或和了。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<map> 7 using namespace std; 8 #define Maxn 400010 9 10 int n,Mod; 11 12 int w[Maxn]; 13 int nl[Maxn],nr[Maxn]; 14 map<int,int> z; 15 16 struct node 17 { 18 int x,y,next; 19 }t[Maxn*2]; 20 int len,first[Maxn]; 21 void ins(int x,int y) 22 { 23 t[++len].x=x;t[len].y=y; 24 t[len].next=first[x];first[x]=len; 25 } 26 27 struct sp 28 { 29 int son[2],fa,d,a1,a2; 30 bool dep; 31 }tr[Maxn*2];int tot; 32 33 void upd(int x) 34 { 35 int lc=tr[x].son[0],rc=tr[x].son[1]; 36 tr[x].a1=tr[lc].a1^tr[rc].a1; 37 tr[x].a2=tr[lc].a2^tr[rc].a2; 38 if(!tr[x].dep) tr[x].a2^=tr[x].d; 39 else tr[x].a1^=tr[x].d; 40 } 41 void rot(int x) 42 { 43 int fa=tr[x].fa,yy=tr[fa].fa; 44 int w=tr[fa].son[0]==x?1:0; 45 tr[fa].son[1-w]=tr[x].son[w]; 46 if(tr[x].son[w]) tr[tr[x].son[w]].fa=fa; 47 if(yy) 48 { 49 if(tr[yy].son[0]==fa) tr[yy].son[0]=x; 50 else tr[yy].son[1]=x; 51 }tr[x].fa=yy; 52 tr[x].son[w]=fa;tr[fa].fa=x; 53 upd(fa);upd(x); 54 } 55 void splay(int x,int nf) 56 { 57 while(tr[x].fa!=nf) 58 { 59 int fa=tr[x].fa,yy=tr[fa].fa; 60 if(yy==nf) rot(x); 61 else 62 { 63 if((tr[yy].son[0]==fa)==(tr[fa].son[0]==x)) {rot(fa);rot(x);} 64 else {rot(x);rot(x);} 65 } 66 } 67 } 68 int Lower(int x) 69 { 70 splay(x,0); 71 x=tr[x].son[1]; 72 while(tr[x].son[0]) x=tr[x].son[0]; 73 return x; 74 } 75 void insert(int fa,int x) 76 { 77 int r=Lower(fa); 78 splay(fa,0);splay(r,fa); 79 tr[r].son[0]=x; 80 tr[x].fa=r; 81 upd(r);upd(fa); 82 } 83 void dfs(int x,int fa) 84 { 85 tr[x].dep=!tr[fa].dep; 86 if(fa) 87 { 88 tr[nl[x]].son[1]=nr[x];tr[nr[x]].fa=nl[x]; 89 tr[nl[x]].d=w[x];upd(nr[x]);upd(nl[x]); 90 insert(fa,x); 91 } 92 for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa) 93 { 94 int y=t[i].y; 95 dfs(y,x); 96 } 97 } 98 99 int main() 100 { 101 scanf("%d%d",&n,&Mod);Mod++; 102 for(int i=1;i<=n;i++) {scanf("%d",&w[i]);z[i]=i;w[i]%=Mod;} 103 for(int i=1;i<n;i++) 104 { 105 int x,y; 106 scanf("%d%d",&x,&y); 107 ins(x,y);ins(y,x); 108 } 109 for(int i=1;i<=n;i++) nl[i]=i,nr[i]=i+n;tot=n*2; 110 tr[0].dep=0;tr[1].son[1]=n+1; 111 tr[1].d=w[1];tr[n+1].fa=1;upd(n+1);upd(1); 112 dfs(1,0); 113 int q,nw=0; 114 scanf("%d",&q); 115 while(q--) 116 { 117 int opt,ans; 118 int x,y,k; 119 scanf("%d",&opt); 120 if(opt==1) 121 { 122 scanf("%d",&x); 123 x^=nw; 124 x=z[x]; 125 splay(nl[x],0);splay(nr[x],nl[x]); 126 if(!tr[x].dep) ans=tr[tr[nr[x]].son[0]].a1; 127 else ans=tr[tr[nr[x]].son[0]].a2; 128 if(ans==0) printf("GTY\n"); 129 else {printf("MeiZ\n");nw++;} 130 } 131 else if(opt==2) 132 { 133 scanf("%d%d",&x,&y); 134 x^=nw;y^=nw; 135 y%=Mod; 136 x=z[x]; 137 splay(nl[x],0); 138 if(!tr[nl[x]].dep) tr[nl[x]].a2^=y^tr[nl[x]].d; 139 else tr[nl[x]].a1^=y^tr[nl[x]].d; 140 tr[nl[x]].d=y; 141 } 142 else 143 { 144 scanf("%d%d%d",&x,&y,&k); 145 x^=nw;y^=nw;k^=nw; 146 k%=Mod;x=z[x];z[y]=y=++n; 147 nl[y]=++tot;nr[y]=++tot; 148 tr[nl[y]].dep=!tr[nl[x]].dep; 149 tr[nl[y]].d=k;tr[nr[y]].d=0; 150 tr[nr[y]].fa=nl[y]; 151 tr[nl[y]].fa=nl[x];upd(nl[y]);upd(nr[y]); 152 insert(nl[x],nl[y]); 153 } 154 } 155 return 0; 156 } View Code

?

【AC了還是很興奮的。。。以后要多做點(diǎn)dfs序，splay之類的。。

?

2017-03-30?16:39:42

轉(zhuǎn)載于:https://www.cnblogs.com/Konjakmoyu/p/6646312.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ 3729】3729: Gty的游戏 （Splay维护dfs序+博弈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。