M_sea

洛谷5305 [GXOI/GZOI2019]旧词
LuoguBZOJLOJ分析树链剖分+线段树。先要知道 $k=1$ 怎么做。这一部分是一个原题,戳这里。考虑 $k...
扫描右侧二维码阅读全文
30
2019/04

洛谷5305 [GXOI/GZOI2019]旧词

Luogu

BZOJ

LOJ

分析

树链剖分+线段树。


先要知道 $k=1$ 怎么做。

这一部分是一个原题,戳这里


考虑 $k>1$ 的情况。

为什么 $k=1$ 时加的是 $1$ 呢?这个 $1$ 实际上是差分后的结果,也就是 $dep[u]^1-(dep[u]-1)^1$ 。

那么我们只要把 $1$ 换成 $dep[u]^k-(dep[u]-1)^k$ 即可。

预处理出线段树上每个节点对应的这个东西的和,就可以做了。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int mod=998244353;

int n,Q,k;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

struct Edge { int v,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

struct Query { int x,z,id,w; } q[N];
bool operator <(Query a,Query b) { return a.x<b.x; }
int tot=0;

int val[N],dep[N],fa[N],sz[N],hson[N],top[N],dfn[N],rl[N],tim=0;

inline void dfs1(int u,int f) {
    dep[u]=dep[f]+1,fa[u]=f,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,rl[tim]=u;
    if (!hson[u]) return;
    dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

struct Segment_Tree {
#define ls (o<<1)
#define rs (o<<1|1)
    
    int add[N<<2],sum[N<<2],val[N<<2];
    
    inline void pushup(int o) { sum[o]=(sum[ls]+sum[rs])%mod; }
    inline void pushdown(int o) {
        if (add[o]) {
            add[ls]+=add[o],add[rs]+=add[o];
            sum[ls]=(sum[ls]+1ll*val[ls]*add[o])%mod;
            sum[rs]=(sum[rs]+1ll*val[rs]*add[o])%mod;
            add[o]=0;
        }
    }

    inline void build(int o,int l,int r) {
        if (l==r) {
            val[o]=(qpow(dep[rl[l]],k)-qpow(dep[rl[l]]-1,k)+mod)%mod;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        val[o]=(val[ls]+val[rs])%mod;
    }
    
    inline void update(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) {
            ++add[o],sum[o]=(sum[o]+val[o])%mod;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(o);
        if (ql<=mid) update(ls,l,mid,ql,qr);
        if (qr>mid) update(rs,mid+1,r,ql,qr);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sum[o];
        int mid=(l+r)>>1,res=0;
        pushdown(o);
        if (ql<=mid) res=(res+query(ls,l,mid,ql,qr))%mod;
        if (qr>mid) res=(res+query(rs,mid+1,r,ql,qr))%mod;
        pushup(o);
        return res;
    }

#undef ls
#undef rs
} T;

inline void modify(int u,int v) {
    int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        T.update(1,1,n,dfn[tu],dfn[u]);
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    T.update(1,1,n,dfn[v],dfn[u]);
}

inline int query(int u,int v) {
    int tu=top[u],tv=top[v],res=0;
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        res=(res+T.query(1,1,n,dfn[tu],dfn[u]))%mod;
        u=fa[tu],tu=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    res=(res+T.query(1,1,n,dfn[v],dfn[u]))%mod;
    return res;
}

int ans[N];

int main() {
    n=read(),Q=read(),k=read();
    for (re int i=2;i<=n;++i) addEdge(read(),i);
    dfs1(1,0); dfs2(1,1); T.build(1,1,tim);
    for (re int i=1;i<=Q;++i) {
        int x=read(),z=read();
        q[++tot]=(Query){x,z,i,1};
    }
    sort(q+1,q+tot+1);
    for (re int i=1,j=1;i<=tot;++i) {
        if (!q[i].x) continue;
        while (j<=q[i].x) modify(1,j),++j;
        ans[q[i].id]=(ans[q[i].id]+q[i].w*query(1,q[i].z)+mod)%mod;
    }
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]%mod);
    return 0;
}
最后修改:2019 年 05 月 26 日 10 : 01 PM

发表评论