Processing math: 14%

[洛谷 5305][GXOI/GZOI2019]旧词

题目链接

https://www.luogu.com.cn/problem/P5305

题解

本题显然是 [LNOI2014]LCA 的推广。

我们还是采用和那道题一样的方法来维护 LCA 深度和。唯一的区别就在于对 k 次方这个操作的处理上。

先思考一下 k=1 的情况,我们将路径上所有节点的值加一,究竟是为什么呢?

其实这个操作可以视为一个树上差分的操作。我们执行的修改操作,其实是给点权加上相邻两点深度的差值(k=1 时显然就是 1),而把差分数组累加起来,则就是要求的和。

理解了这一点,我们也不难把这个操作推广到 k \neq 1 的情况了。根据上文所述,对于一个深度为 dep_i 的点,我们执行一次修改操作给它的点权加上的值为 dep_i^k-(dep_i-1)^k

这样我们就完美地解决了本题。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;
struct query
{
int r,z,id;
bool operator<(const query&a)const
{
return r<a.r;
}
};
struct seg
{
long long sum,tag,ds;
}s[200005];
struct edge
{
int v,next;
}e[50005];
vector<query> q;
int n,Q,k;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005],num[50005];
int id[50005],top[50005],cnt;
int dk[50005];
long long fpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%MOD;
x=x*x%MOD;
y>>=1;
}
return ans;
}
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f)
{
siz[u]=1;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t)
{
id[u]=++cnt;
num[cnt]=u;
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD;
}
void build(int root,int l,int r)
{
if(l==r)
{
s[root].ds=dk[num[l]];
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
void pushdown(int root)
{
s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD;
s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD;
s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
s[root].tag++;
s[root].sum=(s[root].sum+s[root].ds)%MOD;
return;
}
pushdown(root);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r);
update(root<<1|1,mid+1,cr,l,r);
pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return 0;
if(l<=cl&&cr<=r)return s[root].sum;
pushdown(root);
int mid=(cl+cr)>>1;
return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y]);
}
int query_chain(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>Q>>k;
for(int i=2;i<=n;i++)
{
cin>>fa[i];
addedge(fa[i],i);
}
cnt=0;
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++)
dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD;
build(1,1,n);
for(int i=1;i<=Q;i++)
{
int r,z;
cin>>r>>z;
q.push_back({r,z,i});
}
sort(q.begin(),q.end());
int u=1;
for(auto i:q)
{
while(u<=i.r)
{
update_chain(1,u);
u++;
}
ans[i.id]=query_chain(1,i.z);
}
for(int i=1;i<=Q;i++)
cout<<(ans[i]+MOD)%MOD<<endl;
return 0;
}
#include <iostream> #include <vector> #include <algorithm> #define MOD 998244353 using namespace std; struct query { int r,z,id; bool operator<(const query&a)const { return r<a.r; } }; struct seg { long long sum,tag,ds; }s[200005]; struct edge { int v,next; }e[50005]; vector<query> q; int n,Q,k; int head[50005],ans[50005]; int siz[50005],dep[50005],son[50005],fa[50005],num[50005]; int id[50005],top[50005],cnt; int dk[50005]; long long fpow(long long x,long long y) { long long ans=1; while(y) { if(y&1)ans=ans*x%MOD; x=x*x%MOD; y>>=1; } return ans; } void addedge(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs1(int u,int f) { siz[u]=1; dep[u]=dep[f]+1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; } } void dfs2(int u,int t) { id[u]=++cnt; num[cnt]=u; top[u]=t; if(!son[u])return; dfs2(son[u],t); for(int i=head[u];i;i=e[i].next) if(e[i].v!=son[u])dfs2(e[i].v,e[i].v); } void pushup(int root) { s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD; s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD; } void build(int root,int l,int r) { if(l==r) { s[root].ds=dk[num[l]]; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); pushup(root); } void pushdown(int root) { s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD; s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD; s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD; s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD; s[root].tag=0; } void update(int root,int cl,int cr,int l,int r) { if(r<cl||cr<l)return; if(l<=cl&&cr<=r) { s[root].tag++; s[root].sum=(s[root].sum+s[root].ds)%MOD; return; } pushdown(root); int mid=(cl+cr)>>1; update(root<<1,cl,mid,l,r); update(root<<1|1,mid+1,cr,l,r); pushup(root); } int query(int root,int cl,int cr,int l,int r) { if(r<cl||cr<l)return 0; if(l<=cl&&cr<=r)return s[root].sum; pushdown(root); int mid=(cl+cr)>>1; return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD; } void update_chain(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); update(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,n,id[x],id[y]); } int query_chain(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD; x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans=(ans+query(1,1,n,id[x],id[y]))%MOD; return ans; } int main() { ios::sync_with_stdio(false); cin>>n>>Q>>k; for(int i=2;i<=n;i++) { cin>>fa[i]; addedge(fa[i],i); } cnt=0; dfs1(1,1); dfs2(1,1); for(int i=1;i<=n;i++) dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD; build(1,1,n); for(int i=1;i<=Q;i++) { int r,z; cin>>r>>z; q.push_back({r,z,i}); } sort(q.begin(),q.end()); int u=1; for(auto i:q) { while(u<=i.r) { update_chain(1,u); u++; } ans[i.id]=query_chain(1,i.z); } for(int i=1;i<=Q;i++) cout<<(ans[i]+MOD)%MOD<<endl; return 0; }
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;
struct query
{
 int r,z,id;
 bool operator<(const query&a)const
 {
  return r<a.r;
 }
};
struct seg
{
 long long sum,tag,ds;
}s[200005];
struct edge
{
 int v,next;
}e[50005];
vector<query> q;
int n,Q,k;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005],num[50005];
int id[50005],top[50005],cnt;
int dk[50005];
long long fpow(long long x,long long y)
{
 long long ans=1;
 while(y)
 {
  if(y&1)ans=ans*x%MOD;
  x=x*x%MOD;
  y>>=1;
 }
 return ans;
}
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs1(int u,int f)
{
 siz[u]=1;
 dep[u]=dep[f]+1;
 for(int i=head[u];i;i=e[i].next)
 {
  int v=e[i].v;
  dfs1(v,u);
  siz[u]+=siz[v];
  if(siz[v]>siz[son[u]])son[u]=v;
 }
}
void dfs2(int u,int t)
{
 id[u]=++cnt;
 num[cnt]=u;
 top[u]=t;
 if(!son[u])return;
 dfs2(son[u],t);
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
 s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
 s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD;
}
void build(int root,int l,int r)
{
 if(l==r)
 {
  s[root].ds=dk[num[l]];
  return;
 }
 int mid=(l+r)>>1;
 build(root<<1,l,mid);
 build(root<<1|1,mid+1,r);
 pushup(root);
}
void pushdown(int root)
{
 s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
 s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
 s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD;
 s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD;
 s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
 if(r<cl||cr<l)return;
 if(l<=cl&&cr<=r)
 {
  s[root].tag++;
  s[root].sum=(s[root].sum+s[root].ds)%MOD;
  return;
 }
 pushdown(root);
 int mid=(cl+cr)>>1;
 update(root<<1,cl,mid,l,r);
 update(root<<1|1,mid+1,cr,l,r);
 pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
 if(r<cl||cr<l)return 0;
 if(l<=cl&&cr<=r)return s[root].sum;
 pushdown(root);
 int mid=(cl+cr)>>1;
 return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y)
{
 while(top[x]!=top[y])
 {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  update(1,1,n,id[top[x]],id[x]);
  x=fa[top[x]];
 }
 if(dep[x]>dep[y])swap(x,y);
 update(1,1,n,id[x],id[y]);
}
int query_chain(int x,int y)
{
 int ans=0;
 while(top[x]!=top[y])
 {
  if(dep[top[x]]<dep[top[y]])swap(x,y);
  ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
  x=fa[top[x]];
 }
 if(dep[x]>dep[y])swap(x,y);
 ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
 return ans;
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>Q>>k;
 for(int i=2;i<=n;i++)
 {
  cin>>fa[i];
  addedge(fa[i],i);
 }
 cnt=0;
 dfs1(1,1);
 dfs2(1,1);
 for(int i=1;i<=n;i++)
  dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD;
 build(1,1,n);
 for(int i=1;i<=Q;i++)
 {
  int r,z;
  cin>>r>>z;
  q.push_back({r,z,i});
 }
 sort(q.begin(),q.end());
 int u=1;
 for(auto i:q)
 {
  while(u<=i.r)
  {
   update_chain(1,u);
   u++;
  }
  ans[i.id]=query_chain(1,i.z);
 }
 for(int i=1;i<=Q;i++)
  cout<<(ans[i]+MOD)%MOD<<endl;
 return 0;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理