bzoj 1095 [ZJOI2007]Hide 捉迷藏（括号序列+线段树）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=1095

【题意】

给定一棵树，树上颜色或白或黑而且可以更改，多个询问求最远黑点之间的距离。

【思路】

括号序列+线段树

　对树进行一遍dfs我们可以得到一个括号序列。如：

　　[A[B[E][F[H][I]]][C][D[G]]]

　 E和G之间去掉匹配的括号和字母之后的串就是：

　　　 ]][[

把它看作一个二元组(a,b)表示有a个]和b个[，而且这个二元组的形式一定是…]]]][[[…的，则E G之间的距离为a+b。

线段树维护：每个节点维护7个值如下

a,b:分别表示]和[的数量

dis:max{ a+b } S’为S子串

l1:max{ a+b } S’为S的后缀，且S’紧跟在一个黑色点之后

l2:max{ b-a } S’为S的后缀，且S’紧跟在一个黑色点之后

r1:max{ a+b } S’为S的前缀，且一个黑色点紧跟在S’之后

r2:max{ a-b } S’为S的前缀，且一个黑色点紧跟在S’之后

合并线段树的左右儿子L和R：

dis=max{ L.dis,R.dis,L.a+R.b+|L.b-R.a| }

=max{ L.dis,R.dis,max{ L.r1+R.l2,L.r2+R.l1 } }

//R’定义为R的前缀，且一个黑色点紧跟在R’之后

　 l1=max{ L.l1 , L.a+R’.b+|L.b-R’.a| }

=max{ L.l1 , max{ R.l2+L.a+L.b , R.l1+L.a-L.b } }

l2=max{ L.l2 , max{ R’.b+L.b-R’.a-L.a , R’.b-L.a-R’.a+L.b } }

=max{ L.l2 , R.l2+L.b-L.a }

r1与r2的[推倒]同理，此处略去，直接给出：

r1=max{ R.r1 , max{ L.r1,R.a+R.b , L.r2+R.a+R.b } }

　 r2=max{ R.r2 , L.r2+R.a-R.b }

【代码】

  1 #include<set>
  2 #include<map>
  3 #include<cmath>
  4 #include<cstdio>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<algorithm>
  8 #define FOR(a,b,c) for(int a=b;a<=c;a++)
  9 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
 10 using namespace std;
 11 
 12 typedef long long ll;
 13 const int N = 1e6+10;
 14 const int inf = 1<<25;    //不要太大 
 15 
 16 ll read() {
 17     char c=getchar();
 18     ll f=1,x=0;
 19     while(!isdigit(c)) {
 20         if(c=='-') f=-1; c=getchar();
 21     }
 22     while(isdigit(c))
 23         x=x*10+c-'0',c=getchar();
 24     return x*f;
 25 }
 26 
 27 int n,q,tot;
 28 int vis[N],num[N],pos[N];
 29 
 30 struct Edge { int v,nxt;
 31 }e[N<<1];
 32 int en=1,front[N];
 33 void adde(int u,int v) 
 34 {
 35     e[++en]=(Edge){v,front[u]}; front[u]=en;
 36 }
 37 
 38 struct Tnode {
 39     int a,b,dis,l1,l2,r1,r2;
 40     void val(int x) {
 41         a=b=0;
 42         dis=l1=l2=r1=r2=-inf;
 43         if(x==-1) b=1;
 44         else if(x==-2) a=1;
 45         else if(vis[x]==1) l1=l2=r1=r2=0; 
 46     }
 47     void merge(Tnode L,Tnode R) {
 48         a=L.a+max(0,R.a-L.b);
 49         b=R.b+max(0,L.b-R.a);
 50         dis=max(max(L.dis,R.dis),max(L.r1+R.l2,L.r2+R.l1));
 51         l1=max(L.l1,max(R.l1-L.b+L.a,R.l2+L.b+L.a));
 52         l2=max(L.l2,R.l2+L.b-L.a);
 53         r1=max(R.r1,max(L.r1-R.a+R.b,L.r2+R.a+R.b));
 54         r2=max(R.r2,L.r2+R.a-R.b);
 55     }
 56 }T[N<<1];
 57 
 58 void build(int u,int l,int r) 
 59 {
 60     if(l==r) T[u].val(num[l]);
 61     else {
 62         int mid=(l+r)>>1;
 63         build(u<<1,l,mid);
 64         build(u<<1|1,mid+1,r);
 65         T[u].merge(T[u<<1],T[u<<1|1]);
 66     }
 67 }
 68 void update(int u,int l,int r,int rk) 
 69 {
 70     if(l==r) T[u].val(num[l]);
 71     else {
 72         int mid=(l+r)>>1;
 73         if(rk<=mid) update(u<<1,l,mid,rk);
 74         else update(u<<1|1,mid+1,r,rk);
 75         T[u].merge(T[u<<1],T[u<<1|1]);
 76     }
 77 }
 78 
 79 void dfs(int u,int fa) 
 80 {
 81     num[++tot]=-1;
 82     pos[num[++tot]=u]=tot;
 83     trav(u,i) if(e[i].v!=fa) 
 84         dfs(e[i].v,u);
 85     num[++tot]=-2;
 86 }
 87 
 88 int main()
 89 {
 90     n=read();
 91     int cnt=n;
 92     FOR(i,1,n) vis[i]=1;
 93     FOR(i,1,n-1) {
 94         int u=read(),v=read();
 95         adde(u,v),adde(v,u);
 96     }
 97     dfs(1,-1);
 98     build(1,1,tot);
 99     q=read();
100     char op[5]; int x;
101     while(q--) {
102         scanf("%s",op);
103         if(op[0]=='G') {
104             if(cnt==0) puts("-1");
105             else if(cnt==1) puts("0");
106             else printf("%d\n",T[1].dis);
107         }
108         else {
109             x=read();
110             cnt+=vis[x]=-vis[x];
111             update(1,1,tot,pos[x]);
112         }
113     }
114     return 0;
115 }

Cqx论文 click here

秒客网

bzoj 1095 [ZJOI2007]Hide 捉迷藏（括号序列+线段树）

相关文章