SP10628 COT - Count on a tree

xfrvq · 2022-03-06 18:21:18 · 题解

扯淡

定义 n,m 同阶。

首先，通过分析大多数根号数据结构和 \log 数据结构，可以得出

根号套根号，复杂度仍是根号（如分块套莫队，序列分块套值域分块）
根号和 \log 之间不太兼容，它们套起来是 n\sqrt n\log n，跑 10^5 都非常吃力。

首先这个题是树上询问一些不太好做的东西，考虑树上莫队，它还要套上一个可以求 k 大的东西，考虑平衡树。

但是我说过根号是不能和 \log 兼容的，所以我们要把平衡树换成其它东西，比如 值域分块。

莫队所套数据结构是 O(n\sqrt n) 次修改，O(n) 次查询，所以我们应该让这个值域分块 O(1) 插入或删除一数 O(\sqrt n) 查询全局 k 小。

值域分块

同样这玩意求区间 k 小的题：P4278，P4119，过程如下：

值域分块，维护每个值域块的和以及每个位置的和
查询时先不停比较 k 与从小到大每个值域块的出现次数，如果 k 更大就让 k 减去这个出现次数。
不停比较 k 与这个值域块从小到大每一个值的出现次数，如果 k 更大就让 k 减去这个出现次数。

namespace Blk{
    int s1[maxn],s2[sqr],B,C,st[sqr],ed[sqr];

    // B: 块长, C: 块数 
    // s1: 每个位置的出现次数
    // s2: 每个值域块的总出现次数
    // st,ed: 每个值域块的开头/结尾 

    int qry(int k){
        for(int i = 1;i <= C;++i){
            if(k > s2[i]){ k -= s2[i]; continue; }
            for(int j = st[i];j <= ed[i];++j)
                if(k > s1[j]) k -= s1[j];
                else return j;
        }
        return -1;
    }
}

实现

于是剩下贺个树上莫队板子即可。

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>

inline int read(){
    register int x = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return x;
}

#define maxn 200005
#define maxm 400005
#define sqr  450

int n,m;

int c[maxn],d[maxn];
int ans[maxn];

std::vector<int> G[maxn];

int L[maxn],R[maxn],path[maxm],dfn = 0;
int lg2[maxn],dep[maxn],fa[maxn][20];

void dfs(int u = 1,int ft = 0){
    L[u] = ++dfn; path[dfn] = u;
    dep[u] = dep[ft] + 1; fa[u][0] = ft;
    for(int i = 1;i <= 19;++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = 0;i < (int)G[u].size();++i) if(G[u][i] != ft) dfs(G[u][i],u);
    R[u] = ++dfn; path[dfn] = u;
}

int LCA(int x,int y){
    if(dep[x] < dep[y]) x ^= y ^= x ^= y;
    while(dep[x] > dep[y]) x = fa[x][lg2[dep[x] - dep[y]]];
    if(x == y) return x;
    for(int i = 19;~i;--i) if(fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
    return fa[x][0];
}

namespace Blk{
    int s1[maxn],s2[sqr],B,C,st[sqr],ed[sqr],bl[maxn];

    void init(){
        B = sqrt(n); C = (n - 1) / B + 1;
        for(int i = 1;i <= C;++i){
            st[i] = (i - 1) * B + 1;
            ed[i] = i == C ? n : i * B;
            for(int j = st[i];j <= ed[i];++j) bl[j] = i;
        }
    }

    void ins(int x){ ++s1[x]; ++s2[bl[x]]; }

    void ers(int x){ --s1[x]; --s2[bl[x]]; }

    int qry(int k){
        for(int i = 1;i <= C;++i){
            if(k > s2[i]){ k -= s2[i]; continue; }
            for(int j = st[i];j <= ed[i];++j)
                if(k > s1[j]) k -= s1[j];
                else return j;
        }
        return -1;
    }
}

bool use[maxn];

void upd(int i){ use[i] = !use[i]; use[i] ? Blk::ins(c[i]) : Blk::ers(c[i]); }

struct qry{
    int l,r,k,lca,i,be;
    bool operator<(const qry& q) const {
        return be ^ q.be ? be < q.be : be & 1 ? r < q.r : r > q.r;
    }
} q[maxn];

signed main(){
    n = read(),m = read();
    Blk::init();
    int bl = sqrt(n * 1.0);
    for(int i = 1;i <= n;++i) c[i] = d[i] = read();
    std::sort(d + 1,d + n + 1);
    int k = std::unique(d + 1,d + n + 1) - d - 1;
    for(int i = 1;i <= n;++i) c[i] = std::lower_bound(d + 1,d + k + 1,c[i]) - d;
    for(int i = 1;i < n;++i){
        int u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs();
    for(int i = 2;i <= n;++i) lg2[i] = lg2[i >> 1] + 1; 
    for(int i = 1;i <= m;++i){
        int u = read(),v = read(),lca = LCA(u,v); q[i].k = read();
        if(L[u] > L[v]) u ^= v ^= u ^= v;
        if(lca == u) q[i].l = L[u],q[i].r = L[v];
        else q[i].l = R[u],q[i].r = L[v],q[i].lca = lca;
        q[i].i = i; q[i].be = q[i].l / bl;
    }
    std::sort(q + 1,q + m + 1);
    int l = 1,r = 0;
    for(int i = 1;i <= m;++i){
        while(l < q[i].l) upd(path[l++]);
        while(l > q[i].l) upd(path[--l]);
        while(r > q[i].r) upd(path[r--]);
        while(r < q[i].r) upd(path[++r]);
        if(q[i].lca) upd(q[i].lca);
        ans[q[i].i] = Blk::qry(q[i].k);
        if(q[i].lca) upd(q[i].lca);
    }
    for(int i = 1;i <= m;++i) printf("%d\n",d[ans[i]]);
    return 0;
}

注意：这题不能交 C++11 及以上版本，而 SPOJ C++ 语言不能以 const 变量大小建立数组，把我弄 CE 了好几回