「BZOJ3729」Gty的游戏

2015年7月5日6,13512

Description

某一天gty在与他的妹子玩游戏。
妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问
将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。
gty很快计算出了策略。
但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。
gty不忍心打击妹子，所以他将这个问题交给了你。
另外由于gty十分绅士，所以他将先手让给了妹子。

Input

第一行两个数字，n和L,n<=5*10^4,L<=10^9
第二行n个数字，表示每个节点初始石子数。
接下来n-1行，每行两个整数u和v，表示有一条从u到v的边。
接下来一行一个数m，表示m组操作。
接下来m行，每行第一个数字表示操作类型
若为1，后跟一个数字v，表示询问在v的子树中做游戏先手是否必胜。
若为2，后跟两个数字x，y表示将节点x的石子数修改为y。
若为3，后跟三个数字u,v,x，表示为u节点添加一个儿子v，初始石子数为x。
在任意时刻，节点数不超过5*10^4。

Output

对于每个询问，若先手必胜，输出”MeiZ”,否则输出”GTY”。
另，数据进行了强制在线处理，对于m组操作，除了类型名以外，都需要异或之前回答为”MeiZ”的个数。

Sample Input

2 1000
0 0
1 2
1
1 1

Sample Output

GTY

题解

QAQ题意搞半天理解错了，1为根节点，每次选一个结点将该节点上不超过m的石子上移

每次最多取m个，只要把每个结点石子数mod(m+1)，这很显然

还要知道一个阶梯博弈，类似于poj1704

考虑偶数层的结点，如果对手把某个结点的石子上移，你也可以再把它们上移，所以偶数层结点无视就好

奇数层就看成都在第一层，那么就是把奇数层的石子个数全部xor起来

插入新结点，查询子树信息，修改结点信息

强制在线的话，这几个操作只要用splay维护一下dfs序即可

编号用个map映射一下

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
#define N 100000
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,L,mod;
int rt,ind,ynum,top;
int val[2*N],fa[2*N],c[2*N][2],typ[2*N],sg[2*N][2];
int a[N],st[N],dep[N],pos[N][2];
map<int,int>id;
vector<int>e[N];
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	sg[x][0]=sg[l][0]^sg[r][0];
	sg[x][1]=sg[l][1]^sg[r][1];
	sg[x][typ[x]]^=val[x];
}
void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l,r;
	l=(c[y][1]==x);r=l^1;
	if(y==k)k=x;
	else c[z][c[z][1]==y]=x;
	fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x,int &k)
{
	while(x!=k)
	{
		int y=fa[x],z=fa[y];
		if(y!=k)
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}
int build(int l,int r,int f)
{
	if(l>r)return 0;
	int mid=(l+r)/2;
	if(st[mid]>0)
	{
		val[mid]=a[st[mid]];
		pos[st[mid]][0]=mid;
	}
	else pos[-st[mid]][1]=mid;
	typ[mid]=dep[abs(st[mid])];fa[mid]=f;
	c[mid][0]=build(l,mid-1,mid);
	c[mid][1]=build(mid+1,r,mid);
	update(mid);
	return mid;
}
void insert(int u,int v,int num)
{
	splay(pos[u][0],rt);
	int t=c[rt][1];while(c[t][0])t=c[t][0];
	int t1=++top,t2=++top;
	pos[v][0]=t1;pos[v][1]=t2;
	fa[t1]=t;fa[t2]=t1;
	c[t][0]=t1;c[t1][1]=t2;
	val[t1]=num;typ[t1]=typ[t2]=dep[v];
	update(t2);update(t1);splay(t2,rt);
}
void query(int x)
{
	splay(pos[x][0],rt);
	splay(pos[x][1],c[rt][1]);
	if(sg[c[pos[x][1]][0]][dep[x]^1])
	{
		ynum++;
		puts("MeiZ");
	}
	else puts("GTY");
}
void dfs(int x)
{
	st[++top]=x;
	for(int i=0;i<e[x].size();i++)
	{
		dep[e[x][i]]=dep[x]^1;
		dfs(e[x][i]);
	}
	st[++top]=-x;
}
int main()
{
	n=read();L=read();mod=L+1;
	for(int i=1;i<=n;i++)
	{
		a[i]=read()%mod;
		id[i]=i;
	}
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		e[u].push_back(v);
	}
	dfs(1);rt=build(1,top,0);
	m=read();
	int opt,u,v,x;
	while(m--)
	{
		opt=read();
		if(opt==1)
		{
			v=read()^ynum;
			query(id[v]);
		}
		if(opt==2)
		{
			x=read()^ynum;v=(read()^ynum)%mod;
			x=id[x];splay(pos[x][0],rt);val[rt]=v;
			update(rt);
		}
		if(opt==3)
		{
			u=read()^ynum;v=read()^ynum;x=read()^ynum;
			u=id[u];id[v]=++n;
			dep[n]=dep[u]^1;
			insert(u,n,x%mod);
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

#define N 100000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,L,mod;

int rt,ind,ynum,top;

int val[2*N],fa[2*N],c[2*N][2],typ[2*N],sg[2*N][2];

int a[N],st[N],dep[N],pos[N][2];

map<int,int>id;

vector<int>e[N];

void update(int x)

{

int l=c[x][0],r=c[x][1];

sg[x][0]=sg[l][0]^sg[r][0];

sg[x][1]=sg[l][1]^sg[r][1];

sg[x][typ[x]]^=val[x];

}

void rotate(int x,int &k)

{

int y=fa[x],z=fa[y],l,r;

l=(c[y][1]==x);r=l^1;

if(y==k)k=x;

else c[z][c[z][1]==y]=x;

fa[c[x][r]]=y;fa[y]=x;fa[x]=z;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x,int &k)

{

while(x!=k)

{

int y=fa[x],z=fa[y];

if(y!=k)

{

if(c[y][0]==x^c[z][0]==y)rotate(x,k);

else rotate(y,k);

}

rotate(x,k);

}

int build(int l,int r,int f)

{

if(l>r)return 0;

int mid=(l+r)/2;

if(st[mid]>0)

{

val[mid]=a[st[mid]];

pos[st[mid]][0]=mid;

}

else pos[-st[mid]][1]=mid;

typ[mid]=dep[abs(st[mid])];fa[mid]=f;

c[mid][0]=build(l,mid-1,mid);

c[mid][1]=build(mid+1,r,mid);

update(mid);

return mid;

}

void insert(int u,int v,int num)

{

splay(pos[u][0],rt);

int t=c[rt][1];while(c[t][0])t=c[t][0];

int t1=++top,t2=++top;

pos[v][0]=t1;pos[v][1]=t2;

fa[t1]=t;fa[t2]=t1;

c[t][0]=t1;c[t1][1]=t2;

val[t1]=num;typ[t1]=typ[t2]=dep[v];

update(t2);update(t1);splay(t2,rt);

}

void query(int x)

{

splay(pos[x][0],rt);

splay(pos[x][1],c[rt][1]);

if(sg[c[pos[x][1]][0]][dep[x]^1])

{

ynum++;

puts("MeiZ");

}

else puts("GTY");

}

void dfs(int x)

{

st[++top]=x;

for(int i=0;i<e[x].size();i++)

{

dep[e[x][i]]=dep[x]^1;

dfs(e[x][i]);

}

st[++top]=-x;

}

int main()

{

n=read();L=read();mod=L+1;

for(int i=1;i<=n;i++)

{

a[i]=read()%mod;

id[i]=i;

}

for(int i=1;i<n;i++)

{

int u=read(),v=read();

e[u].push_back(v);

}

dfs(1);rt=build(1,top,0);

m=read();

int opt,u,v,x;

while(m--)

{

opt=read();

if(opt==1)

{

v=read()^ynum;

query(id[v]);

}

if(opt==2)

{

x=read()^ynum;v=(read()^ynum)%mod;

x=id[x];splay(pos[x][0],rt);val[rt]=v;

update(rt);

}

if(opt==3)

{

u=read()^ynum;v=read()^ynum;x=read()^ynum;

u=id[u];id[v]=++n;

dep[n]=dep[u]^1;

insert(u,n,x%mod);

}

return 0;

}

« 「CF286X」Codeforces Round #176 (Div. 1) 「BZOJ2118」墨墨的等式 »

(网站证书已炸)

看到一群国家领导人我顿时吓傻了

Okami

看到楼上我全都报警啦!!!

胡锦涛

(⊙v⊙)嗯

江泽Ming

格奥尔吉·阿杰尔松-韦利斯基的AVL，比你们不知道高明到哪里去了，我跟它谈笑风生！

习近平

%%%%可以用treap维护么

李克强

应该可以吧

江泽民

不要因为Splay常数大就把它批判一番。西方这么多数据结构，哪个平衡树我没用过？

温家宝

你嫌常数大，你就可以写非旋转式treap啊！！！

CreationAugust

现在的年轻人啊没说几句就膜起蛤来 naive！

温家宝

%CA娘

Flandre·Scarlet

现在的年轻人啊没说几句就膜起蛤来 naive！

sxb_201

现在的年轻人啊没说几句就膜起蛤来 naive！

wsfqk

捉到 Menci 一只，Orzzzz ……

hzwer.com _ Home | http://hzwer.com

「BZOJ3729」Gty的游戏

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论