计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI 细胞;并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 \(0\)和 \(1\)两种。每个 SHOI 细胞根据三个输入端中 \(0\)和 \(1\)信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
输入的第一行包含一个整数 \(n\)。表示 SHOI 组织的总细胞个数。SHOI 细胞由 \(1\)~ \(n\) 编号,编号为 \(1\) 的是根细胞。
从第二行开始的 \(n\)行,每行三个整数 \(x_1, x_2, x_3\),分别表示编号为 \(1\)~ \(n\) 的 SHOI 细胞的树突连接。\(1 < x_i \leq n\) 表示连向编号为 \(x_i\) 的细胞的轴突, \(n < x_i \leq 3n+1\) 表示连向编号为 \(x_i\) 的外界输入。输入数据保证给出的 SHOI 组织是合法的,且所有的 \(x_i\) 两两不同。
接下来一行包含 \(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
1
0
0
1
1
对于 \(10 \%\)的数据, \(n \leq 1000, q \leq 1000\)。
对于 \(30 \%\)的数据, \(n \leq 100000, q \leq 100000\)。
对于 \(100 \%\)的数据, \(n \leq 500000, q \leq 500000\)。
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 5e5 + 3;
const int maxm = 1.5e6 + 3;
struct node {
node *ch[2], *fa, *n1, *n2;
int val, tag;
node(int val = 0, int tag = 0): val(val), tag(tag) {
ch[0] = ch[1] = fa = n1 = n2 = NULL;
}
void trn() { std::swap(n1, n2); val ^= 3; tag ^= 1; }
void dwn() {
if(!tag) return;
if(ch[0]) ch[0]->trn();
if(ch[1]) ch[1]->trn();
tag = 0;
}
void upd() {
n1 = n2 = NULL; //这行不能少!
//右根左这样找
if(ch[1]) n1 = ch[1]->n1;
if(!n1) n1 = this->val == 1? NULL : this;
if(ch[0] && !n1) n1 = ch[0]->n1;
if(ch[1]) n2 = ch[1]->n2;
if(!n2) n2 = this->val == 2? NULL : this;
if(ch[0] && !n2) n2 = ch[0]->n2;
}
bool isr() { return this == fa->ch[1]; }
bool ntr() { return fa && (fa->ch[1] == this || fa->ch[0] == this); }
}pool[maxn];
int fa[maxm], val[maxm], du[maxm];
int n, ans;
void toposort() {
std::queue<int> q;
for(int i = n + 1; i <= 3 * n + 1; i++) val[i] = in() << 1, q.push(i);
while(!q.empty()) {
int tp = q.front(); q.pop();
if(tp <= n) pool[tp].upd(), pool[tp].fa = pool + fa[tp];
pool[fa[tp]].val += (tp > n? val[tp] : pool[tp].val) >> 1;
du[fa[tp]]--;
if(!du[fa[tp]]) q.push(fa[tp]);
}
pool[1].fa = NULL;
}
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y->ntr()) z->ch[y->isr()] = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o) {
static node *st[maxn];
int top;
st[top = 1] = o;
while(st[top]->ntr()) st[top + 1] = st[top]->fa, top++;
while(top) st[top--]->dwn();
while(o->ntr()) {
if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
void access(node *x) {
for(node *y = NULL; x; x = (y = x)->fa)
splay(x), x->ch[1] = y, x->upd();
}
int main() {
n = in();
for(int i = 1; i <= n; i++) du[fa[in()] = fa[in()] = fa[in()] = i] = 3;
toposort();//求初始的答案
ans = pool[1].val >> 1;
int x, tp;
for(int T = in(); T --> 0;) {
tp = (val[x = in()] ^= 2) >> 1;
access(pool + (x = fa[x])), splay(pool + x);
node *o = pool + x;
node *nr = tp? o->n1 : o->n2; //找最深的点
if(nr) {
splay(nr);
if(nr->ch[1]) nr->ch[1]->trn(), nr->ch[1]->upd();
nr->val += tp? 1 : -1;
nr->upd();
}
else ans ^= 1, o->trn(), o->upd();
printf("%d\n", ans);
}
return 0;
}
原文:https://www.cnblogs.com/olinr/p/10391914.html