1. IOI2018 - 狼人 / werewolf [省选/NOI-]
题意简述：多次询问求是否存在一条 \(s\to t\) 的路径 \(a_1,a_2,...,a_k\) 和路径上一个点 \(a_i\) 使 \(a_1,...,a_i\in[L,n]\) 且 \(a_i,...,a_k\in[1,R]\)。
首先求出两棵 kruskal 重构树：
- 第一棵树边权值设为 \(\min(u,v)\)，由大到小插入每一条边，树上点权设为子树内点权 \(\min\)，则可通过倍增跳树的方式求得每个点经过 \(\geq L\) 的点能到达的点集合（一个子树内所有叶子）；
- 第二棵树边权值设为 \(\max(u,v)\)，由小到大插入每一条边，树上点权设为子树内点权 \(\max\)。
因为一个子树内所有叶子是 dfn 序上一段连续区间，dfn 序又是一个排列，问题转化为了两个排列 \(a,b\)，求 \(a_{[l,r]},b_{[p,q]}\) 是否有交。
设 \(a^{-1}_i\) 表示 \(i\) 在 \(a\) 中的出现位置，若有交则等价于存在 \(x\in[p,q]\) 使 \(a^{-1}_{b_x}\in{[l,r]}\)。设排列 \(c_i=a^{-1}_{b_i}\)，则等价于 \(c_{[p,q]}\) 中存在值域 \(\in [l,r]\) 的数。
考虑使用主席树维护 \(c\)。每次询问查询 \(c_{[1,q]},c_{[1,p-1]}\) 中值域 \(\in[l,r]\) 的数的个数。若二者不等则答案为 \(1\)，否则为 \(0\)。
点击查看代码
const int N = 4e5 + 10;
int n, m, Q, fa[N], anti[N], c[N];
int ancmin[N][20], lenmin[N], ancmax[N][20], lenmax[N];
int dfnmin[N], dfnmax[N], mnmin[N], mxmin[N], mnmax[N], mxmax[N];
pair<int, int> emin[N], emax[N];
vector<int> gmin[N], gmax[N];
bool cmpmin(pair<int, int> x, pair<int, int> y){
return min(x.first, x.second) > min(y.first, y.second);
}
bool cmpmax(pair<int, int> x, pair<int, int> y){
return max(x.first, x.second) < max(y.first, y.second);
}
int gf(int x){
return x == fa[x] ? x : fa[x] = gf(fa[x]);
}
void dfsmin(int x){
if(x <= n){
++ *dfnmin;
dfnmin[*dfnmin] = x;
mnmin[x] = mxmin[x] = *dfnmin;
return;
}
mnmin[x] = 1e9;
for(int i : gmin[x]){
dfsmin(i);
mnmin[x] = min(mnmin[i], mnmin[x]);
mxmin[x] = max(mxmin[i], mxmin[x]);
}
}
void dfsmax(int x){
if(x <= n){
++ *dfnmax;
dfnmax[*dfnmax] = x;
mnmax[x] = mxmax[x] = *dfnmax;
return;
}
mnmax[x] = 1e9;
for(int i : gmax[x]){
dfsmax(i);
mnmax[x] = min(mnmax[i], mnmax[x]);
mxmax[x] = max(mxmax[i], mxmax[x]);
}
}
int jmpmin(int x, int val){
for(int i = 19; i >= 0; -- i){
if(lenmin[ancmin[x][i]] >= val){
x = ancmin[x][i];
}
}
return x;
}
int jmpmax(int x, int val){
for(int i = 19; i >= 0; -- i){
if(lenmax[ancmax[x][i]] <= val){
x = ancmax[x][i];
}
}
return x;
}
int rt[N], t[N*40], cnt, ls[N*40], rs[N*40];
int add(int p, int l, int r, int x, int v){
++ cnt;
t[cnt] = t[p];
ls[cnt] = ls[p];
rs[cnt] = rs[p];
p = cnt;
if(l == r){
t[p] += v;
} else {
int mid = l + r >> 1;
if(x <= mid){
ls[p] = add(ls[p], l, mid, x, v);
} else {
rs[p] = add(rs[p], mid+1, r, x, v);
}
t[p] = t[ls[p]] + t[rs[p]];
}
return p;
}
int qry(int p, int l, int r, int ql, int qr){
if(!p || qr < l || r < ql){
return 0;
} else if(ql <= l && r <= qr){
return t[p];
} else {
int mid = l + r >> 1;
return qry(ls[p], l, mid, ql, qr)
+ qry(rs[p], mid+1, r, ql, qr);
}
}
vector<int> check_validity(
int N,
vector<int> X,
vector<int> Y,
vector<int> S,
vector<int> E,
vector<int> L,
vector<int> R) {
vector<int> ans;
n = N;
m = X.size();
Q = S.size();
for(int i = 1; i <= m; ++ i){
emin[i].first = X[i-1];
emin[i].second = Y[i-1];
++ emin[i].first;
++ emin[i].second;
emax[i] = emin[i];
}
sort(emin + 1, emin + m + 1, cmpmin);
iota(fa + 1, fa + n + n + 1, 1);
iota(lenmin + 1, lenmin + n + 1, 1);
int cnt = n;
for(int i = 1; i <= m; ++ i){
int x = gf(emin[i].first), y = gf(emin[i].second);
if(x != y){
fa[x] = fa[y] = ++ cnt;
gmin[cnt].push_back(x);
gmin[cnt].push_back(y);
ancmin[x][0] = ancmin[y][0] = cnt;
lenmin[cnt] = min(lenmin[x], lenmin[y]);
}
}
dfsmin(cnt);
for(int i = cnt; i >= 1; -- i){
for(int j = 1; j < 20; ++ j){
ancmin[i][j] = ancmin[ancmin[i][j-1]][j-1];
}
}
sort(emax + 1, emax + m + 1, cmpmax);
iota(fa + 1, fa + n + n + 1, 1);
memset(lenmax, 0x3f, sizeof(lenmax));
iota(lenmax + 1, lenmax + n + 1, 1);
cnt = n;
for(int i = 1; i <= m; ++ i){
int x = gf(emax[i].first), y = gf(emax[i].second);
if(x != y){
fa[x] = fa[y] = ++ cnt;
gmax[cnt].push_back(x);
gmax[cnt].push_back(y);
ancmax[x][0] = ancmax[y][0] = cnt;
lenmax[cnt] = max(lenmax[x], lenmax[y]);
}
}
dfsmax(cnt);
for(int i = cnt; i >= 1; -- i){
for(int j = 1; j < 20; ++ j){
ancmax[i][j] = ancmax[ancmax[i][j-1]][j-1];
}
}
for(int i = 1; i <= n; ++ i){
anti[dfnmin[i]] = i;
}
for(int i = 1; i <= n; ++ i){
c[i] = anti[dfnmax[i]];
rt[i] = add(rt[i-1], 1, n, c[i], 1);
}
for(int i = 0; i < Q; ++ i){
int st = S[i], ed = E[i], le = L[i], ri = R[i];
++ st;
++ ed;
++ le;
++ ri;
int x = jmpmin(st, le), y = jmpmax(ed, ri);
int l = mnmin[x], r = mxmin[x], p = mnmax[y], q = mxmax[y];
int v = qry(rt[q], 1, n, l, r) - qry(rt[p-1], 1, n, l, r);
if(v){
ans.push_back(1);
} else {
ans.push_back(0);
}
}
return ans;
}