bzoj1095 [ZJOI2007]Hide 捉迷藏 括号序列/动态点分治/树的数据生成

bzoj1095 [ZJOI2007]Hide 捉迷藏 括号序列/动态点分治/树的数据生成

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。

括号序列的这个方法real神奇

按照深搜序我进这个之前来一个左括号 出这个的时候来个右括号 那么我们最后把这个括号序列生成出来 中间如果匹配就消去 那么这个括号序列最长的部分就是我想要的答案 因为一个括号匹配了就代表这进去将是一个子树 不可能是简单路径 此外感谢zhx巨佬给予的讲解 要不然是不可能理解这题的orz 那么这个怎么维护 我需要存放七个值 分别代表什么 a,b代表这个序列里右括号和左括号的数量 那么以后就用a,b来代替了dis就是我当前这个序列里最长的是多少 lplus就是左起a+b的最大值rplus是右起a+b的最大值 同理lminus是左起b-a的最大值 rminus是右起a-b的最大值 然后像线段树合并一样 分别讨论一下这个最大值是如何维护的 然后这些值都是怎么更新得到的 并且注意有可能不存在点或者只有一个点那么分别输出-1和0怎么搞 我是每个节点记录个size然后每次都update一下 这就可能造成蒟蒻我常数巨大 还有就是这个位置不是(x-1)*3+2因为这个括号序列匹配不确定..我后来选择记录一个Pos数组来搞定

​​E 和 G ，取出介于它们之间的那段括号编码 ：][[][]]][][[把匹配的括号去掉，得到：]][[我们看到 2 个 ] 和 2 个 [，也就是说，在树中，从 E 向上爬 2 步，再向下走 2 步就到了 G。注意到，题目中需要的信息只有这棵树中点与点的距离，所以，贮存编码中匹配的括号是没有意义的。因此，对于介于两个节点间的一段括号编码 S，可以用一个二元组 (a, b) 描述它，即这段编码去掉匹配括号后有 a 个 ] 和 b 个 [。所以，对于两个点 PQ，如果介于某两点 PQ 之间编码 S 可表示为 (a, b)，PQ 之间的距离就是 a+b。也就是说，题目只需要动态维护：max{a+b | S’(a, b) 是 S 的一个子串，且 S’ 介于两个黑点之间}，这里 S 是整棵树的括号编码。我们把这个量记为 dis(s)。现在，如果可以通过左边一半的统计信息和右边一半的统计信息，得到整段编码的统计，这道题就可以用熟悉的线段树解决了。这需要下面的分析。考虑对于两段括号编码 S1(a1, b1) 和 S2(a2, b2)，如果它们连接起来形成 S(a, b)。注意到 S1、S2 相连时又形成了 min{b, c} 对成对的括号，合并后它们会被抵消掉。（？..这里 b, c 应该分别是指 b1 和 a2。。。所以：当 a2 < b1 时第一段 [ 就被消完了，两段 ] 连在一起，例如：] ] [ [ + ] ] ] [ [ = ] ] ] [ [当 a2 >= b1 时第二段 ] 就被消完了，两段 [ 连在一起，例如：] ] [ [ [ + ] ] [ [ = ] ] [ [ [ （？..反了？。。。这样，就得到了一个十分有用的结论：当 a2 < b1 时，(a,b) = (a1-b1+a2, b2)，当 a2 >= b1 时，(a,b) = (a1, b1-a2+b2)。由此，又得到几个简单的推论：(i) a+b = a1+b2+|a2-b1| = max{(a1-b1)+(a2+b2), (a1+b1)+(b2-a2)}(ii) a-b = a1-b1+a2-b2(iii) b-a = b2-a2+b1-a1由 (i) 式，可以发现，要维护 dis(s)，就必须对子串维护以下四个量：right_plus：max{a+b | S’(a,b) 是 S 的一个后缀，且 S’ 紧接在一个黑点之后}right_minus：max{a-b | S’(a,b) 是 S 的一个后缀，且 S’ 紧接在一个黑点之后}left_plus：max{a+b | S’(a,b) 是 S 的一个前缀，且有一个黑点紧接在 S 之后}left_minus：max{b-a | S’(a,b) 是 S 的一个前缀，且有一个黑点紧接在 S 之后}这样，对于 S = S1 + S2，其中 S1(a, b)、S2(c, d)、S(e, f)，就有(e, f) = b < c ? (a-b+c, d) : (a, b-c+d)dis(S) = max{dis(S1), left_minus(S2)+right_plus(S1), left_plus(S2)+right_minus(S1), dis(S2)}那么，增加这四个参数是否就够了呢？是的，因为：right_plus(S) = max{right_plus(S1)-c+d, right_minus(S1)+c+d, right_plus(S2)}right_minus(S) = max{right_minus(S1)+c-d, right_minus(S2)} left_plus(S) = max{left_plus(S2)-b+a, left_minus(S2)+b+a, left_plus(S1)} left_minus(S) = max{left_minus(S2)+b-a, left_minus(S1)} 这样一来，就可以用线段树处理编码串了。实际实现的时候，在编码串中加进结点标号会更方便，对于底层结点，如果对应字符是一个括号或者一个白点，那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -maxlongint；如果对应字符是一个黑点，那么 right_plus、right_minus、left_plus、left_minus 都是 0，dis 是 -maxlongint。现在这个题得到圆满解决，回顾这个过程，可以发现用一个串表达整棵树的信息是关键，这一“压”使得线段树这一强大工具得以利用.. .

———— 以上摘自 NOI08 冬令营论文 《数据结构的提炼与压缩》 by cqx 。。。

以上来自岛娘的blog

#include#include#define N 110000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}struct node{ int y,next;}data[N<<1];struct tr{ int left,right,a,b,lminus,rminus,lplus,rplus,dis,size;}tree[N<<3];int que[N<<2],h[N],num,tot,root,n,m,pos[N];inline void dfs(int x,int fa){ que[++num]=2;que[++num]=3;pos[x]=num; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; dfs(y,x); }que[++num]=1;}inline void update(int x){ int l=tree[x].left,r=tree[x].right;bool flag=0; if (tree[l].b>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);update(x);}inline void insert1(int x,int l,int r,int p){ if (l==r){ if (tree[x].lminus==-inf) tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=0,tree[x].size=1; else tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=-inf,tree[x].size=0;return; }int mid=l+r>>1; if (p<=mid) insert1(tree[x].left,l,mid,p);else insert1(tree[x].right,mid+1,r,p);update(x);}int main(){ freopen("bzoj1095.in","r",stdin); n=read(); for (int i=1;i

动态点分治 顾名思义 就是动态的.. 假如这题不需要有修改操作 那我是不是一遍朴素的点分就可以搞定了 但是现在存在修改怎么办 动态点分的操作就是我首先一遍点分把所有的重心提早找出 然后针对每一个重心的节点我像线段树一样串联起来 这样最多有log层 并且呢 为了统计 我在每个节点上暴力的使用一个数据结构 堆/multiset 来保证我的复杂度 变成n*(logn)^2的 我开设b[x]表示我x分治的这个区域中 所有子树包括自己到我上一层分治点的距离 维护一个大根堆 c[x]表示我x分治区域的这个子树中的每个点到我x节点的上一个分治节点的距离 那么同样也是维护一个大根堆 即可 这个再开设一个A表示全局的最大值 全局最大值都由什么什么构成 那显然就是每个B里面我去选一个最大和次大组合起来啊 但是堆需要删除操作 所以一个小trick 一个堆打标记一个堆加入 或者直接使用Multiset但是效率上会低一点另外为了优化常数还可以使用rmq的lca

代码有些丑陋 因为multiset的用法和priority_queue的用法我都放在一起了turn_on1&turn_off1是multi set的 bzoj大概十多秒吧 用堆的方法就比较快了 turn_on turn_off是堆来维护的

可以自行选择是使用那个此外求lca的方法也是两种lca1是rmq的方法 lca就是普通的倍增 rmq的lca怎么搞 首先遍历一遍整棵树 然后一进一出针对每条边记录两次 一共获得2*n-1个点 先按照顺序把他们依次填入mn数组 然后记录下在mn数组中对应的位置 （注意开数组的时候二倍 预处理log数组的时候也需要预处理两倍的 然后我利用动态规划的思想去搞 设mn[i][j]表示i起始长度为2^j 表示这一段深度最浅的点是谁那么 询问u,v的时候直接返回这两个区间中深度最小的点是谁 即使可能包括u的子树的节点也无妨 因为深度最浅的一定是他们的lca

#include#include#include#include#define N 110000#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}multiset a,b[N],c[N];int h[N],num,n,far[N],fa[N][20],dep[N],root,f[N],size[N],sum,m,cnt,bin[20];int Log[N<<1],tot,mn[N<<1][20],pos[N],tot1;bool visit[N],light[N];struct node{ int y,next;}data[N<<1];struct heap{ priority_queue 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; }}B[N],C[N],A;inline void dfs(int x){ mn[++tot1][0]=x;pos[x]=tot1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (fa[x][0]==y) continue;fa[y][0]=x; dep[y]=dep[x]+1;for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1]; dfs(y);mn[++tot1][0]=x; }}inline void init(){ int t=Log[tot1]; for (int j=1;j<=t;++j) for (int i=1;i<=tot1;++i){ if(i+bin[j-1]>tot1) break; if(dep[mn[i][j-1]]f[x]) root=x;}inline void solve1(int x,int father){ far[x]=father;visit[x]=1;int sum1=sum; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]) continue; root=0;if (size[y]>size[x]) sum=sum1-size[x];else sum=size[y]; get_root(y,x);solve1(root,x); }}inline int lca(int x,int y){ if (dep[x]r) swap(l,r); int t=Log[r-l+1]; return dep[mn[l][t]]::iterator ii; if(c[x].empty()) return 0; ii=c[x].end();--ii;return *ii;}inline int b_top(int x){ multiset::iterator ii; if(b[x].empty()) return 0; ii=b[x].end();--ii;return *ii;}inline int b_stop(int x){ multiset::iterator ii; if(b[x].size()<2) return 0; ii=b[x].end();--ii;--ii;return *ii;}inline void turn_on1(int x,int v){ if (x==v){ b[x].insert(0); if (b[x].size()==2) a.insert(b_top(x)); }if(!far[x]) return;int y=far[x],D=dis(y,v); int tmp=c_top(x);c[x].insert(D); if (D>tmp){ int max1=b_top(y)+b_stop(y),sz=b[y].size(); if (tmp)b[y].erase(b[y].find(tmp));b[y].insert(D); int now=b_top(y)+b_stop(y); if (now>max1){ if (sz>=2) a.erase(a.find(max1)); if (b[y].size()>=2) a.insert(now); } }turn_on1(y,v);}inline void turn_on(int x,int v){ if (x==v){ B[x].push(0);//把x点改成黑点 if (B[x].size()==2) A.push(B[x].top());//如果添加上自己正好有两个黑点那么就可以对全局答案产生贡献 }if (!far[x]) return;int y=far[x],D=dis(y,v);//算出被改点到x's father的距离 int tmp=C[x].top();C[x].push(D);//取出最大值 然后将新的距离放入 if (D>tmp){//当x子树到y的最大深度变化了 需要更改B[Y]的值 int max1=B[y].top()+B[y].stop(),sz=B[y].size(); if (tmp) B[y].erase(tmp);B[y].push(D); int now=B[y].top()+B[y].stop(); if (now>max1){//这时 过Y的合法路径出现了不同 需要去全局修改 if (sz>=2) A.erase(max1); if (B[y].size()>=2) A.push(now); } }turn_on(y,v);}inline void turn_off1(int x,int v){ if (x==v){ b[x].erase(b[x].find(0)); if (b[x].size()==1) a.erase(a.find(b_top(x))); }if (!far[x]) return;int y=far[x],D=dis(y,v); int tmp=c_top(x);c[x].erase(c[x].find(D)); if (D==tmp){ int max1=b_top(y)+b_stop(y),sz=b[y].size(); b[y].erase(b[y].find(tmp)); if (c_top(x)) b[y].insert(c_top(x)); int now=b_top(y)+b_stop(y); if (now=2) a.erase(a.find(max1)); if (b[y].size()>=2) a.insert(now); } }turn_off1(y,v);}inline void turn_off(int x,int v){ if (x==v){ B[x].erase(0); if (B[x].size()==1) A.erase(B[x].top()); }if (!far[x]) return;int y=far[x],D=dis(y,v); int tmp=C[x].top();C[x].erase(D); if (D==tmp){ int max1=B[y].top()+B[y].stop(),sz=B[y].size(); B[y].erase(tmp);if (C[x].top()) B[y].push(C[x].top()); int now=B[y].top()+B[y].stop(); if (now=2) A.erase(max1); if (B[y].size()>=2) A.push(now); } }turn_off(y,v);}int main(){ freopen("bzoj1095.in","r",stdin);// freopen("bzoj1095.out","w",stdout); n=read();for (int i=0;i<=18;++i) bin[i]=1<>1]+1; for (int i=1;i<=n;++i) light[i]=1;cnt=n; for (int i=1;i::iterator ii=a.end();--ii;printf("%d\n",*ii); printf("%d\n",A.top()); } } return 0;}

一开始lca倍增写的有问题 找错足足找了很久orz菜死 然后想办法 怎么去生成一个树然后翻了很久终于找到一个可用的代码 可以生成一棵树 用的是prufer编码 如何生成一棵树 即树的数据生成器

怎么搞 首先先随机一个prufer含有n-2个元素 然后再生成一个集合1~n那么每次我去找一下最小的那个没有在prufer序列中出现的数 把他们连起来 然后在prufer序列中删掉他们重复以上步骤 然后再把最后的两个点连起来即可 对于代码中的做法 就是首先我给每个点度为1 然后随机一个prufer序列把序列里的点的度都+1 然后先按照度排序找到第一个不为0的点 输出prufer序列中的值和我的编号 然后把我的度-1 prufer序列中那个数也-1 程序中我现在固定枚举prufer编码了那么我肯定需要找啊一个不存在这里的数和当前的prufer编码连接 然后把这个删掉 原数列中的度也-1说明现在可以出现在prufer编码中了 因为原来的已经被我删掉了 这个非0就是为了防止重复利用

#include#include#include#include#includeusing namespace std;int a[30000+20];struct nod{ int id,d;}d[30000+20];bool cmpid(nod x,nod y)//按编号排序{ return x.id

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。