首页 > 其他分享 >【解题报告】[LNOI 2014] LCA/[GXOI/GZOI 2019] 旧词

【解题报告】[LNOI 2014] LCA/[GXOI/GZOI 2019] 旧词

时间：2022-10-10 12:11:22浏览次数：78  
标签：int top GZOI deep tag 2019 GXOI ans mod

【省选系列】[LNOI 2014] LCA/[GXOI/GZOI 2019] 旧词

首黑祭，好耶！

[LNOI 2014]LCA

首先考虑，每个节点对答案的贡献，我们可以发现LCA一定会在z到根节点的路径上，每个节点每次增加的贡献应该为\(deep[i]-(deep[i]-1)=1\)，所以我们可以在区间[l,r]内的所有节点到根节点的路径上的点权增加1，不难发现每次查询的结果为z到根节点路径上的权值之和（本质上可以看做树上差分），考虑树剖+线段树

但是对于每次查询，我们都要重新建树并清空线段树，时间复杂度\(O(m*nlog^2n)\)显然会超时，我们可以考虑对区间进行差分，将每个询问区间[l,r]变为[1,l-1],[1,r]，然后对每个区间按右端点进行排序，随后不断向询问中加入右端点，如果加入的点恰好是拆分出的区间的右端点我们就记录答案（1->z），最后的结果为ans_r-ans_l(此处的ans_l指的是l-1)，可以将时间复杂度优化为\(O(nlog^2n)\)

AC code

点击查看代码 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=50010;

const int mod=201314;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

int fa[maxn],head[maxn];

int id[maxn],siz[maxn];

int top[maxn],deep[maxn];

int n,m,tot,max_son[maxn];

struct edge
{
	int to,next;
}e[maxn*2];

struct s_t
{
	int l,r;
	int val;
	int tag;
}t[maxn*4];

struct que
{
	int ans_l,ans_r;
}q[maxn];

struct ques
{
	int id,r,z;
	bool check;
}qu[maxn*2];

void add(int x,int y)
{
	e[++tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}

void dfs_first(int x,int f)
{
	siz[x]=1;fa[x]=f;
	deep[x]=deep[f]+1;
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==f) continue;
		dfs_first(to,x);
		siz[x]+=siz[to];
		if(siz[to]>siz[max_son[x]]) max_son[x]=to;
	}
}

void dfs_second(int x,int t)
{
	id[x]=++tot;top[x]=t;
	if(max_son[x]==0) return ;
	dfs_second(max_son[x],top[x]);
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to!=fa[x] && to!=max_son[x]) dfs_second(to,to);
	}
}

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}

void push_down(int p)
{
	if(t[p].tag)
	{
		t[p*2].val=(t[p*2].val+(t[p*2].r-t[p*2].l+1)*t[p].tag)%mod;
		t[p*2].tag=(t[p*2].tag+t[p].tag)%mod;
		t[p*2+1].val=(t[p*2+1].val+(t[p*2+1].r-t[p*2+1].l+1)*t[p].tag)%mod;
		t[p*2+1].tag=(t[p*2+1].tag+t[p].tag)%mod;
		t[p].tag=0;
	}
}

void update(int p,int l,int r)
{
	if(l<=t[p].l && t[p].r<=r)
	{
		t[p].val=(t[p].val+(t[p].r-t[p].l+1))%mod;
		t[p].tag=(t[p].tag+1)%mod;	return ;
	}
	push_down(p);
	int mid=(t[p].r+t[p].l)>>1;
	if(l<=mid) update(p*2,l,r);
	if(r>mid) update(p*2+1,l,r);
	t[p].val=(t[p*2].val+t[p*2+1].val)%mod;
}

int query(int p,int l,int r)
{
	if(l<=t[p].l && t[p].r<=r) return t[p].val%mod;
	push_down(p);
	int mid=(t[p].l+t[p].r)>>1;
	int ans=0;
	if(l<=mid) ans=(ans+query(p*2,l,r))%mod;
	if(r>mid) ans=(ans+query(p*2+1,l,r))%mod;
	return ans;
}

void change(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		}
		update(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	update(1,id[x],id[y]);
}

int get_sum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		}
		ans=(ans+query(1,id[top[x]],id[x]))%mod;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	ans=(ans+query(1,id[x],id[y]))%mod;
	return ans%mod;
}

bool cmp(ques x,ques y)
{
	return x.r<y.r;
}

int main()
{
	n=read();m=read();
	
	for(int i=2;i<=n;i++)
	{
		int k=read()+1;
		add(k,i);add(i,k);
	}
	tot=0,dfs_first(1,0);
	tot=0,dfs_second(1,1);
	build(1,1,n);
	
	int cnt=0;
	
	for(int i=1;i<=m;i++)
	{
		int l=read()+1;
		int r=read()+1;
		int z=read()+1;
		qu[++cnt]={i,l-1,z,0};
		qu[++cnt]={i,r,z,1};
	}
	
	sort(qu+1,qu+cnt+1,cmp);

	int now=0;

	for(int i=1;i<=cnt;i++)
	{
		while(now<qu[i].r)
		{
			change(1,++now);
		}
		int id=qu[i].id;
		if(qu[i].check==0)
		{
			q[id].ans_l=get_sum(1,qu[i].z);
		}
		else
		{
			q[id].ans_r=get_sum(1,qu[i].z);
		}
	}

	for(int i=1;i<=m;i++)
	{
		cout<<(q[i].ans_r-q[i].ans_l+mod)%mod<<'\n';
	}

	return 0;
}

[GXOI/GZOI 2019]旧词

相对于上一道题目而言，这道题目只是将维护的变为\(deep^k\),想到之前计算贡献的方法\(deep[i]^1-(deep[i]-1)^1=1\)

所以此处产生的贡献为\(deep[i]^k-(deep[i]-1)^k\)，将幂预处理出来，建树时将对应的贡献预处理，然后线段树维护的操作变为了区间加贡献，区间查询，就可以切黑题力

AC code

点击查看代码 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define int long long

using namespace std;

const int maxn=50010;

const int mod=998244353;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

int A[maxn],rev[maxn];

int fa[maxn],head[maxn];

int id[maxn],siz[maxn];

int top[maxn],deep[maxn];

int n,m,k,tot,max_son[maxn];

struct edge
{
	int to,next;
}e[maxn*2];

struct s_t
{
	int l,r;
	int val;
	int sum;
	int tag;
}t[maxn*4];

struct que
{
	int ans;
}q[maxn];

struct ques
{
	int id,r,z;
}qu[maxn*2];

void add(int x,int y)
{
	e[++tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}

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

void dfs_first(int x,int f)
{
	siz[x]=1;fa[x]=f;
	deep[x]=deep[f]+1;
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==f) continue;
		dfs_first(to,x);
		siz[x]+=siz[to];
		if(siz[to]>siz[max_son[x]]) max_son[x]=to;
	}
}

void dfs_second(int x,int t)
{
	id[x]=++tot;top[x]=t;rev[tot]=x;
	if(max_son[x]==0) return ;
	dfs_second(max_son[x],top[x]);
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to!=fa[x] && to!=max_son[x]) dfs_second(to,to);
	}
}

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r)
	{
		t[p].val=(A[deep[rev[l]]]-A[deep[rev[l]]-1]+mod)%mod;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].val=(t[p*2].val+t[p*2+1].val)%mod;
}

void push_down(int p)
{
	if(t[p].tag)
	{
		t[p*2].sum=(t[p*2].sum+(t[p*2].val*t[p].tag)%mod)%mod;
		t[p*2].tag=(t[p*2].tag+t[p].tag)%mod;
		t[p*2+1].sum=(t[p*2+1].sum+(t[p*2+1].val*t[p].tag)%mod)%mod;
		t[p*2+1].tag=(t[p*2+1].tag+t[p].tag)%mod;
		t[p].tag=0;
	}
}

void update(int p,int l,int r)
{
	if(l<=t[p].l && t[p].r<=r)
	{
		t[p].sum=(t[p].sum+t[p].val)%mod;
		t[p].tag++;	return ;
	}
	push_down(p);
	int mid=(t[p].r+t[p].l)>>1;
	if(l<=mid) update(p*2,l,r);
	if(r>mid) update(p*2+1,l,r);
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}

int query(int p,int l,int r)
{
	if(l<=t[p].l && t[p].r<=r) return t[p].sum%mod;
	push_down(p);
	int mid=(t[p].l+t[p].r)>>1;
	int ans=0;
	if(l<=mid) ans=(ans+query(p*2,l,r))%mod;
	if(r>mid) ans=(ans+query(p*2+1,l,r))%mod;
	return ans%mod;
}

void change(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		}
		update(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	update(1,id[x],id[y]);
}

int get_sum(int x,int y)
{
	int ans=0;
	while(top[x]!=top[y])
	{
		if(deep[top[x]]<deep[top[y]])
		{
			swap(x,y);
		}
		ans=(ans+query(1,id[top[x]],id[x]))%mod;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y]) swap(x,y);
	ans=(ans+query(1,id[x],id[y]))%mod;
	return ans%mod;
}

bool cmp(ques x,ques y)
{
	return x.r<y.r;
}

signed main()
{
	n=read();m=read();k=read();
	
	for(int i=1;i<=n;i++)
	{
		A[i]=qpow(i,k)%mod;
	}
	
	for(int i=2;i<=n;i++)
	{
		int u=read();
		add(u,i);add(i,u);
	}
	tot=0,dfs_first(1,0);
	tot=0,dfs_second(1,1);
	build(1,1,n);
	
	int cnt=0;
	
	for(int i=1;i<=m;i++)
	{
		int r=read();
		int z=read();
		qu[++cnt]={i,r,z};
	}
	
	sort(qu+1,qu+cnt+1,cmp);

	int now=0;

	for(int i=1;i<=cnt;i++)
	{
		while(now<qu[i].r)
		{
			change(1,++now);
		}
		int id=qu[i].id;
		q[id].ans=get_sum(1,qu[i].z);
	}

	for(int i=1;i<=m;i++)
	{
		cout<<(q[i].ans)%mod<<'\n';
	}

	return 0;
}

标签：int,top,GZOI,deep,tag,2019,GXOI,ans,mod
From： https://www.cnblogs.com/SitoASK/p/16775176.html

相关文章

  • [LOJ3138] [COI2019] LJEPOTICA
    非常简单数位dp。先差分转成前缀询问，然后记录状态\(dp_{p,num,hv,pre}\)表示当前考虑到第\(p\)位，还剩\(num\)次改变定义的机会，\(hv\)表示这一位是否考虑大小限......
  • VS2019 下载NUGet包 本地安装 但没有成功
    1、下载：在网址https://www.nuget.org/中找对应的包版本 2、新建程序包源地址，其地址设置为下载的本地包地址：E:\NuGet离线包；点击更新   3、在程序包管理控制......
  • Windows Server 2019远程控制的配置与管理方法
    1、WindowsServer远程桌面功能在企业中服务器一般被寄存在专门的IDC机房中，这些机房在固定的地点，可能距离企业距离很远。但是大部分服务器需要定期维护，如果每次维护时，系统......
  • winserver2019不重装系统，对磁盘进行重新划分
    不重装系统进行分盘刚开始只有一块儿磁盘C盘，需要将C盘拆分成C盘和D盘第一步在c盘出右键->压缩卷压缩的大小为，总大小减去需要为原有的C盘剩余的大小，毕业C盘总大小为4......
  • UML建模工具更新情况（2019下半年-2020）（一）
    工具最新版本：EnterpriseArchitect15.1RC更新时间：​2020年1月9日​​工具最新版本：​VisualParadigmforUML16.1更新时间：​2019年12月2日​ 工具最新版本：AstahUML8.2......
  • UML建模工具更新情况（2019下半年-2020）（二）
    工具最新版本：BOUML7.9更新时间：2019年7月15日工具最新版本：SinelaboreRT4.0更新时间：2019年9月工具最新版本：SoftwareIdeasModeler12.06更新时间：2020年1月10日工具最新版本......
  • BUUCTF—ciscn_2019_n_1
    先看看开了什么保护机制打开64位ida看看如果v2为11.28125，那么就执行system（"cat/flag"），这样就可以得到flag了，然后发现v2是局部变量，在栈上，然后还有个gets的栈溢出，所以这......
  • Microsoft word 2019 for Mac中文激活版
    Microsoftword2019是功能强大的文档编辑工具，被认为是office的主要程序，拥有文字搜索、导航、文档的编辑共享、重点部分的标注等多种功能，word拥有视图学些功能，字体的颜色变......
  • VS 2019设置中文提示
    汉化包下载官方地址https://dotnet.microsoft.com/zh-cn/download/intellisense 解压   解压后将文件zh-hans放到（VS2019默认安装路径）C:\ProgramFiles\d......
  • 2019上半年（上午）网络工程师试题解析
    2019上半年（上午）网络工程师试题解析1.计算机执行指令的过程中，需要由( )产生每条指令的操作信号，并将信号送往相应的部件进行处理，以完成指定的操作。A.CPU的控制器 B.CPU的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99