写在前面
把黑题看成蓝题结果想了老半天感觉不对劲
本题对于理解SplaySplaySplay和LCTLCTLCT结构具有至关重要的意义,值得反复思考。
可能因为我比较菜
题目思路
题目给定一个类似神经网络的东西,每个节点都具有激活层、三输入单输出,输出由输入的111的个数决定,111比000多就输出111。每次修改一个外界输入,要求求根节点的输出。
首先考虑一个问题,修改外界输入对上级节点输出的影响究竟有几种:
- 从叶子节点开始有一段连续的输入111的个数为111的节点
不难发现,此时如果将121212号节点修改为111,那么因此的改变到333号点(第一个非111点)终止,不会引起根节点的修改 - 同样,从叶子节点开始有一段连续的输入111个数为222的节点,此时叶节点的改变只会影响到第一个非222点
那么就可以解决这个问题了,对于每个修改的叶子节点,找到向上首个非111/非222节点(对应叶节点0→10 \rightarrow 10→1和1→01 \rightarrow 01→0)。
考虑使用LCT维护这个信息,对每个节点记录两个变量id1id_1id1和id2id_2id2,分别表示沿当前点向上的第一个非111/非222点。然后每次修改前Access(x)Access(x)Access(x)再Splay(x)Splay(x)Splay(x)就可以将信息上传到xxx待修改的xxx节点上。
但是注意,这里的xxx节点并不是输入的那个叶子节点,而是它的父亲节点,因为叶子节点没有输入只有输出,修改是没有意义的。
那么问题就来了,信息该怎样上传到xxx节点呢?我们回想LCTLCTLCT的三个关键操作:Rotate(x),Splay(x),Access(x)Rotate(x), Splay(x), Access(x)Rotate(x),Splay(x),Access(x),我们可以以上树为例来理解:
我们建树时全部连虚边(只连父不连子),然后执行Access(12)Access(12)Access(12),这时1∼121 \sim 121∼12的点全部位于一条实链上,然后我们将121212旋到根上,在这里需要注意,我们看一下Rotate()Rotate()Rotate()和Splay()Splay()Splay()两个函数:
void rotate(int x) {int y = f[x], z = f[y], k = get(x);if(!isRoot(y)) ch[z][ch[z][1] == y] = x;ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;ch[x][!k] = y, f[y] = x, f[x] = z;push_up(y); push_up(x);
}void update(int x) {if(!isRoot(x)) update(f[x]);push_down(x);
}void splay(int x) {update(x);for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]) {if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);}push_up(x);
}
每次RotateRotateRotate后,我们会先更新原先的父亲节点的信息,再更新当前节点的信息。那么在一路将121212旋到根的过程中,我们会将到根节点路径上的点旋到xxx的子树里,并将信息更新给正在旋转过程中的xxx。那么我们考虑如何能够找到我们需要的信息:向上首个非111/非222节点,那么这些信息一定存在于其父亲节点(此处的父亲节点指的是旋转前的父亲节点)的右子树(旋转后)(感性理解,xxx的左子树为深度严格小于xxx的节点,左子树首个节点的右子树在仍然满足深度严格小于xxx的同时深度继续增大),因此我们优先从右子树继承信息,当右子树没有信息时判断当前节点是否满足,否则才从左子节点继承信息(此时更新的一般是xxx节点本身,而不是其父亲节点)。
此外,本题细节比较多,要仔细写。
Code
#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;const int N = 3e6 + 10;int n = 0;namespace LCT{struct Info{short in, out;int id1, id2, add_tag;void activate() { out = (in >= 2); }}tree[N];int ch[N][2], f[N], tag[N];#define ls ch[x][0]#define rs ch[x][1]inline void push_reverse(int x) { swap(ls, rs), tag[x] ^= 1; }inline void push_add(int x, int c) {tree[x].in += c;tree[x].add_tag += c;tree[x].activate();swap(tree[x].id1, tree[x].id2);}inline void push_down(int x) {if(tag[x]) {if(ls) push_reverse(ls);if(rs) push_reverse(rs);tag[x] = 0;}if (tree[x].add_tag) {if(ls) push_add(ls, tree[x].add_tag);if(rs) push_add(rs, tree[x].add_tag);tree[x].add_tag = 0;}} inline void push_up(int x) {tree[x].id1 = tree[rs].id1;tree[x].id2 = tree[rs].id2;if(!tree[x].id1) {if(tree[x].in != 1) tree[x].id1 = x;else tree[x].id1 = tree[ls].id1;}if(!tree[x].id2) {if(tree[x].in != 2) tree[x].id2 = x;else tree[x].id2 = tree[ls].id2;}}#define get(x) (ch[f[x]][1] == x) #define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)void rotate(int x) {int y = f[x], z = f[y], k = get(x);if(!isRoot(y)) ch[z][ch[z][1] == y] = x;ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;ch[x][!k] = y, f[y] = x, f[x] = z;push_up(y); push_up(x);}void update(int x) {if(!isRoot(x)) update(f[x]);push_down(x);}void splay(int x) {update(x);for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]) {if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);}push_up(x);}int access(int x) {int p;for(p = 0; x; x = f[p = x]) splay(x), rs = p, push_up(x);return p;}void makeRoot(int x) { access(x), splay(x), push_reverse(x); }int findRoot(int x) {access(x), splay(x);while(ch[x][0]) push_down(x), x = ch[x][0];splay(x);return x;}void split(int x, int y) {makeRoot(x);access(y), splay(y);}void link(int x, int y) {makeRoot(x);if(findRoot(y) != x) f[x] = y;}void cut(int x, int y) {makeRoot(x);if(findRoot(y) == x && f[y] == x && !ch[y][0]) {f[y] = ch[x][1] = 0;push_up(x);}}
}using LCT::tree;vector<int> g[N];void dfs(int u) {for(auto v : g[u]) {dfs(v);tree[u].in += tree[v].out;}if(u <= n) tree[u].activate();// cout << "The output of node " << u << " is " << tree[u].out << endl;
}inline void solve(){cin >> n;for(int i = 1; i <= n; i++) {int x1, x2, x3; cin >> x1 >> x2 >> x3;g[i].emplace_back(x1), LCT::f[x1] = i;g[i].emplace_back(x2), LCT::f[x2] = i;g[i].emplace_back(x3), LCT::f[x3] = i;}for(int i = n + 1; i <= 3 * n + 1; i++) cin >> tree[i].out;dfs(1);int q, ans = tree[1].out; cin >> q;while(q--) {int x; cin >> x;int xfa = LCT::f[x];// cout << "Query of change : input x = " << x << ", father of x is " << xfa << endl; int add_val = (tree[x].out == 1) ? -1 : 1;LCT::access(xfa), LCT::splay(xfa);int split_node = (tree[x].out == 1) ? tree[xfa].id2 : tree[xfa].id1;// cout << "Deepest node of found : " << split_node << endl;// cout << "Add_val = " << add_val << endl; if(split_node) {LCT::splay(split_node);LCT::push_add(LCT::ch[split_node][1], add_val);// cout << "Tree[" << split_node << "].in origin value is " << tree[split_node].in << endl;tree[split_node].in += add_val;tree[split_node].activate();LCT::push_up(LCT::ch[split_node][1]);// cout << "Tree[" << split_node << "].in has been changed to " << tree[split_node].in << endl;// ans = tree[1].out;} else {LCT::push_add(xfa, add_val);LCT::push_up(xfa);ans ^= 1;}tree[x].out ^= 1;cout << ans << endl;}
}signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; // cin >> t;while(t--) solve();return 0;
}