“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;
}

主要思路

其实这道题没什么思路…就是一道主席树的模板题，用前缀和 \(sum[]\) 来维护不同版本之间数字出现的个数即可。

代码

// POJ2104.cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mid ((l + r) >> 1)
using namespace std;
const int MX_N = 1e5 + 20;
struct node
{
    int ls, rs, info, weight;
} nodes[(2 << 5) * MX_N];
int n, m, ncnt, seq[MX_N], misc[MX_N], len, roots[MX_N], sum[(2 << 5) * MX_N];
int getId(int val) { return lower_bound(misc + 1, misc + 1 + len, val) - misc; }
int build(int l, int r)
{
    int p = ++ncnt;
    if (l == r)
        return p;
    nodes[p].ls = build(l, mid);
    nodes[p].rs = build(mid + 1, r);
    return p;
}
int update(int l, int r, int previous, int c)
{
    int p = ++ncnt;
    nodes[p].ls = nodes[previous].ls;
    nodes[p].rs = nodes[previous].rs;
    sum[p] = sum[previous] + 1;
    if (l == r)
        return p;
    if (c <= mid)
        nodes[p].ls = update(l, mid, nodes[p].ls, c);
    else
        nodes[p].rs = update(mid + 1, r, nodes[p].rs, c);
    return p;
}
int query(int l, int r, int previous, int now, int k)
{
    int lsWeight = sum[nodes[now].ls] - sum[nodes[previous].ls];
    if (l == r)
        return l;
    if (k <= lsWeight)
        return query(l, mid, nodes[previous].ls, nodes[now].ls, k);
    else
        return query(mid + 1, r, nodes[previous].rs, nodes[now].rs, k - lsWeight);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    memcpy(misc, seq, sizeof(misc));
    sort(misc + 1, misc + 1 + n);
    len = unique(misc + 1, misc + 1 + n) - misc - 1;
    roots[0] = build(1, len);
    for (int i = 1; i <= n; i++)
        roots[i] = update(1, len, roots[i - 1], getId(seq[i]));
    while (m--)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", misc[query(1, len, roots[l - 1], roots[r], k)]);
    }
    return 0;
}