P4899:[IOI2018] werewolf 狼人题解

解法

这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态,我们要找到一个点点权小于\(L\)的点,就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl,其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值,然后按最小生成树的方式去构造重构树;符合狼形规律的 Kruskal 重构树被记为 Tu,其中构造它的方式就是将端点编号最小值赋为边权,然后按最大生成树的方式构造。之后,我们再到主席树中求交集即可,如果有交集那么查询结果为一个不为零的数,输出\(1\)即可;没有交集那么查询结果即为\(0\),输出\(0\)。

继续阅读P4899:[IOI2018] werewolf 狼人题解

主席树总结

简述

主席树是一个很有意思的数据结构,其全称其实是「可持久化线段树」,至于为什么叫「主席树」是因为:

由于发明者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛(H.J.T.)相同,因此这种数据结构也可被称为总书记树或主席树。

From Wikipedia.org

继续阅读主席树总结

数颜色题解

题意

给定一个长度为n的序列A[],你需要回答q个询问。每次给定两个端点,询问区间内不同颜色的个数。n, q < 1e5。

主要思路

可以考虑建立主席树,以位置做版本下标,以颜色离散化后的值做下标,记录该颜色前缀个数,然后版本信息相减即可。

P3899:[湖南集训]谈笑风生题解

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

 

POJ2104:K-th Number 题解

主要思路

其实这道题没什么思路…就是一道主席树的模板题,用前缀和 \(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;
}