# Nemlit 的博客

By a konjac

### 题解 P4899 【[IOI2018] werewolf 狼人】

posted on 2019-10-14 21:27:21 | under 题解 |

## $Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define Next(i, u) for(re int i = head[u]; i; i = e[i].next)
#define _ 400005
int n, m, fa[_], q, fr[_], to[_], head[_], cnt, gg[_], size[_ * 15], ls[_ * 15], rs[_ * 15], gk, rt[_];
struct Edge { int v, next; }e[_ << 1];
struct edge { int u, v, w; }E[_];
il bool cmp(edge a, edge b) { return a.w < b.w; }
il int find(int x) {
while(x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
struct Tree {
int L[_], R[_], pax, dfn[_], val[_], f[21][_];
il void dfs(int u) {
if(u <= n) L[u] = ++ pax, dfn[pax] = u, val[u] = u;
else L[u] = pax + 1;
rep(i, 1, 20) f[i][u] = f[i - 1][f[i - 1][u]];
Next(i, u) f[0][e[i].v] = u, dfs(e[i].v);
R[u] = pax;
}
il int find_pre(int x, int y) {
drep(i, 0, 20) if(val[f[i][x]] >= y && f[i][x]) x = f[i][x];
return x;
}
il int find_nxt(int x, int y) {
drep(i, 0, 20) if(val[f[i][x]] <= y && f[i][x]) x = f[i][x];
return x;
}
}t1, t2;//重构树中用倍增找到我们需要的最高点
il void solve(Tree&t, int opt) {
rep(i, 1, n * 2) fa[i] = i;
int tot = n;
rep(i, 1, m) {
if(opt == 1) E[i] = (edge){fr[i], to[i], -min(fr[i], to[i])};
if(opt == 2) E[i] = (edge){fr[i], to[i], max(fr[i], to[i])};
}
sort(E + 1, E + m + 1, cmp);
rep(i, 1, m) {
int u = E[i].u, v = E[i].v, a = find(u), b = find(v);
if(a != b) fa[a] = fa[b] = ++ tot, t.val[tot] = abs(E[i].w), add(tot, a), add(tot, b);
}
t.dfs(tot);
}//构建重构树
il void insert(int &k, int kk, int l, int r, int ll) {
if(!k) k = ++ gk; size[k] = size[kk] + 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(ll <= mid) insert(ls[k], ls[kk], l, mid, ll), rs[k] = rs[kk];
else insert(rs[k], rs[kk], mid + 1, r, ll), ls[k] = ls[kk];
}
il int query(int k, int kk, int l, int r, int ll, int rr) {
if(ll <= l && r <= rr) return size[kk] - size[k];
int mid = (l + r) >> 1, ans = 0;
if(ll <= mid) ans += query(ls[k], ls[kk], l, mid, ll, rr);
if(mid < rr) ans += query(rs[k], rs[kk], mid + 1, r, ll, rr);
return ans;
}//主席树求交
int main() {
}