一开始想了一个假的，后面写完了之后才意识到哪里错了，就很傻逼。
首先贪心的知道，肯定是第 \(i\) 小的数位于 \(K + i – 1\) 的位置上。我们算答案的时候会发现无非就是把贡献根据绝对值的拆法进行分开处理，一部分是 \((a_i – rk_i) – (k – 1)\)，还有一部分是 \((k – 1) – (a_i – rk_i)\)。所以我们需要一个数据结构来拆分这两个部分。
首先我们知道这两个部分肯定是连续的两段，因为前后的 Delta 都至多为 \(1\)。知道这个性质之后，我们其实可以尝试用主席树来搞区间内的段。考虑用势能线段树的那一套，我们可以把段一直下传，直到段完整为止。
对于完整的段，发现其实就是给上面那个贡献式子套 \(\sum\)，而且发现套 \(\sum\) 的时候要记录这一段和的左端点，这样就可以用等差数列直接搞了。
Continue reading →\(\Theta(n^2)\)暴力还是很好写的，先枚举水平线，然后再分上下讨论；讨论中，我们都要从左往右枚举，但是我们有两个指针\(lptr, rptr\)，我们可以在过程中维护在\([lptr, rptr]\)之间的颜色数始终严格小于\(k\)，然后再用点个数更新答案。
那么正解就没这么好写了。我们考虑在\(k\)中枚举一个被排除的颜色，然后分情况讨论：
详细见代码：
这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态，我们要找到一个点点权小于\(L\)的点，就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl，其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值，然后按最小生成树的方式去构造重构树；符合狼形规律的 Kruskal 重构树被记为 Tu，其中构造它的方式就是将端点编号最小值赋为边权，然后按最大生成树的方式构造。之后，我们再到主席树中求交集即可，如果有交集那么查询结果为一个不为零的数，输出\(1\)即可；没有交集那么查询结果即为\(0\)，输出\(0\)。
主席树是一个很有意思的数据结构，其全称其实是「可持久化线段树」，至于为什么叫「主席树」是因为：
由于发明者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛（H.J.T.）相同，因此这种数据结构也可被称为总书记树或主席树。
From Wikipedia.org
给定一个长度为n的序列A[]，你需要回答q个询问。每次给定两个端点，询问区间内不同颜色的个数。n, q < 1e5。
可以考虑建立主席树，以位置做版本下标，以颜色离散化后的值做下标，记录该颜色前缀个数，然后版本信息相减即可。
“This is a big mistake!”
如何把对主席树“能解决区间第 k 大问题”这个印象迁移到这道非常暴力的题目上呢？我们可以把整棵树用 DFS 序来入手（连续性在本题会比离散型更好）。我们可以先用一个 DFS 来记录 DFS 序、Low 数组、子树大小。
然后，我们以深度为权值，子树大小为要维护的信息。以 DFS 序的顺序来计算前缀子树和、创建主席树。具体见代码：
// P3899.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
const ll MX_N = 3e5 + 1000;
ll ncnt, dfn[MX_N], low[MX_N], antiDFN[MX_N], ndfn, dep[MX_N], fa[MX_N], n, q, tmpx, tmpy;
ll subtree[MX_N], roots[MX_N];
vector<ll> G[MX_N];
struct node
{
ll sum, ls, rs;
} nodes[MX_N * (2 << 5)];
ll build(ll l, ll r)
{
ll p = ++ncnt;
if (l == r)
return p;
nodes[p].ls = build(l, mid), nodes[p].rs = build(mid + 1, r);
nodes[p].sum = 0;
return p;
}
ll update(ll l, ll r, ll previous, ll depth, ll ad)
{
ll curt = ++ncnt;
nodes[curt].ls = nodes[previous].ls, nodes[curt].rs = nodes[previous].rs;
nodes[curt].sum = nodes[previous].sum + ad;
if (l == r && l == depth)
return curt;
if (depth <= mid)
nodes[curt].ls = update(l, mid, nodes[previous].ls, depth, ad);
else
nodes[curt].rs = update(mid + 1, r, nodes[previous].rs, depth, ad);
return curt;
}
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
if (ql <= l && r <= qr)
return nodes[p].sum;
if (mid >= qr)
return query(ql, qr, l, mid, nodes[p].ls);
if (mid < ql)
return query(ql, qr, mid + 1, r, nodes[p].rs);
return query(ql, qr, l, mid, nodes[p].ls) + query(ql, qr, mid + 1, r, nodes[p].rs);
}
void dfs(ll u)
{
dfn[u] = ++ndfn, subtree[u]++;
antiDFN[ndfn] = u, dep[u] = dep[fa[u]] + 1;
ll siz = G[u].size();
for (ll i = 0; i < siz; i++)
if (G[u][i] != fa[u])
fa[G[u][i]] = u, dfs(G[u][i]), subtree[u] += subtree[G[u][i]];
low[u] = ndfn;
}
int main()
{
scanf("%lld%lld", &n, &q);
for (int i = 0; i < n - 1; i++)
scanf("%lld%lld", &tmpx, &tmpy), G[tmpx].push_back(tmpy), G[tmpy].push_back(tmpx);
dfs(1), roots[0] = build(1, n);
for (int i = 1; i <= n; i++)
roots[i] = update(1, n, roots[i - 1], dep[antiDFN[i]], subtree[antiDFN[i]] - 1);
while (q--)
{
scanf("%lld%lld", &tmpx, &tmpy);
ll ret = min(dep[tmpx] - 1, tmpy) * (subtree[tmpx] - 1);
ll another = query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[low[tmpx]]) -
query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[dfn[tmpx]]);
printf("%lld\n", ret + another);
}
return 0;
}