考虑k=1的做法:这是一道原题,我还写过题解,其实挺水的,但当时我菜还是看题解的:https://www.cnblogs.com/hfctf0210/p/10187947.html。其实就是树上差分后值为1。
考虑k>1的做法:其实可以再次树上差分,给每个点i赋值v[i]=dep[i]k-dep[i-1]k,然后还是和原来一样开一棵线段树,记录一个val[rt]表示当前节点内区间v值的和,以及sum[rt]表示区间值。修改时打标记,只需要将sum[rt]+=v*val[rt],lazy[rt]+=v即可。树剖一下即可。
#include<bits/stdc++.h>#define lson l,mID,rt<<1#define rson mID+1,r,rt<<1|1using @R_301_6889@space std;typedef pair<int,int>pii;const int N=51000,mod=998244353;int n,Q,k,cnt,dep[N],fa[N],pw[N],sz[N],son[N],top[N],ID[N],dfx[N];int ans[N],sum[N<<2],val[N<<2],lazy[N<<2];vector<int>G[N];vector<pii>vec[N];int qpow(int a,int b){ int ret=1; while(b) { if(b&1)ret=1ll*ret*a%mod; a=1ll*a*a%mod,b>>=1; } return ret;}voID dfs(int u){ dep[u]=dep[fa[u]]+1,sz[u]=1; for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]) { dfs(G[u][i]),sz[u]+=sz[G[u][i]]; if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i]; }}voID dfs2(int u,int tp){ top[u]=tp,ID[u]=++cnt,dfx[cnt]=u; if(son[u])dfs2(son[u],tp); for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa[u]&&G[u][i]!=son[u])dfs2(G[u][i],G[u][i]);}voID build(int l,int r,int rt){ if(l==r){val[rt]=pw[dep[dfx[l]]];return;} int mID=l+r>>1; build(lson),build(rson); val[rt]=(val[rt<<1]+val[rt<<1|1])%mod;}voID pushdown(int rt){ if(!lazy[rt])return; int v=lazy[rt];lazy[rt]=0; lazy[rt<<1]=(lazy[rt<<1]+v)%mod,sum[rt<<1]=(sum[rt<<1]+1ll*v*val[rt<<1])%mod; lazy[rt<<1|1]=(lazy[rt<<1|1]+v)%mod,sum[rt<<1|1]=(sum[rt<<1|1]+1ll*v*val[rt<<1|1])%mod;}voID update(int L,int R,int l,int rt){ if(L<=l&&r<=R){lazy[rt]++,sum[rt]=(sum[rt]+val[rt])%mod;return;} pushdown(rt); int mID=l+r>>1; if(L<=mID)update(L,R,lson); if(R>mID)update(L,rson); sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;}voID Update(int u){ while(top[u]!=1)update(ID[top[u]],ID[u],1,n,1),u=fa[top[u]]; update(1,1);}int query(int L,int rt){ if(L<=l&&r<=R)return sum[rt]; pushdown(rt); int mID=l+r>>1,ret=0; if(L<=mID)ret=(ret+query(L,lson))%mod; if(R>mID)ret=(ret+query(L,rson))%mod; return ret;}int query(int u){ int ret=0; while(top[u]!=1)ret=(ret+query(ID[top[u]],1))%mod,u=fa[top[u]]; ret=(ret+query(1,1))%mod; return ret;}int main(){ scanf("%d%d%d",&n,&Q,&k); for(int i=1;i<=n;i++)pw[i]=(qpow(i,k)-qpow(i-1,k)+mod)%mod; for(int i=2;i<=n;i++)scanf("%d",&fa[i]),G[fa[i]].push_back(i); dfs(1),dfs2(1,1); build(1,1); for(int i=1,x,y;i<=Q;i++)scanf("%d%d",&x,&y),vec[x].push_back(pii(y,i)); for(int i=1;i<=n;i++) { Update(i); for(int j=0;j<vec[i].size();j++)ans[vec[i][j].second]=query(vec[i][j].first); } for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);}VIEw Code 总结
以上是内存溢出为你收集整理的[GX/GZOI2019]旧词(树上差分+树剖+线段树)全部内容,希望文章能够帮你解决[GX/GZOI2019]旧词(树上差分+树剖+线段树)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)