贪心思想。将a排序后，对于每一个a，找到对应的删除m个后最小的b，每次更新答案即可。
如何删除才是合法并且最优的？首先，对于排了序的a，第$i$个那么之前就应该删除前$i-1$个a对应的b。剩下$m-i+1$可以删，那么在剩下的b中查找第$m-i+2$小即可。每次做完就删除当前a对应的b。
注意离散化。
还有数组不要开大了....
#include<bits/stdc++.h>
#define LL long long
using namespace std; void read(int &x) {
x = ; int t = ; char ch = getchar();
while(ch > '' || ch < '') { if(ch == '-') t = -; ch = getchar(); }
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
x = x * t;
} int a[], b[], n, m; struct Node {
int a, b;
int ida, idb;
} mat[];
bool cmp(Node a, Node b) { if(a.a == b.a) return a.b < b.b; return a.a < b.a; } int siz[], val[]; void modify(int nd, int l, int r, int pos, int d) {
if(l == r) {
siz[nd] += d;
return ;
}
int mid = (l + r) >> ;
if(pos <= mid) modify(nd << , l, mid, pos, d);
else modify(nd << | , mid + , r, pos, d);
siz[nd] = siz[nd << ] + siz[nd << | ];
} int query(int nd, int l, int r, int pos) {
if(l == r) return val[l];
int mid = (l + r) >> ;
if(pos <= siz[nd << ]) return query(nd << , l, mid, pos);
else return query(nd << | , mid + , r, pos - siz[nd << ]);
} int pos[];
void work() {
sort(b + , b + + n);
int q = unique(b + , b + + n) - b - ; memset(siz, , sizeof(siz));
sort(mat + , mat + + n, cmp);
for(int i = ; i <= n; i ++) {
pos[i] = lower_bound(b + , b + + q, mat[i].b) - b;
val[pos[i]] = mat[i].b;
modify(, , q, pos[i], );
} LL ans = ;
int r = min(mat[].b, query(, , q, m + ));
ans = 1ll * mat[].a * r;
for(int i = ; i <= m; i ++) {
modify(, , q, pos[i], -);
int res = m - i + ;
r = query(, , q, res);
if(mat[i + ].b < r) r = mat[i + ].b;
LL now = 1ll * mat[i + ].a * r;
ans = max(ans, now);
} printf("%lld\n", ans);
} int main() {
freopen("d.in", "r", stdin);
freopen("d.out", "w", stdout);
int T;
scanf("%d", &T);
while(T --) {
read(n); read(m);
for(int i = ; i <= n; i ++) {
read(mat[i].a); read(mat[i].b);
b[i] = mat[i].b;
}
work();
}
return ;
}
依旧是数据结构。我们发现，对于一个点集，它们一定有一个lca，而满足包含所有点的最小点集就是所有点到这个lca的链上的所有点。再加上题目要求最小的$abs(a[u]-r)$，就是用每条链上r的前驱和后驱来更新答案。
用主席树维护即可。每个结点的版本是由它的父亲结点转移过来。这样做查询的时候直接取出当前结点和lca的父亲结点的版本即可。
关于这个前驱和后驱的计算可以学习一下。
#include<bits/stdc++.h>
#define LL long long
using namespace std; const int maxn = 1e9; void read(int &x) {
x = ; int t = ; char ch = getchar();
while(ch > '' || ch < '') { if(ch == '-') t = -; ch = getchar(); }
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
x = x * t;
} int n, q, type; struct Node {
int v, nex;
Node(int v = , int nex = ) :
v(v), nex(nex) { }
} Edge[]; int h[], stot;
void add(int u, int v) {
Edge[++stot] = Node(v, h[u]);
h[u] = stot;
} int sum[*], ls[*], rs[*], tail;
inline int newnode(int x) {
sum[++tail] = sum[x];
ls[tail] = ls[x]; rs[tail] = rs[x];
return tail;
} inline void update(int nd) {
sum[nd] = sum[ls[nd]] + sum[rs[nd]];
} int insert(int nd, int l, int r, LL pos) {
nd = newnode(nd);
sum[nd] ++;
if(l == r) return nd;
int mid = (l + r) >> ;
if(pos <= mid) ls[nd] = insert(ls[nd], l, mid, pos);
else rs[nd] = insert(rs[nd], mid + , r, pos);
update(nd);
return nd;
} int queryl(int nd1, int nd2, int l, int r, int pos) {
if(sum[nd1] == sum[nd2]) return ;///这个结点下面没有新的点
if(l == r) return l;
int mid = (l + r) >> ;
if(pos <= mid) return queryl(ls[nd1], ls[nd2], l, mid, pos);
else {
int tmp = queryl(rs[nd1], rs[nd2], mid + , r, pos);////尽量往靠近pos的地方走
if(tmp) return tmp;///如果走不到就尽量往mid走
else return queryl(ls[nd1], ls[nd2], l, mid, mid);
}
} int queryr(int nd1, int nd2, int l, int r, int pos) {
if(sum[nd1] == sum[nd2]) return ;
if(l == r) return l;
int mid = (l + r) >> ;
if(pos > mid) return queryr(rs[nd1], rs[nd2], mid + , r, pos);
else {
int tmp = queryr(ls[nd1], ls[nd2], l, mid, pos);
if(tmp) return tmp;
else return queryr(rs[nd1], rs[nd2], mid + , r, mid);
}
} int dep[], jum[][];
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int t = dep[u] - dep[v];
for(int p = ; t; t >>= , p ++)
if(t & ) u = jum[u][p];
if(u == v) return u;
for(int p = ; p >= ; p --)
if(jum[u][p] != jum[v][p]) u = jum[u][p], v = jum[v][p];
return jum[u][];
} int rt[], a[];
void dfs(int u, int f) {
jum[u][] = f;
for(int i = ; i < ; i ++)
jum[u][i] = jum[jum[u][i - ]][i - ];
dep[u] = dep[f] + ;
rt[u] = insert(rt[f], , maxn, a[u]);
for(int i = h[u]; i; i = Edge[i].nex) {
int v = Edge[i].v;
if(v == f) continue;
dfs(v, u);
}
} int x[], p[];
int main() {
freopen("e.in", "r", stdin);
freopen("e.out", "w", stdout);
scanf("%d%d%d", &n, &q, &type);
for(int i = ; i <= n; i ++) read(a[i]);
for(int i = ; i < n; i ++) {
int u, v;
read(u); read(v);
add(u, v); add(v, u);
}
dfs(, );
int lastans = ;
for(int i = ; i <= q; i ++) {
int r, k;
scanf("%d%d", &r, &k);
for(int j = ; j <= k; j ++) {
read(x[j]);
p[j] = (x[j] - + lastans * type) % n + ;
}
int l = p[];
for(int j = ; j <= k; j ++)
l = lca(l, p[j]);
l = jum[l][];
int res = maxn, tmp;
for(int j = ; j <= k; j ++) {
tmp = queryl(rt[l], rt[p[j]], , maxn, r);
if(tmp && r - tmp < res) res = r - tmp;
tmp = queryr(rt[l], rt[p[j]], , maxn, r);
if(tmp && tmp - r < res) res = tmp - r;
}
printf("%d\n", res);
lastans = res;
}
return ;
}