「BZOJ1095」[ZJOI2007] Hide 捉迷藏

2015年4月20日24,8277

Description

捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。我们将以如下形式定义每一种操作： C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

Input

第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。

Output

对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开着，输出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

HINT

对于100%的数据， N ≤100000, M ≤500000。

题解

2014.11.28

括号序列神题。。。

大家一起膜拜岛娘吧

http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-%E6%8D%89%E8%BF%B7%E8%97%8F/

。。。

2015.4.20

其实。。。我至今没有完全掌握括号序列的做法。。。

在PoPoQQQ大爷和KuribohG的指导下我学会了奇怪的分治做法

大爷称之动态树分治。。。

http://blog.csdn.net/popoqqq/article/details/44461423

一开始写的可并堆感觉自己快炸了…

其实这种做法不难。。。就是代码长。。。

把每次分治的重心连成一棵树，树的深度是logn，每次修改一个结点只影响它到树根的一条链

这题具体实现的时候要维护三层堆

C.每个重心存所有子树到其距离

B.每个重心存各个子树最大值，即子结点堆C的最大值

A.全局一个堆，维护答案最大值，存每个堆B的最大值和次大值之和

树上距离用rmq来求比较优越2333

线段树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<algorithm>
#define inf 1000000000
#define ll long long
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;
}
char ch[10];
int n,q,cnt,tot,black;
int last[100005];
int v[300005],pos[100005],c[100005];
struct edge{int to,next;}e[200005];
struct seg{
	int l,r,l1,r1,l2,r2,dis,c1,c2;
	void ini(int x){
		dis=-inf;
		c1=c2=0;
		if(v[x]==-6)c2=1;
		if(v[x]==-9)c1=1;
		if(v[x]>0&&c[v[x]])
			l1=l2=r1=r2=0;
		else l1=l2=r1=r2=-inf;
		}
}t[1200005];
inline int max(int a,int b,int c)
{
	return max(max(a,b),c);
}
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dfs(int x,int fa)
{
	v[++tot]=-6;
	v[++tot]=x;
	pos[x]=tot;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
			dfs(e[i].to,x);
	v[++tot]=-9;
}
inline seg merge(seg s1,seg s2)
{
	seg s;
	int a=s1.c1,b=s1.c2,c=s2.c1,d=s2.c2;
	s.l=s1.l;s.r=s2.r;

	s.dis=max(s1.dis,s2.dis);
	s.dis=max(s.dis,s1.r1+s2.l2,s1.r2+s2.l1);

	if(b<c)s.c1=a-b+c,s.c2=d;
	else s.c1=a,s.c2=b-c+d;

	s.r1=max(s2.r1,s1.r1-c+d,s1.r2+c+d);
	s.r2=max(s2.r2,s1.r2+c-d);

	s.l1=max(s1.l1,s2.l1-b+a,s2.l2+b+a);
	s.l2=max(s1.l2,s2.l2+b-a);

	return s;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		t[k].l=l;t[k].r=r;
		t[k].ini(l);
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	t[k]=merge(t[k<<1],t[k<<1|1]);
}
void modify(int k,int x)
{
	int l=t[k].l,r=t[k].r;
	if(l==r){t[k].ini(l);return;}
	int mid=(l+r)>>1;
	if(x<=mid)modify(k<<1,x);
	else modify(k<<1|1,x);
	t[k]=merge(t[k<<1],t[k<<1|1]);
}
int main()
{
	black=n=read();
	for(int i=1;i<=n;i++)c[i]=1;
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dfs(1,0);
	build(1,1,tot);
	q=read();
	for(int i=1;i<=q;i++)
	{
		scanf("%s",ch);
		if(ch[0]=='C')
		{
			int x=read();
			if(c[x])black--;
			else black++;
			c[x]^=1;
			modify(1,pos[x]);
		}
		else 
		{
			if(!black)puts("-1");
			else if(black==1)puts("0");
			else printf("%d\n",t[1].dis);
		}
	}
	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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<algorithm>

#define inf 1000000000

#define ll long long

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;

}

char ch[10];

int n,q,cnt,tot,black;

int last[100005];

int v[300005],pos[100005],c[100005];

struct edge{int to,next;}e[200005];

struct seg{

int l,r,l1,r1,l2,r2,dis,c1,c2;

void ini(int x){

dis=-inf;

c1=c2=0;

if(v[x]==-6)c2=1;

if(v[x]==-9)c1=1;

if(v[x]>0&&c[v[x]])

l1=l2=r1=r2=0;

else l1=l2=r1=r2=-inf;

}

}t[1200005];

inline int max(int a,int b,int c)

{

return max(max(a,b),c);

}

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

void dfs(int x,int fa)

{

v[++tot]=-6;

v[++tot]=x;

pos[x]=tot;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

dfs(e[i].to,x);

v[++tot]=-9;

}

inline seg merge(seg s1,seg s2)

{

seg s;

int a=s1.c1,b=s1.c2,c=s2.c1,d=s2.c2;

s.l=s1.l;s.r=s2.r;

s.dis=max(s1.dis,s2.dis);

s.dis=max(s.dis,s1.r1+s2.l2,s1.r2+s2.l1);

if(b<c)s.c1=a-b+c,s.c2=d;

else s.c1=a,s.c2=b-c+d;

s.r1=max(s2.r1,s1.r1-c+d,s1.r2+c+d);

s.r2=max(s2.r2,s1.r2+c-d);

s.l1=max(s1.l1,s2.l1-b+a,s2.l2+b+a);

s.l2=max(s1.l2,s2.l2+b-a);

return s;

}

void build(int k,int l,int r)

{

if(l==r)

{

t[k].l=l;t[k].r=r;

t[k].ini(l);

return;

}

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

t[k]=merge(t[k<<1],t[k<<1|1]);

}

void modify(int k,int x)

{

int l=t[k].l,r=t[k].r;

if(l==r){t[k].ini(l);return;}

int mid=(l+r)>>1;

if(x<=mid)modify(k<<1,x);

else modify(k<<1|1,x);

t[k]=merge(t[k<<1],t[k<<1|1]);

}

int main()

{

black=n=read();

for(int i=1;i<=n;i++)c[i]=1;

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

{

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

insert(u,v);

}

dfs(1,0);

build(1,1,tot);

q=read();

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

{

scanf("%s",ch);

if(ch[0]=='C')

{

int x=read();

if(c[x])black--;

else black++;

c[x]^=1;

modify(1,pos[x]);

}

else

{

if(!black)puts("-1");

else if(black==1)puts("0");

else printf("%d\n",t[1].dis);

}

return 0;

}

分治

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
inline 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 bin[20],Log[200005];
int n,m,G,cnt,dfn,sum,tot;
int size[100005],f[100005],deep[100005],last[100005];
int mn[18][200005],pos[100005],fa[100005];
bool vis[100005],clo[100005];
struct edge{
	int to,next;
}e[200005];
void insert(int u,int v)
{
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
struct heap{
	priority_queue<int> A,B;
	void push(int x){
		A.push(x);
	}
	void erase(int x){
		B.push(x);
	}
	void pop(){
		while(B.size()&&A.top()==B.top())
			A.pop(),B.pop();
		A.pop();
	}
	int top(){
		while(B.size()&&A.top()==B.top())
			A.pop(),B.pop();
		if(!A.size())return 0;
		return A.top();
	}
	int size(){
		return A.size()-B.size();
	}
	int stop(){
		if(size()<2)return 0;
		int x=top();pop();
		int y=top();push(x);
		return y;
	}
}A,B[100005],C[100005];
void dfs(int x,int fa)
{
	mn[0][++dfn]=deep[x];
	pos[x]=dfn;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			deep[e[i].to]=deep[x]+1;
			dfs(e[i].to,x);
			mn[0][++dfn]=deep[x];
		}
}
void getrt(int x,int fa)
{
	size[x]=1;f[x]=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa&&!vis[e[i].to])
		{
			getrt(e[i].to,x);
			size[x]+=size[e[i].to];
			f[x]=max(f[x],size[e[i].to]);
		}
	f[x]=max(f[x],sum-size[x]);
	if(f[x]<f[G])G=x;
}
void divi(int x,int f)
{
	fa[x]=f;vis[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			sum=size[e[i].to];G=0;
			getrt(e[i].to,x);
			divi(G,x);
		}
}
int rmq(int x,int y)
{
	x=pos[x];y=pos[y];
	if(y<x)swap(x,y);
	int t=Log[y-x+1];
	return min(mn[t][x],mn[t][y-bin[t]+1]);
}
int dis(int x,int y)
{
	return deep[x]+deep[y]-2*rmq(x,y);
}
void turn_off(int u,int v)
{
	if(u==v)
	{
		B[u].push(0);
		if(B[u].size()==2)A.push(B[u].top());
	}
	if(!fa[u])return;
    int f=fa[u],D=dis(f,v),tmp=C[u].top();
	C[u].push(D);
	if(D>tmp)
	{
		int mx=B[f].top()+B[f].stop(),size=B[f].size();
		if(tmp)B[f].erase(tmp);
		B[f].push(D);
		int now=B[f].top()+B[f].stop();
		if(now>mx)
		{
			if(size>=2)A.erase(mx);
			if(B[f].size()>=2)A.push(now);
		}
	}
	turn_off(f,v);
}
void turn_on(int u,int v)
{
	if(u==v)
	{
		if(B[u].size()==2)A.erase(B[u].top());
		B[u].erase(0);
	}
	if(!fa[u])return;
	int f=fa[u],D=dis(f,v),tmp=C[u].top();
	C[u].erase(D);
	if(D==tmp)
	{
		int mx=B[f].top()+B[f].stop(),size=B[f].size();
		B[f].erase(D);
		if(C[u].top())B[f].push(C[u].top());
		int now=B[f].top()+B[f].stop();
		if(now<mx)
		{
			if(size>=2)A.erase(mx);
			if(B[f].size()>=2)A.push(now);
		}
	}
	turn_on(f,v);
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	Log[0]=-1;for(int i=1;i<=200000;i++)Log[i]=Log[i>>1]+1;
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dfs(1,0);
	for(int i=1;i<=Log[dfn];i++)
		for(int j=1;j<=dfn;j++)
			if(j+bin[i]-1<=dfn)
				mn[i][j]=min(mn[i-1][j],mn[i-1][j+bin[i-1]]);
	G=0;f[0]=inf;sum=n;
	getrt(1,0);divi(G,0);
	for(int i=1;i<=n;i++)C[i].push(0);
	for(int i=1;i<=n;i++)clo[i]=1;
	for(int i=1;i<=n;i++)
	{
		turn_off(i,i);
		tot++;
	}
	char ch[2];
	m=read();
	while(m--)
	{
		scanf("%s",ch+1);
		if(ch[1]=='G')
		{
			if(tot<=1)printf("%d\n",tot-1);
			else printf("%d\n",A.top());
		}
		else 
		{
			int x=read();
			if(clo[x])turn_on(x,x),tot--;
			else turn_off(x,x),tot++;
			clo[x]^=1;
		}
	}
	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

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

inline 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 bin[20],Log[200005];

int n,m,G,cnt,dfn,sum,tot;

int size[100005],f[100005],deep[100005],last[100005];

int mn[18][200005],pos[100005],fa[100005];

bool vis[100005],clo[100005];

struct edge{

int to,next;

}e[200005];

void insert(int u,int v)

{

e[++cnt]=(edge){v,last[u]};last[u]=cnt;

e[++cnt]=(edge){u,last[v]};last[v]=cnt;

}

struct heap{

priority_queue<int> A,B;

void push(int x){

A.push(x);

}

void erase(int x){

B.push(x);

}

void pop(){

while(B.size()&&A.top()==B.top())

A.pop(),B.pop();

A.pop();

}

int top(){

while(B.size()&&A.top()==B.top())

A.pop(),B.pop();

if(!A.size())return 0;

return A.top();

}

int size(){

return A.size()-B.size();

}

int stop(){

if(size()<2)return 0;

int x=top();pop();

int y=top();push(x);

return y;

}

}A,B[100005],C[100005];

void dfs(int x,int fa)

{

mn[0][++dfn]=deep[x];

pos[x]=dfn;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa)

{

deep[e[i].to]=deep[x]+1;

dfs(e[i].to,x);

mn[0][++dfn]=deep[x];

}

void getrt(int x,int fa)

{

size[x]=1;f[x]=0;

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa&&!vis[e[i].to])

{

getrt(e[i].to,x);

size[x]+=size[e[i].to];

f[x]=max(f[x],size[e[i].to]);

}

f[x]=max(f[x],sum-size[x]);

if(f[x]<f[G])G=x;

}

void divi(int x,int f)

{

fa[x]=f;vis[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

sum=size[e[i].to];G=0;

getrt(e[i].to,x);

divi(G,x);

}

int rmq(int x,int y)

{

x=pos[x];y=pos[y];

if(y<x)swap(x,y);

int t=Log[y-x+1];

return min(mn[t][x],mn[t][y-bin[t]+1]);

}

int dis(int x,int y)

{

return deep[x]+deep[y]-2*rmq(x,y);

}

void turn_off(int u,int v)

{

if(u==v)

{

B[u].push(0);

if(B[u].size()==2)A.push(B[u].top());

}

if(!fa[u])return;

int f=fa[u],D=dis(f,v),tmp=C[u].top();

C[u].push(D);

if(D>tmp)

{

int mx=B[f].top()+B[f].stop(),size=B[f].size();

if(tmp)B[f].erase(tmp);

B[f].push(D);

int now=B[f].top()+B[f].stop();

if(now>mx)

{

if(size>=2)A.erase(mx);

if(B[f].size()>=2)A.push(now);

}

turn_off(f,v);

}

void turn_on(int u,int v)

{

if(u==v)

{

if(B[u].size()==2)A.erase(B[u].top());

B[u].erase(0);

}

if(!fa[u])return;

int f=fa[u],D=dis(f,v),tmp=C[u].top();

C[u].erase(D);

if(D==tmp)

{

int mx=B[f].top()+B[f].stop(),size=B[f].size();

B[f].erase(D);

if(C[u].top())B[f].push(C[u].top());

int now=B[f].top()+B[f].stop();

if(now<mx)

{

if(size>=2)A.erase(mx);

if(B[f].size()>=2)A.push(now);

}

turn_on(f,v);

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

Log[0]=-1;for(int i=1;i<=200000;i++)Log[i]=Log[i>>1]+1;

n=read();

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

{

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

insert(u,v);

}

dfs(1,0);

for(int i=1;i<=Log[dfn];i++)

for(int j=1;j<=dfn;j++)

if(j+bin[i]-1<=dfn)

mn[i][j]=min(mn[i-1][j],mn[i-1][j+bin[i-1]]);

G=0;f[0]=inf;sum=n;

getrt(1,0);divi(G,0);

for(int i=1;i<=n;i++)C[i].push(0);

for(int i=1;i<=n;i++)clo[i]=1;

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

{

turn_off(i,i);

tot++;

}

char ch[2];

m=read();

while(m--)

{

scanf("%s",ch+1);

if(ch[1]=='G')

{

if(tot<=1)printf("%d\n",tot-1);

else printf("%d\n",A.top());

}

else

{

int x=read();

if(clo[x])turn_on(x,x),tot--;

else turn_off(x,x),tot++;

clo[x]^=1;

}

return 0;

}

« 「BZOJ3991」[SDOI2015] 寻宝游戏「BZOJ2811」[Apio2012] Guard »

傲寒

岛娘的博客关惹QAQ可以稍微解释一下括号序列的做法中线段树维护了什么信息么QAQ

小岛

没关啊。。。

De℃,.: )

前几天和陈老师的blog一起50x了。。。

傲寒

咦！！！前两天进不了，以为关了……原来是误会……

Scarlet

神得无法同台竞技

【BZOJ1095】【ZJOI2007】Hide 捉迷藏线段树维护括号序列数据结构的压缩。 – 剑客|关注科技互联网

[…] …… 首先我们有 [hzwer犇] 的代码： http://hzwer.com/5247.html 其次我们有 [ ~~岛娘 ~~ ] 的注释： […]

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

「BZOJ1095」[ZJOI2007] Hide 捉迷藏

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论