BZOJ 3553: [Shoi2014]三叉神经树

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

 

 

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/
Avatar_small
Kerala Plus One Prev 说:
2022年8月22日 03:24

The Keralan government offers top-notch instruction, top-notch facilities, and a clean learning atmosphere. As a result of the state board's extensive provision of educational facilities, there has been a yearly increase in education at all levels in the state. On the official website, the Kerala +1 Important Question Paper 2023 was posted. Kerala Plus One Previous Paper 2023 The Kerala +1 Important Question Paper 2023 will be released as soon as it is ready, and the Kerala 11th Model Question Paper of the exams was posted fairly quickly on the official website. By utilising their registration number and Subjects-wise, they may check their Kerala +1 Important Question Paper 2023.


登录 *


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