【BZOJ 1095】 [ZJOI2007]Hide 捉迷藏

1095: [ZJOI2007]Hide 捉迷藏Time Limit:40 SecMemory Limit:162 MBSubmit:1232Solved:501[Submit][Status]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

81 22 33 43 53 66 76 87GC 1GC 2GC 1G

Sample Output

4334

HINT

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

详细题解。

这道题先把两点的距离转成了括号序列的括号个数问题，，通过线段树的区间合并操作来维护。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#define inf 0x3f3f3f3f#define M 1000005using namespace std;char str[30];int n,m,tot,v[M],pos[100005],h[100005],c[100005],black,q;struct edge{int y,ne;}e[200005];struct seg{int l,r,lp,lm,rp,rm,dis,c6,c9;void in(int x){dis=-inf;c6=c9=0;if (v[x]==-6) c6=1;if (v[x]==-9) c9=1;if (v[x]>0&&c[v[x]])lp=lm=rp=rm=0;else lp=lm=rp=rm=-inf;}}a[1200005];void read(int &tmp){tmp=0;int fu=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar())if (ch=='-') fu=-1;for (;ch>='0'&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';tmp*=fu;}void Addedge(int x,int y){e[++tot].y=y;e[tot].ne=h[x];h[x]=tot;}void dfs(int x,int fa){v[++tot]=-6;v[++tot]=x;pos[x]=tot;for (int i=h[x];i;i=e[i].ne)if (e[i].y!=fa)dfs(e[i].y,x);v[++tot]=-9;}int max(int a,int b,int c){return max(a,max(b,c));}seg Merge(seg s1,seg s2){seg s;s.l=s1.l,s.r=s2.r;int a=s1.c9,b=s1.c6,c=s2.c9,d=s2.c6;s.dis=max(s1.dis,s2.dis);s.dis=max(s.dis,s1.rp+s2.lm,s1.rm+s2.lp);if (b<c) s.c9=a+c-b,s.c6=d;else s.c9=a,s.c6=b-c+d;s.lp=max(s1.lp,s2.lp+a-b,s2.lm+b+a);s.lm=max(s1.lm,s2.lm+b-a);s.rp=max(s2.rp,s1.rp-c+d,s1.rm+c+d);s.rm=max(s2.rm,s1.rm+c-d);return s;}void Build(int x,int l,int r){if (l==r){a[x].l=l,a[x].r=r;a[x].in(l);return;}int m=(l+r)>>1;Build(x<<1,l,m);Build(x<<1|1,m+1,r);a[x]=Merge(a[x<<1],a[x<<1|1]);}void Modify(int x,int p){if (a[x].l==a[x].r){a[x].in(a[x].l);return;}int m=(a[x].l+a[x].r)>>1;if (p<=m) Modify(x<<1,p);else Modify(x<<1|1,p);a[x]=Merge(a[x<<1],a[x<<1|1]);}int main(){read(n);black=n;for (int i=1;i<=n;i++)c[i]=1;for (int i=1;i<n;i++){int x,y;read(x),read(y);Addedge(x,y),Addedge(y,x);}tot=0;dfs(1,0);Build(1,1,tot);read(q);for (int i=1;i<=q;i++){scanf("%s",str);if (str[0]=='C'){int x;read(x);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",a[1].dis);}}return 0;}

感悟：

1.左括号表示向下走，右括号表示向上走，因此()可以抵消

2.转换成括号序列之后，列出表达式，然后在线段树中维护表达式中出现的量

3.实现的技巧是dfs时把括号和节点都加入，若是黑点括号序列才有意义，否则直接赋值为-inf，不会更新答案

爱情唯美短句子