HDU4358 Boring counting

题目描述

分析

这道题做起来还有点复杂。一开始并没有想到离线,以为是自己在线算法掌握得不够多…
首先一定是将问题转化为dfs序上的区间询问。我们先将询问按右端点排序,从左向右扫描dfs序,我们维护从每一个位置到当前点这段区间恰好出现K次的权值种数(即这段区间的答案)。考虑加入第i个位置的点,设它权值为val,之前同权值的点位置为p_1,p_2,…,p_t(包括它自己),那么这时候位置p_{t-K-1}+1p_{t-K}位置答案会减少1(现在这段区间val值个数超过了K个),而p_{t-K}+1p_{t-K+1}位置的答案会增加1,这样以来问题就变为了区间修改,单点查询,我们可以用差分树状数组实现。加入完后,就可以回答右端点是i的询问了。
时间复杂度:O(n log n)
(然后网上还有一种很诡异的写法,好像是错的,可能数据弱恰好过了?)

核心代码

typedef int Arr[MAXN];

struct Query {
    int id, l, r;
    bool operator<(const Query & q) const {
        return r < q.r;
    }
} qry[MAXN];

int N, K, Q, totn, tote, dfs_clock;
Arr last, vrt, bgn, end, num, W, ans;
std::vector<int> pos[MAXN];

void dfs(int u, int fa) {
    bgn[u] = ++dfs_clock;
    vrt[dfs_clock] = W[u];
    for (int v, e = last[u]; e; e = E[e].next) {
        if ((v = E[e].to) == fa) continue;
        dfs(v, u);
    }
    end[u] = dfs_clock;
}

inline int get_id(int val) {
    return std::lower_bound(num, num + totn, val) - num;
}

void solve() {
    totn = tote = dfs_clock = 0;
    memset(last, 0, sizeof last);
    using FastIO::read;

    read(N), read(K);
    for (int i = 1; i <= N; i++) read(W[i]), num[totn++] = W[i];
    for (int i = 1, ui, vi; i < N; i++) {
        read(ui), read(vi);
        add_edge(ui, vi);
    }
    dfs(1, 0);
    read(Q);
    for (int i = 0, u; i < Q; i++) {
        read(u);
        qry[i] = (Query){i, bgn[u], end[u]};
    }

    std::sort(num, num + totn);
    totn = std::unique(num, num + totn) - num;
    for (int i = 0; i < totn; i++) pos[i].clear(), pos[i].pb(0);
    // pos是存储每一类权值出现位置的向量,先放入一个0(虚点)方便处理
    std::sort(qry, qry + Q);
    BIT::init();
    for (int i = 1, iq = 0; i <= N && iq < Q; i++) {
        std::vector<int> & now = pos[get_id(W[i])];
        now.pb(i);
        int cnt = now.size() - 1;
        // 注意减去虚点
        if (cnt >= K) {
            BIT::add(now[cnt - K] + 1, now[cnt - K + 1], 1);
            if (cnt > K) BIT::add(now[cnt - K - 1] + 1, now[cnt - K], -1);
            // 这里的操作还可以简化
        }
        for (; iq < Q && qry[iq].r == i; ++iq) ans[qry[iq].id] = BIT::query(qry[iq].l);
    }

    static int ks = 0;
    if (ks) putchar('\n');
    FastIO::write("Case #");
    FastIO::write(++ks);
    putchar(':'), putchar('\n');
    for (int i = 0; i < Q; i++) FastIO::writeln(ans[i]);
}

总结

这题的离线思想比较难想到,其实说实在的还是暴力。另外,又学到了一种新的维护答案的方法:用BIT维护。还有就是一开始被网上错误的思路困扰了,看过题解还是应该自己多想想。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注