关于矩形与点其实有两种关系。
一种是每个矩形包含多少点。一种是每个点被多少矩形包含。
解：因为可以离线所以直接套整体二分。关键是考虑如何能够被覆盖。
我一开始都是想的树上操作...其实是转化成DFS序。分链和有lca两种情况。
考虑每个盘子能接住的水果，两端DFS序满足的性质。发现是二维平面上的矩形。
一个水果就是询问一个点被多少矩形覆盖(能被多少盘子接)。于是整体二分里面扫描线，片改点查用树状数组。
#include <bits/stdc++.h>
const int N = ;
struct Edge {
int nex, v;
}edge[N << ]; int tp;
int e[N], pos[N], ed[N], num, n, fa[N][], pw[N], d[N]; /// tree
int X[N], xx, ans[N];
struct Node {
int id, x, y, k, z;
Node(int ID = , int X = , int Y = , int K = , int Z = ) {
id = ID;
x = X;
y = Y;
k = K;
z = Z;
}
inline bool operator <(const Node &w) const {
if(id != w.id) return id < w.id;
return z < w.z;
}
}node[N], t1[N], t2[N], stk[N << ];
namespace ta {
int ta[N];
inline void add(int x, int v) {
for(int i = x; i <= n + ; i += (i & (-i))) {
ta[i] += v;
}
return;
}
inline int ask(int x) {
int ans = ;
for(int i = x; i >= ; i -= (i & (-i))) {
ans += ta[i];
}
return ans;
}
inline void del(int x) {
for(int i = x; i <= n + ; i += (i & (-i))) {
ta[i] = ;
}
return;
}
}
inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void DFS(int x, int f) {
pos[x] = ++num;
fa[x][] = f;
d[x] = d[f] + ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) continue;
DFS(y, x);
}
ed[x] = num;
return;
}
inline void prework() {
for(int i = ; i <= n; i++) pw[i] = pw[i >> ] + ;
for(int j = ; j <= pw[n]; j++) {
for(int i = ; i <= n; i++) {
fa[i][j] = fa[fa[i][j - ]][j - ];
}
}
return;
}
inline int lca(int x, int y) {
if(d[x] > d[y]) std::swap(x, y);
int t = pw[n];
while(t >= && d[y] > d[x]) {
if(d[fa[y][t]] >= d[x]) {
y = fa[y][t];
}
t--;
}
if(x == y) return x;
t = pw[n];
while(t >= && fa[x][] != fa[y][]) {
if(fa[x][t] != fa[y][t]) {
x = fa[x][t];
y = fa[y][t];
}
t--;
}
return fa[x][];
}
inline int getPos(int x, int y) {
int t = pw[n];
while(t >= && fa[y][] != x) {
if(d[fa[y][t]] > d[x]) {
y = fa[y][t];
}
t--;
}
return y;
}
void Div(int L, int R, int l, int r) {
if(L > R) return;
if(l == r) {
for(int i = L; i <= R; i++) {
if(node[i].id) ans[node[i].id] = r;
}
return;
}
int mid = (l + r) >> , top1 = , top2 = , top = ;
for(int i = L; i <= R; i++) {
int x = node[i].x, y = node[i].y, z = node[i].z;
if(!node[i].id) { /// change | this is a Matrix
if(node[i].k > mid) {
t2[++top2] = node[i];
continue;
}
t1[++top1] = node[i];
if(z) { /// line
stk[++top] = Node(, pos[y], ed[y], , );
stk[++top] = Node(pos[z], pos[y], ed[y], -, );
stk[++top] = Node(pos[y], ed[z] + , n, , );
stk[++top] = Node(ed[y] + , ed[z] + , n, -, );
}
else { /// lca
stk[++top] = Node(pos[x], pos[y], ed[y], , );
stk[++top] = Node(ed[x] + , pos[y], ed[y], -, );
}
}
else { /// ask | this is a Point
stk[++top] = Node(pos[x], , pos[y], i, );
}
}
std::sort(stk + , stk + top + );
for(int i = ; i <= top; i++) {
if(stk[i].z == ) { /// change
ta::add(stk[i].x, stk[i].k);
ta::add(stk[i].y + , -stk[i].k);
}
else { /// ask
int t = ta::ask(stk[i].y), id = stk[i].k;
if(node[id].k <= t) {
t1[++top1] = node[id];
}
else {
node[id].k -= t;
t2[++top2] = node[id];
}
}
}
for(int i = ; i <= top; i++) { /// clear
if(stk[i].z == ) {
ta::del(stk[i].x);
ta::del(stk[i].y + );
}
}
memcpy(node + L, t1 + , top1 * sizeof(Node));
memcpy(node + L + top1, t2 + , top2 * sizeof(Node));
Div(L, L + top1 - , l, mid);
Div(L + top1, R, mid + , r);
return;
}
int main() {
int m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i = , x, y; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
DFS(, );
prework();
for(int i = , x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &X[i]);
if(pos[x] > pos[y]) std::swap(x, y);
z = lca(x, y);
node[i] = Node(, x, y, X[i], (z == x) ? getPos(x, y) : );
}
std::sort(X + , X + n + );
xx = std::unique(X + , X + n + ) - X - ;
for(int i = ; i <= m; i++) {
node[i].k = std::lower_bound(X + , X + xx + , node[i].k) - X;
}
for(int i = , x, y, k; i <= q; i++) {
scanf("%d%d%d", &x, &y, &k);
if(pos[x] > pos[y]) std::swap(x, y);
node[m + i] = Node(i, x, y, k, );
}
Div(, m + q, , xx);
for(int i = ; i <= q; i++) printf("%d\n", X[ans[i]]);
return ;
}
AC代码