jzoj6420 迷雾华光 （区间众数，树分块）

jzoj6420 迷雾华光 （区间众数，树分块）

题意

一棵树，每个点上有三个数。求一条路径上的众数以及其出现次数。
强制在线
n ≤ 8 × 1 0 4 , q ≤ 1 0 5 nleq8times 10^4,qleq10^5 n≤8×104,q≤105
时限：10s

吐槽

Infleaking：垃圾分块模板题，还硬生生加个3的常数

思路

• ilnil：众所周知，区间众数是个经典的分块问题。（我不知道.jpg）
• 小常识：括号序上 ( L e f t [ x ] , L e f t [ y ] ) (Left[x],Left[y]) (Left[x],Left[y])包含树上祖孙路径 ( x , y ) (x,y) (x,y)路径的点的左括号，以及其他一些点的左右括号。
• 离线：在括号序上做莫队， O ( n n ) O(nsqrt n) O(nn ​)
• 在线：经典的分块问题。
• 考虑分块上树。
• 有多种分块方法：

1. 每个点有 1 / n 1/sqrt n 1/n ​的概率变成关键点。
2. 每颗子树x若比块大小大，则“断掉”其到父亲的边，将x设为关键点。

以上两种操作都能期望每一块（被关键点隔开的连通块）直径不会超过 O ( n ) O(sqrt n) O(n ​)

• 预处理两个东西：每个关键点到根的路径上每一个数的出现次数还有两两关键点之间的答案。
• 找出路径(x,y)上的两个最远关键点。（如果没有就暴力好了）
• 由于答案只可能是散点或者预处理好的路径答案，因此散点直接加入询问即可。
• 写的时候细节有点多。

O ( q n ) O(qsqrt n) O(qn ​)

#include <bits/stdc++.h>
using namespace std;
const int N = 8e4 + 10, BLOCK_SIZE = 300, KEY_NODE_CNT = N / BLOCK_SIZE * 2;
int py,n,a[N][3],xorsum;
int final[N],nex[N*2],to[N*2],tot;
void link(int x, int y) {to[++tot] = y, nex[tot] = final[x], final[x] = tot;
}int g[N][18], dep[N];
vector<int> key;
int pre[KEY_NODE_CNT][N],sz[N];
int dfn[N], stm, R[N];void dfs(int x) {dfn[x] = ++ stm;dep[x]=dep[g[x][0]]+1;for(int i=1;i<17;i++)g[x][i]=g[g[x][i - 1]][i - 1];for(int i = final[x]; i; i = nex[i]) {int y = to[i];if (y != g[x][0]) {g[y][0] = x;dfs(y);sz[x] += sz[y];}}sz[x]++;if(sz[x] >= BLOCK_SIZE){key.push_back(x);sz[x]=0;}R[x] = stm;
}int lca(int x, int y) {if(dep[x]<dep[y])swap(x,y);for(int i=17;~i;i--)if(dep[g[x][i]]>=dep[y])x=g[x][i];if(x==y)return x;for(int i=17;~i;i--)if(g[x][i]!=g[y][i])x=g[x][i],y=g[y][i];return g[x][0];
}int no[N],kfa[N],d[N],keycnt[N];
pair<int,int> cnt[N], now;
pair<int,int> pro[KEY_NODE_CNT][KEY_NODE_CNT];void init(int x, int neark) {for(int i = 0; i < 3; i++) d[a[x][i]]++;if(no[x] != 0){memcpy(pre[no[x]], d, sizeof d);neark = x;}kfa[x] = neark;keycnt[x] = keycnt[g[x][0]] + (no[x] != 0);for(int i = final[x]; i; i = nex[i]) {int y = to[i]; if (y != g[x][0]) {init(y, neark);}}for(int i = 0; i < 3; i++) d[a[x][i]]--;
}int ori;
void calc(int x, int from) {pair<int,int> las_ans = now;for(int i : a[x]) {cnt[i].first++;if(cnt[i] > now) now=cnt[i];}if (no[x] != 0) {pro[ori][no[x]] = now;}for(int i = final[x]; i; i = nex[i]) {int y = to[i]; if (y != from) {calc(y, x);}}for(int i : a[x]) cnt[i].first--;now = las_ans;
}pair<int,int> brute_force(int u, int v) {pair<int,int> ans = make_pair(0, 0);int e = lca(u,v);for(int i : a[e]) {cnt[i].first++;if (cnt[i] > ans) ans = cnt[i];}for(int z = u; z != e; z = g[z][0]) {for(int i : a[z]) {cnt[i].first++;if (cnt[i] > ans) ans = cnt[i];}}for(int z = v; z != e; z = g[z][0]) {for(int i : a[z]) {cnt[i].first++;if (cnt[i] > ans) ans = cnt[i];}}for(int i : a[e]) cnt[i].first--;for(int z = u; z != e; z = g[z][0]) {for(int i : a[z]) cnt[i].first--;}for(int z = v; z != e; z = g[z][0]) {for(int i : a[z]) cnt[i].first--;}return ans;
}int jump(int st, int up) {for(int i = 17; ~i; i--) if (keycnt[g[st][i]] - keycnt[up] > 0) {st = g[st][i];}return st;
}int query(int u, int g, int v, int w) {int ret = pre[no[u]][w] + pre[no[v]][w] - 2 * pre[no[g]][w];for(int i : a[g]) ret += i == w;return ret;
}
vector<int> todel;int main() {freopen("mode.in","r",stdin);freopen("mode.out","w",stdout);	cin>>py>>n;for(int i=1;i<=n;i++){scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);}for(int i=1;i<n;i++){int u,v;scanf("%d %d",&u,&v);link(u,v),link(v,u);}dfs(1);key.push_back(1);int tmp = key.size();for(int i = 0; i < tmp; i++) {for(int j = i + 1; j < tmp; j++) {key.push_back(lca(key[i], key[j]));}}sort(key.begin(), d());size(unique(key.begin(), d()) - key.begin());for(int i = 0; i < key.size(); i++) {no[key[i]] = i + 1;}init(1,0);for(int i = 1; i <= n; i++) cnt[i].second = -i;for(int x : key) ori = no[x], calc(x, 0);int q; cin >> q;for(int i = 1; i <= q; i++) {int u,v; scanf("%d %d",&u,&v);if (py) u^=xorsum, v^=xorsum;pair<int,int> ans = make_pair(0,0);int e = lca(u, v);if (keycnt[u] + keycnt[v] - 2 * keycnt[e] + (no[e] != 0) < 2) {ans = brute_force(u, v);} else {if (dfn[u] > dfn[v]) swap(u, v);int x = 0, y = 0;//u-x-y-vint flagu = 0, flagv = 0;if (keycnt[u] != keycnt[e]) x = kfa[u];else x = jump(v, e), flagu = 1;if (keycnt[v] != keycnt[e]) y = kfa[v];else y = jump(u, e), flagv = 1;todel.clear();ans = pro[no[x]][no[y]];int ee = lca(x, y);for(int z = u; z != e && z != x; z = g[z][0]) {todel.push_back(z);for(int i : a[z]) {cnt[i].first++;pair<int,int> fact = cnt[i];fact.first += query(x, ee, y, i);if (fact > ans) ans = fact;}}for(int z = v; z != e && z != y; z = g[z][0]) {todel.push_back(z);for(int i : a[z]) {cnt[i].first++;pair<int,int> fact = cnt[i];fact.first += query(x, ee, y, i);if (fact > ans) ans = fact;}}if (flagu) {for(int z = g[x][0]; z != g[e][0]; z = g[z][0]) {todel.push_back(z);for(int i : a[z]) {cnt[i].first++;pair<int,int> fact = cnt[i];fact.first += query(x, ee, y, i);if (fact > ans) ans = fact;}}}if (flagv) {for(int z = g[y][0]; z != g[e][0]; z = g[z][0]) {todel.push_back(z);for(int i : a[z]) {cnt[i].first++;pair<int,int> fact = cnt[i];fact.first += query(x, ee, y, i);if (fact > ans) ans = fact;}}}for(int z : todel) {for(int i : a[z]) cnt[i].first--;}}xorsum ^= ans.first ^ -ans.second;printf("%d %dn", ans.first, -ans.second);}
}