ABC350 FG 题解
本人 Unrated 在开始后 1h 参加，20 分钟过 F，1h 过 G。
F
Overview
唐，史上最水 F。
Description
有一个串
S
S
S，包含大小写字母，( 和 )，保证括号匹配。
对于每组匹配括号，从里往外翻转、改变大小写。
比如 ((A)y)x，可以先变成 (ay)x，再变成 YAx。
求最终的 S S S。
Solution
首先确定每个字母的大小写再分治翻转就行了。
类似中缀表达式的求解过程。
O ( n log n ) O(n\log n) O(nlogn)。
Code
void solve(int ll, int r){
if(layer[r] & 1){
int i = r;
while(i >= ll){
if(s[i] == ')'){
solve(lst[i] + 1, i - 1), i = lst[i] - 1;
}
else cout << s[i], i--;
}
}
else{
int i = ll;
while(i <= r){
if(s[i] == '('){
solve(i + 1, nxt[i] - 1), i = nxt[i] + 1;
}
else cout << s[i], i++;
}
}
}
void solve(int testcase, ...){
init_vars();
cin >> s;
stack<int> st;
for(int i = 0; i < s.length(); i++){
if(i) layer[i] = layer[i - 1];
if(s[i] == '(') st.push(i), layer[i]++;
else if(s[i] == ')'){
nxt[st.top()] = i, lst[i] = st.top(), st.pop(); layer[i]--;
}
else{
if(layer[i] & 1){
if(s[i] >= 'a') s[i] = s[i] - 'a' + 'A';
else s[i] = s[i] - 'A' + 'a';
}
}
}
solve(0, s.length() - 1);
}
G
Overview
唐，史上最水 G。
Description
给出 n n n 个点， m m m 个操作， q q q 个操作如下：
1 x y加边操作；2 x y求 z z z，满足存在 ( x , z ) (x,z) (x,z) 和 ( y , z ) (y,z) (y,z)，没有输出0。
保证操作后的图是一个森林。
Solution
如果记录每个点的父亲 f x f_x fx，那么可以通过以下方法查询：
- 如果 z z z 是两个点的共同父亲，那么 f x = f y = z f_x=f_y=z fx=fy=z；
- 如果 z z z 是两个点的中间层，令 x x x 为更深的点，那么 f f x = y f_{f_x}=y ffx=y，答案为 f x f_x fx。
合并操作需要更新至少一个子树的 f f f，用启发式合并（按秩合并）即可。
O ( n log n ) O(n\log n) O(nlogn)。
题外话：原来的程序 TLE，本人通过计算理论复杂度和实际计算次数算出了问题。
Code
void dfs(int u, int fat){
// cout << u << " " << fat << endl;
// tott++;
fa1[u] = fat;
for(auto v : gv[u]){
if(v == fat) continue;
dfs(v, u);
}
}
int FindFather(int x){
if(fa[x] == x) return x;
return fa[x] = FindFather(fa[x]);
}
void Union(int u, int v){
u = FindFather(u), v = FindFather(v);
if(u == v) return;
sz[u] += sz[v];
fa[v] = u;
}
void solve(int testcase, ...){
init_vars();
int n, q; scanf("%lld%lld", &n, &q);
for(int i = 1; i <= n; i++) fa[i] = i, fa1[i] = 0, sz[i] = 1;
int tot = 0, lst = 0;
for(int i = 1; i <= q; i++){
int a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
a = 1 + (((a * (1 + lst)) % 998244353) % 2);
b = 1 + (((b * (1 + lst)) % 998244353) % n);
c = 1 + (((c * (1 + lst)) % 998244353) % n);
// cout << a << " " << b << " " << c << endl;
if(a == 1){
if(sz[FindFather(b)] > sz[FindFather(c)]) swap(b, c);
// cout << b << " " << c << endl;
tott = 0;
dfs(b, c);
// cout << tott << " " << sz[b] << endl;
Union(c, b);
gv[b].push_back(c);
gv[c].push_back(b);
}
else{
// for(int j = 1; j <= n; j++) cout << sz[FindFather(j)] << " ";
// cout << endl;
if(fa1[fa1[b]] == c) lst = fa1[b], printf("%lld\n", fa1[b]);
else if(fa1[fa1[c]] == b) lst = fa1[c], printf("%lld\n", fa1[c]);
else if(fa1[b] == fa1[c] && fa1[b]) lst = fa1[b], printf("%lld\n", fa1[b]);
else lst = 0, printf("0\n");
tot++;
}
// if(tott > 30000000) return;
}
}
