一种贪心思想，很符合直觉，又有点像乱搞
- 考虑一类点对统计问题，形如给定 \([l,r]\)，对于 \([l\le x\le y\le r]\)，你需要寻找满足某个限制的 \((x,y)\) 数量，或者是所有 \((x,y)\) 的最大权值
如果存在 \([x_1,y_1]\subset [x_2,y_2]\) 且 \([x_1,y_1]\) 满足限制 / 贡献更大，就可以只保留 \([x_1,y_1]\)
因为统计了 \([x_2,y_2]\) 就必须要统计 \([x_1,y_1]\)，反之则不一定成立。题目会给出一些性质使得最终保留下来的 \([x_1,y_1]\) 的数量不多
树上支配对 / 第一类支配对
- 这类问题的特征很明显，多次询问，给定一个编号区间，统计树上点对相关信息。
会想到点分治、dsu on tree 这两个工具，其中点分治处理距离问题更方便，dsu on tree 更常用来处理 LCA 问题
固定当前的根之后，钦定支配对来自两个不同子树（注意根自身参与形成支配对的情况），那么共有 \(O(n\log n)\) 对支配对先用这两种方法在树上找到支配对，就可以把询问离线下来做扫描线之类的了
本质是利用 LCA 的树上性质，以及点分、dsu on tree 只用统计 \(O(n\log n)\) 个单侧点，同时对于每个单侧点只存在 \(O(1)\) 个相应的前驱、后继点达到 LCA 找到 \(O(n\log n)\) 个支配对
D - rldcot
https://www.luogu.com.cn/problem/P7880
- 若存在 \((x_1,y_1)\) 和 \((x_2,y_2)\) 拥有相同的 LCA，那么认为 \((x_1,y_1)\) 支配了 \((x_2,y_2)\)
- 树有根，故需要 dsu on tree
- 用一个 set 处理前驱、后继的查询，然后就是正常的 dsu on tree 了
- 离线下来扫描线，树状数组实时维护每个颜色（离散化一下）最靠右的区间即可
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
using ll = long long;
int n, m;
std::cin >> n >> m;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int i = 1, x, y, w; i < n; ++i) {
std::cin >> x >> y >> w;
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
}
int tot = 0;
std::vector<ll> dep(n + 1);
std::unordered_map<ll, int> tab;
std::vector<int> siz(n + 1), son(n + 1), col(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
siz[x] = 1;
if (!tab.count(dep[x]))
tab[dep[x]] = ++tot;
col[x] = tab[dep[x]];
for (auto [i, w] : g[x])
if (i != fa) {
dep[i] = dep[x] + w;
DFS(i, x);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
DFS(1, -1);
std::vector<std::vector<std::pair<int, int> > > u(n + 1);
std::function<void(int, int, int, std::set<int> &)> DFS2 = [&](int col, int x, int fa, std::set<int> &t) {
auto p = t.lower_bound(x);
if (col == -1)
t.insert(x);
else {
if (p != t.begin())
u[x].emplace_back(*std::prev(p), col );
if (p != t.end())
u[*p].emplace_back(x, col);
}
for (auto [i, w] : g[x])
if (i != fa)
DFS2(col, i, x, t);
return;
};
std::function<void(int, int, std::set<int> &)> DFS1 = [&](int x, int fa, std::set<int> &t) {
if (son[x])
DFS1(son[x], x, t);
for (auto [i, w] : g[x])
if (i != fa && i != son[x]) {
std::set<int> nt;
DFS1(i, x, nt);
}
t.insert(x);
u[x].emplace_back(x, col[x]);
for (auto [i, w] : g[x])
if (i != fa && i != son[x])
DFS2(col[x], i, x, t), DFS2(-1, i, x, t);
return;
};
{
std::set<int> t;
DFS1(1, -1, t);
}
std::vector<int> res(m + 1);
std::vector<std::vector<std::pair<int, int> > > t(n + 1);
for (int i = 1, l, r; i <= m; ++i) {
std::cin >> l >> r;
t[r].emplace_back(l, i);
}
std::vector<int> bit(n + 1), la(tot + 1);
auto lowbit = [](int x) {
return x & -x;
};
auto add = [&](int x, int v) {
for (; x <= n; x += lowbit(x))
bit[x] += v;
return;
};
auto ask = [&](int x) {
int res = 0;
for (; x; x -= lowbit(x))
res += bit[x];
return res;
};
for (int r = 1; r <= n; ++r) {
for (auto [l, c] : u[r])
if (l > la[c]) {
if (la[c])
add(la[c], -1);
add(l, 1), la[c] = l;
}
for (auto [l, id] : t[r])
res[id] = ask(r) - ask(l - 1);
}
for (int i = 1; i <= m; ++i)
std::cout << res[i] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}E - 铃原露露
https://www.luogu.com.cn/problem/P8528
考虑一下支配关系在哪里，固定一个 LCA \(z\)，讨论 \(a_z\) 与 \(a_x,a_y\) 的大小关系给 \([1,a_x]\) 间的 \(l\) 带来的限制：
- \(a_z\in[a_x,a_y]\)，\((x,y)\) 总是合法，无限制。
- \(a_z<a_x\)，对于 \(r\ge a_y\)，当 \(l\in(a_z,a_x]\) 时，\((x,y)\) 非法。
- \(a_z>a_y\)，当 \(r\in[a_y,a_z)\) 时，\((x,y)\) 总是非法。此时所有 \(l\in[1,a_x]\) 不可选。
- 发现固定 \(a_z,a_x\)，那么当 \(a_y\) 越靠近 \(a_x\) 时给出的限制越紧，反之亦然，就可以得到这样的支配关系
- 容易发现当 \(a_z\notin [a_x,a_y]\) 时，\((x,y)\) 不合法；故只需要在 dsu on tree 上找到 \(a_x\) 的前驱、后继并统计支配对即可
考虑询问，发现需要维护区间加、区间历史 0 个数，后者是经典 trick，是好做的。
历史标记的下传需要格外注意一下，应该只保证标记期间存在 0 的区间拥有懒标记；具体地，只应将其下传到和当前区间最小值相同的子区间（具体可以看代码），容易证明是对的。
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
struct node {
long long s;
int l, r, u, c, d, d1;
node operator+ (const node q) const {
node res;
res.s = s + q.s;
res.l = l, res.r = q.r;
res.u = std::min(u, q.u);
res.d = res.d1 = res.c = 0;
if (u == res.u)
res.c = c;
if (q.u == res.u)
res.c += q.c;
return res;
}
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].c = r - l + 1;
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushdown(int p) {
if (t[p].d) {
t[lt].d += t[p].d, t[lt].u += t[p].d;
t[rt].d += t[p].d, t[rt].u += t[p].d;
t[p].d = 0;
}
if (t[p].d1) {
if (t[lt].u == t[p].u) {
t[lt].s += (long long)t[lt].c * t[p].d1;
t[lt].d1 += t[p].d1;
}
if (t[rt].u == t[p].u) {
t[rt].s += (long long)t[rt].c * t[p].d1;
t[rt].d1 += t[p].d1;
}
t[p].d1 = 0;
}
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d += v, t[p].u += v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p] = t[lt] + t[rt];
return;
}
void upd(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) {
if (!t[p].u)
t[p].s += t[p].c, ++t[p].d1;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r);
if (r > mid)
upd(rt, l, r);
t[p] = t[lt] + t[rt];
return;
}
long long ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
auto res(0ll);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > g(n + 1);
for (int i = 2, x; i <= n; ++i)
std::cin >> x, g[x].push_back(i);
std::vector<int> siz(n + 1), son(n + 1);
std::function<void(int)> DFS = [&](int x) {
siz[x] = 1;
for (auto i : g[x]) {
DFS(i);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
};
DFS(1);
std::vector<std::vector<std::pair<int, int> > > u1(n + 1), u2(n + 1);
std::function<void(int, int, std::set<int> &)> DFS2 = [&](int col, int x, std::set<int> &t) {
auto p = t.lower_bound(a[x]);
if (col == -1)
t.insert(a[x]);
else {
if (p != t.begin()) {
int y = *std::prev(p);
if (col < y)
u1[a[x]].emplace_back(col + 1, y);
else if (col > a[x]) {
u1[a[x]].emplace_back(1, y);
u2[col].emplace_back(1, y);
}
}
if (p != t.end()) {
int y = *p;
if (col < a[x])
u1[y].emplace_back(col + 1, a[x]);
else if (col > y) {
u1[y].emplace_back(1, a[x]);
u2[col].emplace_back(1, a[x]);
}
}
}
for (auto i : g[x])
DFS2(col, i, t);
return;
};
std::function<void(int, std::set<int> &)> DFS1 = [&](int x, std::set<int> &t) {
if (son[x])
DFS1(son[x], t);
for (auto i : g[x])
if (i != son[x]) {
std::set<int> nt;
DFS1(i, nt);
}
t.insert(a[x]);
for (auto i : g[x])
if (i != son[x])
DFS2(a[x], i, t), DFS2(-1, i, t);
return;
};
{
std::set<int> t;
DFS1(1, t);
}
std::vector<long long> res(m + 1);
std::vector<std::vector<std::pair<int, int> > > t(n + 1);
for (int i = 1, l, r; i <= m; ++i) {
std::cin >> l >> r;
t[r].emplace_back(l, i);
}
bld(1, 1, n);
for (int i = 1; i <= n; ++i) {
for (auto [l, r] : u1[i])
add(1, l, r, 1);
for (auto [l, r] : u2[i])
add(1, l, r, -1);
upd(1, 1, i);
for (auto [l, id] : t[i])
res[id] = ask(1, l, i);
}
for (int i = 1; i <= m; ++i)
std::cout << res[i] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}