题解：P13308 故障

视频讲解。

题意

给定一个树，进行以下两种操作，删边修改和查询联通块大小。

思路

这道题其实很好写，因为它给的性质非常好。由于题目给的树是一个大小为 \(2^n-1\) 的满二叉树，那么深度就是 \(O(n)\) 级别的，所以我们考虑暴力修改。

先来考虑查询操作，我们先记录以每个结点为根的子树大小，若一个结点 \(u\) 为根形成的子树深度为 \(d\)，且内部没有进行任何修改，那么这就是一个满二叉树，大小为 \(2^d-1\)。而 \(d\) 可以由结点 \(u\) 在原树中的深度与 \(n\) 做差得到，随后就可以写出以下代码：

inline int dep(int u) { // 求深度 int h = 0;while(u) {h ++ , u >>= 1;}return h;
}
inline int gets(int u) { // 求以 u 为根的满二叉树大小 return (1ll << (n - dep(u) + 1)) - 1;
}

由于树的结点数高达 \(2^{60}-1\)，无法直接存储完整结构，可以用一个映射表 \(mp\) 来记录有效数据。对于每个修改操作，只有修改对象自身不是根，就会形成一个新的根，这里同样用一个映射表 \(now\) 来记录。

每个结点记录的信息是以该结点为根的子树大小，那么查询联通块大小就是找到这个联通块的根，\(n\) 的范围很小，所以暴力往上跳即可。就可以写出以下代码：

inline int query(int u) { // 处理查询 while(now.find(u) == now.end()) u >>= 1; // 找到根 if(!mp[u]) return mp[u] = gets(u); // 如果根未初始化值，默认为满二叉树 return mp[u]; 
}

接下来想修改操作。

删掉结点 \(u\) 与其父亲结点相连的边，就会形成一个新的根，构成一个以 \(u\) 为结点的子树。同时，对于 \(u\) 在删边前的所有直系父结点，其记录的子树大小都会减去子树 \(u\) 的结点数。所以这里可以像查询一样，暴力往上跳，对其所有直系父结点做贡献，如果其未初始化，赋予满二叉树的结点数然后再算贡献，反之直接做减法。注意还要对根结点算贡献。

于是就写出了以下代码：

void change(int u , int val) { // 修改操作 while(now.find(u) == now.end()) { // 遍历结点 u 的所以直系父结点 if(!mp[u]) mp[u] = gets(u) - val; // 未初始化值，默认为满二叉树，然后算贡献 else mp[u] -= val; // 否则直接算贡献 u >>= 1; // 继续向上跳 }if(!mp[u]) mp[u] = gets(u) - val; // 对根结点算贡献 else mp[u] -= val;
}

然后就似乎写完了，一交：70 分。

三个点超时了。

分析一下时间复杂度吧。树的深度为 \(O(n)\)，\(n\) 最大可达 \(60\)。查询操作是暴力往上跳，跳的次数自然是 \(O(n)\) 的，但是判断每个结点是否为根需要调用映射表 now，其复杂度跟目前根的数量有关，因此是 \(O(\log_2 m)\)。

综上，单次查询的时间复杂度是 \(O(n\log_2m)\) 的。

然后看修改，同样是暴力往上跳，自然也有一个 \(O(n)\)，也要判根结点，也有一个 \(O(\log_2 m)\)。

但不同的是，修改操作需要修改结点信息，需要调用储存子树大小的映射表 \(mp\)，接下来分析一下它的复杂度。对于每次修改，会往 \(mp\) 内新增 \(O(n)\) 个元素，共 \(O(m)\) 次操作，所以 \(mp\) 内的元素数量是 \(O(nm)\) 级别的，复杂度为 \(O(\log_2{nm})\)。当结点未初始化，还需要计算子树大小，涉及到深度的计算，耗时 \(O(n)\)。

综上，单次修改操作的时间复杂度为：

\[O(n)\times(O(\log_2 m)+O(\log_2{nm}) + O(n))=O(n\log_2{nm}) \]

代入极限数据计算得：

\[60\times\log_2{(60\times3\times10^5)}=360\times25=1500 \]

修改操作的复杂度太大了，即使跑不满也依旧会炸。

考虑优化修改。不难发现，每次查询只需要访问根结点存储的值，所以只需要对会成为根结点的结点算贡献，再开一个映射表 \(s\) 提前记录所有根结点即可。那么记录子树大小的映射表 \(mp\) 内的元素个数就降到了 \(O(m)\) 级别，单次修改的时间复杂度就成功降到了 \(O(n\log_2{m})\)。

以上就是将算法的时间复杂度从 \(O(nm\log_2{nm})\) 优化到 \(O(nm\log_2{m})\) 的全过程，接下来讲卡常。

按以上思路优化完的代码一交：80 分，不吸氧有 90 分。但可以发现，超时的两个点都接近 AC 的边缘！这个时候我们只需要浅浅地优化一下常数就可以过了。

我们的代码有什么问题？我们滥用了 STL！上述思路共用了三个映射表，分别为记录根的 \(now\)、是否可以成为根的 \(s\) 以及结点信息 \(mp\)。

那么就只需要用别的技巧替换掉调用次数最多的那个就行了。不难发现，调用次数最多的，不是 \(mp\)，而是 \(s\)。而 \(s\) 又是提前预处理出来的，因此可以用离散化替代，对所有进行修改操作的结点记录下来，并排序去重，通过二分查找判断结点是否存在于序列中，从而起到与 \(s\) 等效且常数更小的复杂度。

优化后的代码：

inline void change(int u , int val) { // 修改操作 while(now.find(u) == now.end()) { // 遍历结点 u 的所以直系父结点 if(b[lower_bound(b + 1 , b + tot + 1 , u) - b] == u) { // 如果该结点之后会成为根 if(!mp[u]) mp[u] = gets(u) - val; // 未初始化值，默认为满二叉树，然后算贡献 else mp[u] -= val; // 否则直接算贡献 }u >>= 1; // 继续向上跳 }if(!mp[u]) mp[u] = gets(u) - val; // 对根结点算贡献 else mp[u] -= val;
}

优化后的代码就可以轻松的通过本题：100 分。

代码

#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e5 + 5;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc() {static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
set<int> now; // 记录所有连通块的根 
int b[N] , tot; // 离散化数组 
unordered_map<int , int>mp; // 哈希表储存每个结点以其为根的子树大小 
int n , m;
inline int dep(int u) { // 求深度 int h = 0;while(u) {h ++ , u >>= 1;}return h;
}
inline int gets(int u) { // 求以 u 为根的满二叉树大小 return (1ll << (n - dep(u) + 1)) - 1;
}
inline void change(int u , int val) { // 修改操作 while(now.find(u) == now.end()) { // 遍历结点 u 的所以直系父结点 if(b[lower_bound(b + 1 , b + tot + 1 , u) - b] == u) { // 如果该结点之后会成为根 if(!mp[u]) mp[u] = gets(u) - val; // 未初始化值，默认为满二叉树，然后算贡献 else mp[u] -= val; // 否则直接算贡献 }u >>= 1; // 继续向上跳 }if(!mp[u]) mp[u] = gets(u) - val; // 对根结点算贡献 else mp[u] -= val;
}
inline int query(int u) { // 处理查询 while(now.find(u) == now.end()) u >>= 1; // 找到根 if(!mp[u]) return mp[u] = gets(u); // 如果根未初始化值，默认为满二叉树 return mp[u]; 
}
int op[N] , u[N]; 
signed main() {//cin_fast;int ans = 0;in(n) , in(m);now.insert(1); // 初始化根结点1 mp[1] = gets(1);for(int i = 1 ; i <= m ; i ++) {in(op[i]) , in(u[i]);if(op[i] == 1)b[++ tot] = u[i]; // 对于操作 1 的 u 离线记录下来 }sort(b + 1 , b + tot + 1) , tot = unique(b + 1 , b + tot + 1) - b - 1; // 离散化 for(int i = 1 ; i <= m ; i ++) { if(op[i] == 1) {if(now.find(u[i]) != now.end()) continue; // 如果该结点已经是根，直接跳过 now.insert(u[i]); // 标记结点 u 为根 if(!mp[u[i]]) change(u[i] >> 1 , gets(u[i])); // 进行修改操作 else change(u[i] >> 1 , mp[u[i]]);} else {ans ^= query(u[i]); // 进行查询操作 }}cout<<ans<<'\n';I_love_Foccarus 0;
}