震惊, 蒟蒻学树剖第二天就打题解
所以说, 理解之后树剖这种东西其实难度真心不大. 至少这种模板题都可以秒切的
这里推荐一个博客: 树剖详解 https://www.cnblogs.com/chinhhh/p/7965433.html
蒟蒻就是在这个博客上学到的
如果想看我自己写的总结, 请点 我的博客 https://www.cnblogs.com/DannyXu/p/12372291.html
这个链接 (虽然这个是写给自己看的, 理解难度应该不小)
树剖的方法在博客上都有了, 在这里不细讲, 专注讲一下这题的实现:
\(dfs\) 请使用博客上的方法, 这题需要做的只是照搬
首先, 我们可以发现, 这题跟普通的树剖基本上一样. 唯一的区别就是他要使用 \(xor\) . 那么, 我们发现, \(xor\) 的操作其实跟加减没有任何区别. 于是, 我们只需要将加减法换成 \(xor\), 这题的操作就实现了
1.update
update 跟正常的线段树 update 没有区别, 而且他不需要 lazy, 因为他只需要 update 一个点. 所以我们仍然是二分查找, 找到就二分, 然后他的父亲就更新为左儿子 \(xor\) 右儿子.
我们还可以观察到, 如果更新右儿子, 那么左儿子就不用更新了. 因此, 这个更新速度是恒定的 \(O(logn)\)
- void update(int way, int l, int r, int q, int val){
- if (q<l || q>r) return;// 不在范围内 (其实用处不大)
- if (l==r && r==q) {seg[way]=val;return;}// 刚好是这个数就更新
- if (l==r) return;// 否则不更新
- int mid = (l+r)/2;
- if (q<=mid)update(way*2,l,mid,q,val);// 在左儿子的区间
- if (q>mid)update(way*2+1,mid+1,r,q,val);// 在右儿子的区间
- seg[way] =seg[way*2]^seg[way*2+1];// 用儿子更新父亲
- }
- 2.query
这题的难点来了: 怎么拿路径
我们可以发现, 取两点之间的路径相当于分别取两点到他俩 \(lca\) 的值.
再观察, 我们发现, 在取 \(lca\) 途中答案可以直接更新, 因为去 lca 的路径只有一条, 所以, 我们每次 query 的时候先将答案设成 0, 每次网上跳区间的时候答案就是 \(ans^ 区间 \)
- int query_up(int way, int l, int r, int qlow, int qhigh){
- if (qlow<= l && r<=qhigh) return seg[way];// 完全包围
- if (l>qhigh || r<qlow) return 0;// 不在范围
- int mid = (l+r)/2;
- return (query_up(way*2,l,mid,qlow,qhigh) ^ query_up(way*2+1,mid+1,r,qlow,qhigh));// 左儿子 ^ 右儿子
- }
- int query(int x, int y){
- int ans = 0;// 设答案为 0
- while(top[x]!=top[y]){// 如果不在同一条链
- if (dep[top[x]]<dep[top[y]]) swap(x,y);// 谁高谁低
- ans ^= query_up(1,1,n,id[top[x]],id[x]);// 更新答案
- x = fat[top[x]];// 跳到上面那条链
- }
- if (dep[x]>dep[y]) swap(x,y);
- ans ^= query_up(1,1,n,id[x],id[y]);// 找本链的值
- return ans;
- }
完整代码:
- #include
- #include
- #include
- #include
- using namespace std;
- const int MAXN = 1e5+5;
- int res = 0;
- int n,m,r,p,dep[MAXN],fat[MAXN],son[MAXN],sz[MAXN],num[MAXN],id[MAXN],top[MAXN],wt[MAXN],cnt=0,head[MAXN],tot = 0;
- int seg[MAXN*4],lazy[MAXN*4];
- vector adj[MAXN];
- void dfs1(int pos, int f, int depth){
- dep[pos] = depth;
- fat[pos] = f;
- sz[pos] = 1;
- int maxi = -1;
- for (int v : adj[pos]){
- if (v == f) continue;
- dfs1(v,pos,depth+1);
- sz[pos]+=sz[v];
- if (maxi<sz[v]) {maxi = sz[v];son[pos] = v;}
- }
- }
- bool vis[MAXN];
- void dfs2(int pos, int top_pos){
- id[pos] = ++cnt;
- wt[cnt] = num[pos];
- top[pos] = top_pos;
- if (!son[pos]) return;
- dfs2(son[pos],top_pos);
- for (int v : adj[pos]){
- if (v==fat[pos] || v==son[pos]) continue;
- dfs2(v,v);
- }
- }// 树剖的基础 dfs
- void make_tree(int way, int l, int r){
- if (l==r) {seg[way] = wt[l];return;}
- int mid = (l+r)/2;
- make_tree(way*2,l,mid);
- make_tree(way*2+1,mid+1,r);
- seg[way] = seg[way*2] ^seg[way*2+1] ;
- }// 建树
- void update(int way, int l, int r, int q, int val){
- if (q<l || q>r) return;
- if (l==r && r==q) {seg[way]=val;return;}
- if (l==r) return;
- int mid = (l+r)/2;
- if (q<=mid)update(way*2,l,mid,q,val);
- if (q>mid)update(way*2+1,mid+1,r,q,val);
- seg[way] =seg[way*2]^seg[way*2+1];
- }// 更新
- int query_up(int way, int l, int r, int qlow, int qhigh){
- if (qlow<= l && r<=qhigh) return seg[way];
- if (l>qhigh || r<qlow) return 0;
- int mid = (l+r)/2;
- return (query_up(way*2,l,mid,qlow,qhigh) ^ query_up(way*2+1,mid+1,r,qlow,qhigh));
- }// 求区间
- int query(int x, int y){
- int ans = 0;
- while(top[x]!=top[y]){
- if (dep[top[x]]<dep[top[y]]) swap(x,y);
- ans ^= query_up(1,1,n,id[top[x]],id[x]);
- x = fat[top[x]];
- }
- if (dep[x]>dep[y]) swap(x,y);
- ans ^= query_up(1,1,n,id[x],id[y]);
- return ans;
- }// 求链
- int main(){
- cin>> n>> m;
- for (int i=1;i<=n;i++) cin>> num[i];
- for (int i=0;i<n-1;i++){
- int a,b; cin>> a>> b;
- adj[a].push_back(b);
- adj[b].push_back(a);
- }
- dfs1(1,0,1);
- dfs2(1,1);
- make_tree(1,1,n);
- // 初始化
- for (int i=0;i<m;i++){
- int ind,a,b; cin>> ind>> a>> b;
- if (ind==1){
- update(1,1,n,id[a],b);
- }else{
- cout << query(a,b) << endl;
- }// 操作
- }
- }
复杂度 \(O(nlog^2n)\) 可以过
做完建议去做 P3384, 本蒟蒻就是做了那题才恍然大悟的
来源: http://www.bubuko.com/infodetail-3439090.html