BZOJ 3553: [Shoi2014]三叉神经树

qwer posted @ 2014年5月18日 15:12 in Bzoj with tags [Shoi2014]三叉神经树 , 987 阅读

 

 

BZOJ 3553: [Shoi2014]三叉神经树

Time Limit: 160 Sec  Memory Limit: 256 MB

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

3
2 3 4
5 6 7
8 9 10
0 0 0 0 1 1 1
5
4
4
5
6
8

Sample Output

1
0
0
1
1

HINT

 

对于 100%的数据,n≤500000,q≤500000。

 

Solution

    定义col[x]为x点输出的信号,val[x]为x点的孩子节点输出的信号和,易知col[x]∈{0,1},val[x]∈{0,1,2,3}。

    由于每次修改操作只会改变该点到根的路径上的点,所以可以树剖 (当然lct也可以 xllend3半个小时就解决了 orz)

    将col=0的点称为白点,将col=1的点称为黑点。

    考虑将一个白点x变为黑点,只有val[x]=1时才会对val[fa[x]]产生影响,那么在线段树中维护从左边开始连续相同的数的个数、从右边开始连续相同的数的个数即可。将一个黑点变白点也一样操作。

    修改只有将一段数加一或减一,加个标记即可。

Code

//+-------------------------------------+
//|     By   qwer_zcc                   |
//|     Date 18/05/2014                 |
//+-------------------------------------+
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#define INF 1000000000
#define LL long long
#define uLL unsigned long long
#define uint unsigned int
#define D double
#define LD long double
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define dep(i,a,b) for (int i=a;i>=b;i--)
#define M(a) memset(a,0,sizeof(a));
#define Chen(a,b,c) int((LL)(a)*(LL)(b)%(LL)(c))
#define pb push_back
#define mp make_pair
#define ins insert
#define ps push
#define Pi M_PI
using namespace std;
template<class T> inline T abs(T &a) {return a>0?a:-a;}
template<class T> inline T min(T &a,T &b) {return a<b?a:b;}
template<class T> inline T max(T &a,T &b) {return a>b?a:b;}
inline void read(int &x)
{
	char ch;
	while ((ch=getchar()) && !(ch>='0' && ch<='9'));x=ch-'0';
	while ((ch=getchar()) && (ch>='0' && ch<='9')) x=x*10+ch-'0';
}
struct point
{
	int x,y;
	point() {}
	point(int _x,int _y) : x(_x),y(_y) {}
} ;
const int N=2100000;
vector<int>E[N];
int dep[N],size[N],n,val[N],col[N],dfn[N],ti,An[N],dy[N],nn,f[N][2];
void add(int x,int y){E[x].pb(y);}
void dfs(int x,int Fa)
{
    f[x][0]=Fa;if (x>nn) return;
	size[x]=1;
    int gs=0;
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa)
	{
		dfs(E[x][i],x);
		val[x]+=col[E[x][i]];
		if (col[E[x][i]]) gs++;
		size[x]+=size[E[x][i]];
	}
	if (gs>1) col[x]=1;
	else col[x]=0;
}
void Dfs(int x,int Fa,int c)
{
	if (x>nn) return;
    dfn[x]=++ti;An[x]=c;dy[ti]=x;
    int Max=0,il=0;
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa) if (size[E[x][i]]>Max) Max=size[E[x][i]],il=E[x][i];
    if (il) Dfs(il,x,c);
    for (int i=0;i<E[x].size();i++)
    if (E[x][i]!=Fa && E[x][i]!=il) Dfs(E[x][i],x,E[x][i]);
}

// Segment Tree Begin
struct lj{int Lc,Rc,L,R,flag,l,r,sum;}t[N];
void Ch(int w,int c)
{
	t[w].Lc+=c,t[w].Rc+=c;t[w].flag+=c;
}
void push(int w)
{
	if (t[w].flag!=0)
	{
		int l=w<<1;
		if (t[l].l) Ch(l,t[w].flag);
		l|=1;
		if (t[l].l) Ch(l,t[w].flag);
		t[w].flag=0;
	}
}
void update(int w)
{
	int L=w<<1,R=w<<1|1;
	if (t[L].Rc==t[R].Lc && t[R].sum==t[R].r-t[R].l+1) t[w].R=t[L].R+t[R].sum;
		else t[w].R=t[R].R;
	if (t[L].Rc==t[R].Lc && t[L].sum==t[L].r-t[L].l+1) t[w].L=t[L].sum+t[R].L;
		else t[w].L=t[L].L;
	t[w].sum=max(t[w].L,t[w].R);
	if (t[L].Rc==t[R].Lc) t[w].sum=max(t[w].sum,t[L].R+t[R].L);
	t[w].Lc=t[L].Lc;
	t[w].Rc=t[R].Rc;
}
void build(int w,int l,int r)
{
	t[w].l=l;t[w].r=r;
	if (l==r)
	{
		t[w].Lc=t[w].Rc=val[dy[l]];
		t[w].sum=t[w].L=t[w].R=1;
		return;
	}
	int mid=l+r>>1;
	build(w<<1,l,mid);build(w<<1|1,mid+1,r);
	update(w);
}
int ask_dig(int w,int l)
{
	push(w);
	if (t[w].l==t[w].r) return t[w].Lc;
	int mid=t[w].l+t[w].r>>1;
	if (l<=mid) return ask_dig(w<<1,l);
	else return ask_dig(w<<1|1,l);
}
int ask_Len(int w,int l,int r)
{
	push(w);
	if (t[w].l==l && t[w].r==r) return t[w].R;
	int mid=t[w].l+t[w].r>>1;
	if (r<=mid) return ask_Len(w<<1,l,r);
	else if (l>mid) return ask_Len(w<<1|1,l,r);
	else
	{
		int c=ask_Len(w<<1|1,mid+1,r);
		if (c<r-mid||t[w<<1].Rc!=t[w<<1|1].Lc) return c;
		else return c+ask_Len(w<<1,l,mid);
	}
}
void add(int w,int l,int r,int c)
{
	push(w);
	if (t[w].l==l && t[w].r==r)
	{
		Ch(w,c);
		return;
	}
	int mid=t[w].l+t[w].r>>1;
	if (r<=mid) add(w<<1,l,r,c);
	else if (l>mid) add(w<<1|1,l,r,c);
	else add(w<<1,l,mid,c),add(w<<1|1,mid+1,r,c);
	update(w);
}
//Segment Tree End
void Add(int x)
{
	int xx=x;
	while (x)
	{
		if (ask_dig(1,dfn[x])!=1)
		{
			add(1,dfn[x],dfn[x],1);
			break;
		}
		int c=ask_Len(1,dfn[An[x]],dfn[x]);
		add(1,max(dfn[x]-c+1,1),dfn[x],1);
		if (max(dfn[x]-c+1,1)!=1 && c!=dfn[x]-dfn[An[x]]+1) add(1,dfn[f[ dy[dfn[x]-c+1] ][0]] , dfn[f[ dy[dfn[x]-c+1] ][0]] , 1);
		if (c!=dfn[x]-dfn[An[x]]+1) break;
		x=f[An[x]][0];
	}
}
void Del(int x)
{
	int xx=x;
	while (x)
	{
		if (ask_dig(1,dfn[x])!=2)
		{
			add(1,dfn[x],dfn[x],-1);
			break;
		}
		int c=ask_Len(1,dfn[An[x]],dfn[x]);
		add(1,max(dfn[x]-c+1,1),dfn[x],-1);
		if (max(dfn[x]-c+1,1)!=1 && c!=dfn[x]-dfn[An[x]]+1) add(1,dfn[f[ dy[dfn[x]-c+1] ][0]] , dfn[f[ dy[dfn[x]-c+1] ][0]] , -1);
		if (c!=dfn[x]-dfn[An[x]]+1) break;
		x=f[An[x]][0];
	}
}

int main()
{
	read(n);int x,y,z;nn=n;
	rep(i,1,n)
	{
		read(x);read(y);read(z);
		add(i,x);add(i,y);add(i,z);
	}
	rep(i,1,n*2+1) read(col[i+n]);
	n=n*3+1;
	dfs(1,0);Dfs(1,0,1);
	n=nn;
	build(1,1,n);int m;
	read(m);
	rep(i,1,m)
	{
		read(x);
		if (!col[x])  // 0->1 find 1
		{
			col[x]^=1;
			Add(f[x][0]);
		}
		else // 1->0 find 2
		{
			col[x]^=1;
			Del(f[x][0]);
		}
		printf("%d\n",ask_dig(1,1)>1);
	}
}
Orz __Shi - > http://shizhouxing.is-programmer.com/

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter