P5305 [GXOI/GZOI2019]旧词

时间：2023-03-09 00:03:08
P5305 [GXOI/GZOI2019]旧词

题目地址：P5305 [GXOI/GZOI2019]旧词

这里是官方题解

\[\sum_{i \leq x}^{}\ depth(lca(i,y))^k\]

\(k = 1\)

求的是 \(\sum_{i \leq x}^{}\ depth(lca(i,y))\) ，一堆点然后每个点和 \(y\) 求 \(lca\) 然后深度求和。

总体思路是把 \(lca\) 的值摊派到这个点到根的路径上（这个东西也叫树上差分？），再离线解决所有询问。

维护一个点权数组 \(sum\) ，初始为 \(0\) ，然后将 \(y\) 到根的每个点的点权设为 \(1\) ，然后对于每个点 \(i \leq x\) ，求从 \(i\) 到根的权值和为上面要求的答案，但这样就 \(O(n)\) 了。

（可以反向考虑），维护一个点权数组 \(sum\) ，初始为 \(0\) ，对于小于等于 \(x\) 的点 \(i\) ，将 \(i\) 到根的路径上所有点的点权 ++ 。然后求从 \(y\) 到根的权值和也是上面要求的答案。这种方法求可以按 \(x\) 排序，然后离线， \(x\) 相等的询问一块问。

可以树链剖分 + 线段树解决。 \(O(nlog^2n)\) 。或者 LCT 也行。

\(k > 1\)

\(k = 2\) 的话，按照上述思路想，把 \(lca^2\) 的值摊到到根的路径上的话就不是之前的 \(1,1,1,...\) ，变成了 \(1,3,5,...\) 直接看的话问题变成了线段树区间加等差数列，好像改一下线段树实现也能做（所以给了点部分分）。

但是 \(k > 2\) 的时候就比较麻烦了。

基于把 \(lca^k\) 摊到从这个点到根的路径上这个思路，实际上对于深度是 \(x\) 的点来说，这个点每次点权增加的值固定是 \(x ^ k - (x - 1) ^ k\) 。

所以实际上，线段树打标记只用记录每个点被算了多少次 \(cnt\) 即可。然后实际上的权值和是 \(sum_i = cnt_i * (dep_i^k -(dep_i - 1)^k)\) ，每次操作只有 \(cnt\) 区间加 \(1\) ，于是预处理线段树上每个区间的 \(\sum (dep_i^k -(dep_i - 1)^k)\) 后就可以直接拿线段树维护 \(sum\) 数组。

于是还是之前的树链剖分 + 线段树解决。 \(O(nlog^2n)\) 。或者 LCT 也行。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

// by zrt
// zhangruotian@foxmail.com

using namespace std;

typedef long long LL;

const int MAXN = 50000+5;
const LL mod = 998244353;

int n,Q,k;
int H[MAXN], X[MAXN], P[MAXN], tot;
int fa[MAXN], dep[MAXN], dfn[MAXN], invdfn[MAXN], siz[MAXN], son[MAXN], top[MAXN];

inline void add(int x,int y) {
    P[++tot]=y;
    X[tot]=H[x];
    H[x]=tot;
}

struct Query {
    int x,y,id;
} query[MAXN];

int ans[MAXN];

bool cmp_by_x(Query a, Query b) {
    return a.x<b.x;
}

void dfs1(int x) {
    dep[x] = dep[fa[x]] + 1;
    siz[x] = 1;
    for(int i=H[x]; i; i=X[i]) {
        dfs1(P[i]);
        siz[x] += siz[P[i]];
        if(siz[P[i]]>siz[son[x]]) {
            son[x] = P[i];
        }
    }
}

int tim;

void dfs2(int x) {
    dfn[x] = ++tim;
    if(!top[x]) top[x]=x;
    if(son[x]) top[son[x]] = top[x], dfs2(son[x]);
    for(int i=H[x]; i; i=X[i]) {
        if(P[i] == son[x]) continue;
        dfs2(P[i]);
    }
}

LL pow(LL a,LL b,LL p) {
    LL ret = 1%p;
    while(b) {
        if(b&1) ret = ret*a%p;
        b>>=1;
        a=a*a%p;
    }
    return ret;
}

const int MAXN4 = MAXN*4;
struct SEGMENT_TREE {
    LL sum[MAXN4], cnt[MAXN4], pre[MAXN4];
    void updsum(int o) {
        sum[o] = (sum[o<<1] + sum[o<<1|1])%mod;
    }
    void bd(int o,int l,int r) {
        if(l==r) {
            pre[o] = (pow(dep[invdfn[l]],k,mod) - pow(dep[invdfn[l]]-1,k,mod) + mod)%mod;
            cnt[o] = sum[o] = 0;
        } else {
            int mid=(l+r)/2;
            bd(o<<1,l,mid);
            bd(o<<1|1,mid+1,r);
            pre[o] = (pre[o<<1]+pre[o<<1|1])%mod;
        }
    }
    void build() {
        bd(1,1,n);
    }
    void down(int o) {
        if(cnt[o]>0) {
            sum[o<<1] = (sum[o<<1]+(pre[o<<1]*cnt[o])%mod)%mod;
            cnt[o<<1] += cnt[o];
            sum[o<<1|1] = (sum[o<<1|1]+(pre[o<<1|1]*cnt[o])%mod)%mod;
            cnt[o<<1|1] += cnt[o];
            cnt[o]=0;
        }
    }
    void add(int o,int l,int r,int L,int R) {
        if(l == L && r == R) {
            sum[o] = (sum[o]+pre[o]) % mod;
            cnt[o] ++;
        } else {
            int mid=(l+r)/2;
            down(o);
            if(R<=mid) add(o<<1,l,mid,L,R);
            else if(L>mid) add(o<<1|1,mid+1,r,L,R);
            else add(o<<1,l,mid,L,mid), add(o<<1|1,mid+1,r,mid+1,R);
            updsum(o);
        }
    }
    void add(int l,int r) {
        assert(l<=r);
        add(1,1,n,l,r);
    }
    LL ask(int o,int l,int r,int L,int R) {
        if(l==L && r == R) {
            return sum[o];
        } else {
            int mid=(l+r)/2;
            down(o);
            if(R<=mid) return ask(o<<1,l,mid,L,R);
            else if(L>mid) return ask(o<<1|1,mid+1,r,L,R);
            else return (ask(o<<1,l,mid,L,mid) + ask(o<<1|1,mid+1,r,mid+1,R))%mod;
        }
    }
    LL ask(int l,int r) {
        assert(l<=r);
        return ask(1,1,n,l,r);
    }
} tree;

void prepare() {
    dfs1(1);
    dfs2(1);
    assert(tim == n);
    for(int i=1; i<=n; i++) invdfn[dfn[i]] = i;
    tree.build();
}

void add_point(int x) {
    while(x) {
        tree.add(dfn[top[x]], dfn[x]);
        x=fa[top[x]];
    }
}

LL ask(int x) {
    LL ret = 0;
    while(x) {
        ret = (ret + tree.ask(dfn[top[x]], dfn[x]))%mod;
        x=fa[top[x]];
    }
    return ret;
}

int main() {
    scanf("%d%d%d",&n,&Q,&k);
    assert(n+5 <= MAXN );
    assert(Q+5 <= MAXN );

    for(int i=2,x; i<=n; i++) {
        scanf("%d",&x);
        add(x,i);
        fa[i]=x;
    }
    for(int i=1; i<=Q; i++) {
        scanf("%d%d",&query[i].x,&query[i].y);
        query[i].id = i;
    }

    prepare();

    sort(query+1,query+Q+1,cmp_by_x);
    int p = 1;
    for(int i=1; i<=n; i++) {
        add_point(i);
        while(p <= Q && query[p].x == i) {
            ans[query[p].id] = ask(query[p].y);
            p++;
        }
    }
    assert(p==Q+1);

    for(int i=1; i<=Q; i++) {
        printf("%d\n",ans[i]);
    }

    return 0;
}

相关文章