题解：P14380 【MX-S9-T3】「LAOI-16」天外来物
WorldMachine
·
·
题解
小清新数据结构题。
首先想到类似支配对的东西：称区间 [l,r] 是极小的，如果 f(l,r)\neq f(l+1,r) 且 f(l,r)\neq f(l,r-1)。
那么答案就是 [L,R] 内的极小子区间 [l,r] 的数量。
极小区间的数量是 \mathcal O(N^2) 的（星形图），意味着必须要找一些好的充要条件刻画之。
不难看出，[l,r] 是极小的，当且仅当 l,r 在 f(l,r) 上都是叶子，并且「l 成为叶子」是对 r 单调的，r 同理。
因此设 \text{pre}_i 表示最小的 x\le i，使得 i 在 f(x,i) 上是叶子，\text{suf}_i 同理。
那么 [l,r] 极小等价于 \text{pre}_r\le l\land\text{suf}_l\ge r。
考虑如何求 \text{pre}_i。i 不是叶子，意味着 f(x,i) 和删去 i 得到的至少 2 个连通块有交。
因此 $i$ 从小到大扫描线，用线段树维护单点修改、区间最值，查询时获取每个子树（含父亲方向）内的最大值，取所有子树的次大值即可。$\text{suf}_i$ 同理。
考虑如何回答询问。$l$ 从右往左扫描线，如果不考虑 $\text{pre}_r\ge l$ 的限制，就是 $[l,\text{suf}_l]$ 内的 $r$ 加 $1$。查询区间和。
$\text{pre}_r$ 的限制意味着 $r$ 会逐渐失效，再维护 $d_r$ 表示 $r$ 是否仍有效，在 $l$ 处把 $\text{pre}_r<l$ 的 $r$ 的 $d_r$ 置零，线段树维护的改为区间加 $d_r$ 即可。
时间复杂度 $\mathcal O(n\log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5, S = 1 << 20; char buf[S], *p1, *p2;
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
inline void rd(int &x) { x = 0; char c = 0; while (c < '0' || c > '9') c = gc; while (c >= '0' && c <= '9') x = x * 10 - '0' + c, c = gc; }
int n, q, fa[N], tot, dfn[N], mxd[N], pre[N], suf[N], qr[N]; ll ans[N];
basic_string<int> G[N], qv[N], dl[N];
void dfs(int u) {
dfn[u] = ++tot;
for (int v : G[u]) if (v ^ fa[u]) fa[v] = u, dfs(v);
mxd[u] = tot;
}
#define lc (p << 1)
#define rc (lc | 1)
struct Seg_max {
int op, t[N << 2];
void init(int p, int l, int r, int v) {
t[p] = v; if (l == r) return; int mid = (l + r) >> 1;
init(lc, l, mid, v), init(rc, mid + 1, r, v);
}
void upd(int p, int l, int r, int x, int v) {
if (l == r) return void(t[p] = v); int mid = (l + r) >> 1;
x <= mid ? upd(lc, l, mid, x, v) : upd(rc, mid + 1, r, x, v);
t[p] = op > 0 ? max(t[lc], t[rc]) : min(t[lc], t[rc]);
}
int qry(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[p]; int mid = (l + r) >> 1;
if (R <= mid) return qry(lc, l, mid, L, R);
if (L > mid) return qry(rc, mid + 1, r, L, R);
int ql = qry(lc, l, mid, L, R), qr = qry(rc, mid + 1, r, L, R);
return op > 0 ? max(ql, qr) : min(ql, qr);
}
} t;
struct Seg_add {
ll t[N << 2]; int d[N << 2], tg[N << 2];
void init(int p, int l, int r) {
if (l == r) return void(d[p] = 1); int mid = (l + r) >> 1;
init(lc, l, mid), init(rc, mid + 1, r), d[p] = d[lc] + d[rc];
}
void mdf(int p, ll x) { t[p] += d[p] * x, tg[p] += x; }
void psd(int p) { if (tg[p]) mdf(lc, tg[p]), mdf(rc, tg[p]), tg[p] = 0; }
void del(int p, int l, int r, int x) {
if (l == r) return void(d[p] = 0); int mid = (l + r) >> 1; psd(p);
x <= mid ? del(lc, l, mid, x) : del(rc, mid + 1, r, x), d[p] = d[lc] + d[rc];
}
void upd(int p, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) return mdf(p, x);
int mid = (l + r) >> 1; psd(p);
if (L <= mid) upd(lc, l, mid, L, R, x);
if (R > mid) upd(rc, mid + 1, r, L, R, x);
t[p] = t[lc] + t[rc];
}
ll qry(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[p];
int mid = (l + r) >> 1; ll ret = 0; psd(p);
if (L <= mid) ret += qry(lc, l, mid, L, R);
if (R > mid) ret += qry(rc, mid + 1, r, L, R);
return ret;
}
} s;
int main() {
// freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);
rd(n), rd(q);
for (int i = 1, u, v; i < n; i++) rd(u), rd(v), G[u] += v, G[v] += u;
dfs(1), t.op = 1;
for (int i = 1; i <= n; i++) {
t.upd(1, 1, n, dfn[i], i); basic_string<int> val;
for (int v : G[i]) if (v ^ fa[i]) val += t.qry(1, 1, n, dfn[v], mxd[v]);
if (i != 1)
val += max (dfn[i] > 1 ? t.qry(1, 1, n, 1, dfn[i] - 1) : 0,
mxd[i] < n ? t.qry(1, 1, n, mxd[i] + 1, n) : 0);
int mx = -1, mx2 = -1;
for (int x : val) if (x > mx) mx2 = mx, mx = x; else if (x > mx2) mx2 = x;
pre[i] = mx2 > 0 ? mx2 + 1 : 1;
}
t.op = -1, t.init(1, 1, n, n + 1);
for (int i = n; i >= 1; i--) {
t.upd(1, 1, n, dfn[i], i); basic_string<int> val;
for (int v : G[i]) if (v ^ fa[i]) val += t.qry(1, 1, n, dfn[v], mxd[v]);
if (i != 1)
val += min (dfn[i] > 1 ? t.qry(1, 1, n, 1, dfn[i] - 1) : n + 1,
mxd[i] < n ? t.qry(1, 1, n, mxd[i] + 1, n) : n + 1);
int mn = n + 2, mn2 = n + 2;
for (int x : val) if (x < mn) mn2 = mn, mn = x; else if (x < mn2) mn2 = x;
suf[i] = mn2 <= n ? mn2 - 1 : n;
}
// for (int i = 1; i <= n; i++) cerr << pre[i] << ' ' << suf[i] << '\n';
// #define BRUTE
#ifdef BRUTE
while (q--) {
int l, r; ll ans = 0; cin >> l >> r;
for (int i = l; i <= r; i++)
for (int j = i; j <= r; j++)
ans += (suf[i] >= j && pre[j] <= i);
cout << ans << '\n';
}
#else
for (int i = 1, l; i <= q; i++) rd(l), rd(qr[i]), qv[l] += i;
for (int i = 1; i <= n; i++) dl[pre[i] - 1] += i;
s.init(1, 1, n);
for (int l = n; l >= 1; l--) {
for (int r : dl[l]) s.del(1, 1, n, r);
s.upd(1, 1, n, l, suf[l], 1);
for (int i : qv[l]) ans[i] = s.qry(1, 1, n, l, qr[i]);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
#endif
}
/*
考虑类似支配对的东西。但这里不保证数量（星形图）
[l, r] 极小，意味着 l, r 在斯坦纳树上都是叶子
设 pre[i] 表示最小的 x 使得 i 在 [x, i] 的斯坦纳树上是叶子，suf[i] 同理
那么 [l, r] 极小等价于 pre[r] <= l && suf[l] >= r
怎么求 pre？考虑去掉 i 之后的每个连通块，分别求出最大的 x，使得 [x, i] 的斯坦纳树有该连通块内的点
然后取 次大值 + 1 是不是就对了，suf 同理，但是具体怎么算呢？
i 从小到大扫，在 dfn 序上搞，就是查区间最大值？
怎么回答询问？区间二维偏序数是什么能 polylog 的东西吗。
l 从大到小扫，一个 r 会在 pre[r] - 1 处变得不合法，相当于每次加入 / 减去一些 r 的贡献
再维护一个 d，然后就是区间 w += d，查询区间和，线段树维护
*/
```