三叉神经树 ( neuron )

题目描述

计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物SHTSC 的密切联系引起了人们的极大关注。

SHOI 组织由若干个SHOI 细胞构成，SHOI 细胞之间形成严密的树形结构。每个SHOI 细胞都有且只有一个输出端，被称为轴突，除了一个特殊的、被称为根细胞的SHOI 细胞的输出作为整个组织的输出以外，其余细胞的轴突均连向其上级SHOI 细胞；并且有且只有三个接收端，被称为树突，从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单，仅有0 和1 两种。每个SHOI 细胞根据三个输入端中0 和1 信号的多寡输出较多的那一种。

现在给出了一段SHOI 组织的信息，以及外部神经组织的输入变化情况。请你模拟SHOI 组织的输出结果。

输入

第一行一个整数：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 的外界输入发生了变化。

输出

输出q 行每行一个整数，对应第i 次外界输入变化后的根细胞的输出。

样例输入

3

2 3 4

5 6 7

8 9 10

0 0 0 0 1 1 1

5

4

4

5

6

8

样例输出

提示

【数据规模】

对于10%的数据，n, q≤1000。

对于额外10%的数据，修改仅会将0 修改成1。

对于额外30%的数据，输入的SHOI 形成以根为端点的一条链。

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

来源

SHTSC2014day2

假设num[i]表示i有几个1节点

每次相当于询问i到根路径上第一个num不等于1或不等于2的点，然后区间加。

于是又是这奇怪的线段树上查询

先查右区间，如果没有再查左区间

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 500005

using namespace std;

int n,head[maxn],son[maxn],top[maxn],size[maxn],fa[maxn*3];

int deep[maxn],dfn[maxn],sc,x1,x2,x3,tot,root,dy[maxn],ch[maxn][3],aa[maxn];

int val[maxn*3],Q,t,li,ri,op;

struct node{

    int nex,v;

}e[maxn*2];

struct no{

    int l,r,ma,mi,bj;

}tree[maxn*4];

void lj(int t1,int t2){

    e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;

}

void dfs1(int k,int fath){

    deep[k]=deep[fath]+1;

    int gp=-1,sz=0;

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v!=fath){

            dfs1(e[i].v,k);

            if(gp==-1)gp=e[i].v;

            if(size[e[i].v]>size[gp])gp=e[i].v;

            sz+=size[e[i].v];

        }

    }

    int co=0;

    co+=val[ch[k][0]]+val[ch[k][1]]+val[ch[k][2]];

    aa[k]=co;

    if(co>1)val[k]=1;

    son[k]=gp,size[k]=sz+1;

}

void dfs2(int k){

    dfn[k]=++sc;dy[sc]=k;

    if(son[k]!=-1)top[son[k]]=top[k],dfs2(son[k]);

    for(int i=head[k];i;i=e[i].nex){

        if(e[i].v!=son[k]&&e[i].v!=fa[k]){

            top[e[i].v]=e[i].v;

            dfs2(e[i].v);

        }

    }

}

void wh(int k){

    tree[k].ma=max(tree[k*2].ma,tree[k*2+1].ma);

    tree[k].mi=min(tree[k*2].mi,tree[k*2+1].mi);

}

void down(int k){

    if(tree[k].bj!=0){

        int fs=tree[k].bj;

        tree[k*2].ma+=fs,tree[k*2].mi+=fs;tree[k*2].bj+=fs;

        tree[k*2+1].ma+=fs,tree[k*2+1].mi+=fs;tree[k*2+1].bj+=fs;

        tree[k].bj=0;

    }

}

void build(int k,int L,int R){

    tree[k].l=L,tree[k].r=R;

    if(L==R){

        tree[k].ma=tree[k].mi=aa[dy[L]];

        return;

    }

    int mid=L+R>>1;

    build(k*2,L,mid);build(k*2+1,mid+1,R);

    wh(k);

}

int find(int k){

    if(tree[k].l==tree[k].r){

        if(tree[k].ma!=op)return tree[k].l;

        else return 0;

    }

    if(tree[k].l>=li&&tree[k].r<=ri&&tree[k].ma==tree[k].mi&&tree[k].ma==op)return 0;

    down(k);

    int mid=tree[k].l+tree[k].r>>1,ans=0;

    if(ri<=mid)return find(k*2);

    if(li>mid)return find(k*2+1);

    if(ri>mid)ans=find(k*2+1);

    if(!ans&&li<mid)ans=find(k*2);

    return ans;

}

void jia(int k){

    if(tree[k].l>=li&&tree[k].r<=ri){

        if(op==1)tree[k].ma++,tree[k].mi++,tree[k].bj++;

        else tree[k].ma--,tree[k].mi--,tree[k].bj--;

        return;

    }

    down(k);

    int mid=tree[k].l+tree[k].r>>1;

    if(li<=mid)jia(k*2);

    if(ri>mid)jia(k*2+1);

    wh(k);

}

int ask(int k){

    //cout<<tree[k].l<<' '<<tree[k].r<<endl;

    if(tree[k].l==tree[k].r)return tree[k].ma;

    down(k);

    return ask(k*2);

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++){

        scanf("%d%d%d",&x1,&x2,&x3);

        fa[x1]=fa[x2]=fa[x3]=i;

        ch[i][0]=x1,ch[i][1]=x2,ch[i][2]=x3;

        if(x1<=n)lj(i,x1);

        if(x2<=n)lj(i,x2);

        if(x3<=n)lj(i,x3);

    }

    for(int i=1;i<=n;i++)if(!fa[i])root=i;

    for(int i=n+1;i<=3*n+1;i++)scanf("%d",&val[i]);

    dfs1(root,0);top[root]=root;dfs2(root);

    build(1,1,n);

    cin>>Q;

    while(Q--){

        scanf("%d",&t);val[t]^=1;

        if(val[t]==1)op=1;else op=2;

        int a=fa[t],t1=top[a];

        while(a){

            li=dfn[t1],ri=dfn[a];

            int pl=find(1);

            if(pl){

                li=pl,ri=dfn[a];

                jia(1);break;

            }

            jia(1);

            a=fa[t1];t1=top[a];

        }

        int ans=ask(1);

        if(ans>1)puts("1");

        else puts("0");

    }

    return 0;

}

巴特西

三叉神经树 ( neuron )