首页 > 代码库 > 【BZOJ-3553】三叉神经树 树链剖分
【BZOJ-3553】三叉神经树 树链剖分
3553: [Shoi2014]三叉神经树
Time Limit: 160 Sec Memory Limit: 256 MBSubmit: 347 Solved: 112
[Submit][Status][Discuss]
Description
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。
每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞;并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 0 和 1 两种。每个 SHOI 细胞根据三个输入端中 0 和 1 信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
Input
第一行一个整数:n。表示 SHOI 组织的总细胞个数。SHOI 细胞由 1~n 编号,编号为 1 的是根细胞。
从第二行开始的 n 行,每行三个整数 x1, x2, x3,分别表示编号为 1~n 的 SHOI 细胞的树突连接。1<xi≤n 表示连向编号为 xi 的细胞的轴突, n<xi≤3n+1 表示连向编号为 xi 的外界输入。输入数据保证给出的 SHOI 组织是合法的且所有的 xi 两两不同。
接下来一行 2n+1 个 0/1 的整数,表示初始时的外界输入。
第 n+3 行有一个整数:q,表示总操作数。
之后 q 行每行一个整数 x,表示编号为 x 的外界输入发生了变化。
Output
输出 q 行每行一个整数,对应第 i 次外界输入变化后的根细胞的输出。
Sample Input
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8
Sample Output
0
0
1
1
HINT
对于 100%的数据,n≤500000,q≤500000。
Source
By 佚名提供
Solution
这题还真是不错。
首先题意就是说，一共有N个节点，然后有其余2*N+1个节点，这些节点成三叉树，然后2*N+1个点有初始0/1值，定义一个非叶子节点的值为它三个孩子中0/1较多的。每次改变2*N+1个节点中的一个0/1值，并输出根节点的值是多少。
这么一看我们发现，对于一个非叶子节点，它的权值状态是可数的000,100,010,001,110,101,011,111，我们不妨设状态为val，那么val=2/3时值为1，val=0/1时值为0
对一个叶子节点权值取反，则它可能直接影响到它的fa，它的fa又可能会影响到fa到root这个路径上的一段节点。
实际上，只有在它的fa的val从2->1或者1->2的时候会对它到root的路径上的点可能产生影响。
那么我们用树链剖分去维护这N个非叶子节点。对于每个区间，我们维护最长的靠右的连续val=1/2的长度
树链在线段树上是从上到下按从左到右存的，而我们每次会影响到的，就是fa->root中连续的与fa直接相连的那段1/2；因为显然fa的改变这会引起他们的改变。，所以这里是靠右的连续的长度
就是说当fa.val=1->2它到root这条路径上，与它直接相连的1都会更改成2；当val=2->1时同理。
我们在覆盖完这连续的区间后，对于区间上面那个点也进行单点修改，其效果大致类似于修改。
同样是可以维护连续靠右的val=1/2的左端，但是树链剖分中链在线段树中是连续的，所以其实只记录长度即可。
Code
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>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;}#define MAXN 500010 int N,Q,val[MAXN*3],fa[MAXN*3],V[MAXN];struct EdgeNode{int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}void InsertEdge(int u,int v) {fa[v]=u; if (v>N) return; AddEdge(u,v); AddEdge(v,u);}int size[MAXN],deep[MAXN],pl[MAXN],dfn,pr[MAXN],pre[MAXN],top[MAXN],son[MAXN];namespace SegmentTree{ //len[1]left[1]表示连续val=1，len[2]left[2]表示连续val=2 struct SegmentTreeNode{int l,r,size,val,tag,len[3];}tree[MAXN<<2]; #define ls now<<1 #define rs now<<1|1 inline void Merge(SegmentTreeNode &rt,SegmentTreeNode lson,SegmentTreeNode rson) { for (int i=1; i<=2; i++) if (rson.len[i]==rson.size) rt.len[i]=lson.len[i]+rson.len[i]; else rt.len[i]=rson.len[i]; } inline void Update(int now) {Merge(tree[now],tree[ls],tree[rs]);} inline void cover(int now,int D) { tree[now].val=D; tree[now].tag=D; tree[now].len[1]=tree[now].len[2]=0; if (D==1) tree[now].len[1]=tree[now].size; if (D==2) tree[now].len[2]=tree[now].size; } inline void PushDown(int now) { if (tree[now].l==tree[now].r || tree[now].tag==-1) return; int delta=tree[now].tag; cover(ls,delta); cover(rs,delta); tree[now].tag=-1; } inline void BuildTree(int now,int l,int r) { tree[now].l=l; tree[now].r=r; tree[now].size=r-l+1; tree[now].tag=-1; tree[now].len[1]=tree[now].len[2]=0; if (l==r) { tree[now].val=V[l]; if (tree[now].val==1) tree[now].len[1]=1; if (tree[now].val==2) tree[now].len[2]=1; return; } int mid=(l+r)>>1; BuildTree(ls,l,mid); BuildTree(rs,mid+1,r); Update(now); } inline void Cover(int now,int L,int R,int D) { int l=tree[now].l,r=tree[now].r; PushDown(now); if (L<=l && R>=r) {cover(now,D); return;} int mid=(l+r)>>1; if (L<=mid) Cover(ls,L,R,D); if (R>mid) Cover(rs,L,R,D); Update(now); } inline SegmentTreeNode Query(int now,int L,int R) { SegmentTreeNode rl,rr,re; bool fl=0,fr=0; int l=tree[now].l,r=tree[now].r; PushDown(now); if (L<=l && R>=r) return tree[now]; int mid=(l+r)>>1; if (L<=mid) fl=1,rl=Query(ls,L,R); if (R>mid) fr=1,rr=Query(rs,L,R); if (fl && !fr) return rl; if (!fl && fr) return rr; if (fl && fr) return Merge(re,rl,rr),re; }}using namespace SegmentTree;inline void DFS_1(int now){ size[now]=1; for (int i=head[now]; i; i=edge[i].next) if (edge[i].to!=fa[now]) { deep[edge[i].to]=deep[now]+1; DFS_1(edge[i].to); size[now]+=size[edge[i].to]; if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to; }}inline void DFS_2(int now,int chain){ pl[now]=++dfn; pre[dfn]=now; top[now]=chain; if (son[now]) DFS_2(son[now],chain); for (int i=head[now]; i; i=edge[i].next) if (edge[i].to!=fa[now] && edge[i].to!=son[now]) DFS_2(edge[i].to,edge[i].to); pr[now]=dfn;}void DFS(int now){ for (int i=head[now]; i; i=edge[i].next) if (edge[i].to!=fa[now]) DFS(edge[i].to),val[now]+=val[edge[i].to]>=2? 1:0;}void Solve(int x,int y){ int L,R,len,t,last,now; bool f,flag=0; if (val[x]==1) f=1; else f=0; val[x]^=1; last=val[fa[x]]; val[fa[x]]+=f? -1:1; now=val[fa[x]]; t=x=fa[x]; if (now==0 || now==3) {SegmentTree::Cover(1,t,t,now); printf("%d\n",SegmentTree::Query(1,1,1).val>=2? 1:0); return;} if (now==1 && last==0 || now==2 && last==3) {SegmentTree::Cover(1,t,t,now); printf("%d\n",SegmentTree::Query(1,1,1).val>=2? 1:0); return;} if (now==1 && last==2) f=1; else f=0; while (top[x]!=top[y]) {// printf("Now(%d , %d)\n",x,y); if (deep[top[x]]<deep[top[y]]) swap(x,y); L=top[x],R=x; SegmentTreeNode t=Query(1,L,R); if (f) len=t.len[2]; else len=t.len[1]; if (len==R-L+1) SegmentTree::Cover(1,L,R,f? 1:2); else {L=L-len+1,SegmentTree::Cover(1,L,R,f? 1:2); flag=1; break;} x=fa[top[x]]; } if (!flag) { if (deep[x]>deep[y]) swap(x,y); L=x,R=y; SegmentTreeNode t=Query(1,L,R); if (f) len=t.len[2]; else len=t.len[1]; if (len==R-L+1) SegmentTree::Cover(1,L,R,f? 1:2); else L=L-len+1,SegmentTree::Cover(1,L,R,f? 1:2); }// puts("===========================================");// for (int i=1; i<=5; i++) printf("%d %d %d %d %d %d %d\n",i,tree[i].l,tree[i].r,tree[i].size,tree[i].val,tree[i].len[1],tree[i].len[2]); t=fa[pre[L]]; if (t) SegmentTree::Cover(1,t,t,f? val[t]-1:val[t]+1); val[t]+=f? -1:1; printf("%d\n",SegmentTree::Query(1,1,1).val>=2? 1:0);}int main(){ N=read(); for (int x,y,z,i=1; i<=N; i++) x=read(),y=read(),z=read(),InsertEdge(i,x),InsertEdge(i,y),InsertEdge(i,z); for (int i=1; i<=2*N+1; i++) val[N+i]=read(),val[fa[N+i]]+=val[N+i]; Q=read(); DFS(1); DFS_1(1); DFS_2(1,1); for (int i=1; i<=N; i++) V[pl[i]]=val[i]; SegmentTree::BuildTree(1,1,N); while (Q--) {int pos=read(); Solve(pos,1);} return 0;}
【BZOJ-3553】三叉神经树 树链剖分