题目描述
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做 SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。 SHOI 组织由若干个 SHOI 细胞构成，SHOI 细胞之间形成严密的树形结构。
每个 SHOI 细胞都有且只有一个输出端，被称为轴突，除了一个特殊的、被称为根细胞的 SHOI 细胞的输出作为整个组织的输出以外，其余细胞的轴突均连向其上级 SHOI 细胞；并且有且只有三个接收端，被称为树突，从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单，仅有 0 和 1 两种。每个 SHOI 细胞根据三个输入端中 0 和 1 信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息，以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
输入格式
第一行一个整数 n，表示 SHOI 组织的总细胞个数。SHOI 细胞由 1\sim n 编号，编号为 1 的是根细胞。
从第二行开始的 n 行，每行三个整数 x_1, x_2, x_3，分别表示编号为 1 \sim 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.
首先先看10分怎么做
就是暴力O(n)修改O(1)查询
每次向上修改直到不能修改为止
那么我们需要增加查询的时间 减少修改的时间
所以想到树剖+线段树
查询的时候单点查询O(\log n)
然后要看修改
我们只考虑从0改成1的情况 (另一种是一样的)
记录下每个节点的num表示当前节点的三个儿子的1的数量
这样就是从当前节点往上一直找 直到到达根或者到达一个节点的num不是1(这时候这个节点的值不变, 再往上就没有影响了)
所以我们维护一个节点的信息的时候 记录下: 当前节点是0/1, num, 从当前节点对应区间的左端点开始连续的1的长度len1, 从当前节点对应区间的左端点开始连续的2的长度len2
这样 修改的复杂度是O(\log^2 n)
按照道理这应该是30分 但是正解好像就是这个...
那你这个30分的部分分是干什么用的?...
网友评论