首页 > 其他分享 >[Ynoi2007]rfplca/[CF1491H] Yuezheng Ling and Dynamic Tree

[Ynoi2007]rfplca/[CF1491H] Yuezheng Ling and Dynamic Tree

时间:2023-12-21 14:46:26浏览次数:35  
标签:CF1491H Yuezheng int Dynamic Ynoi tp leq tg 操作

题目描述

给定一棵大小为 \(n\) 的 \(1\) 为根节点的树,树用如下方式给出:输入 \(a_2,a_3,\dots,a_n\),保证 \(1\leq a_i<i\),将 \(a_i\) 与 \(i\) 连边形成一棵树。

接下来有 \(m\) 次操作,操作有两种:

  • 1 l r x 令 \(a_i=\max(a_i-x,1)(l\leq i\leq r)\)。
  • 2 u v 查询在当前的 \(a\) 数组构成的树上 \(u,v\) 的 LCA。

输入格式

第一行包含两个数 \(n\),\(m\)。

之后一行 \(n-1\) 个数,表示 \(a_2,...,a_n\)。

之后 \(m\) 行,每行三个或四个数,表示一次操作。

本题强制在线,所有输入的 \(l,r,x,u,v\) 均需要异或 \(lastans\),其定义为上一次询问操作得到的答案,若之前没有询问操作,则为 \(0\)。

输出格式

对于每个 \(2\) 操作,输出一行一个数表示答案。

样例 #1

样例输入 #1

6 4
1 2 3 3 4
2 3 4
1 1 0 2
2 6 5
2 1 0

样例输出 #1

3
3
1

提示

Idea:Ynoi,Solution:Ynoi,Code:Ynoi,Data:Ynoi&nzhtl1477

对于 \(100\%\) 的数据,满足
\(2\leq n,q\leq 4\times 10^5\),\(2\leq l\leq r\leq n\),\(1\leq x\leq 4\times 10^5\),\(1\leq u,v\leq n\)。

考虑如何进行求 lca 这个操作。正常的维护肯定是要 LCT 的,但是 LCT 难以支持区间减这种操作。考虑分块。

为什么道题会想到分块呢?因为他是Ynoi由于保证 \(a_i<i\)(操作后更是),所以每个点到根的链都是由 \(\sqrt n\) 个关键链组成的,那么就可以像树剖那样暴力跳,直到跳到关键链顶相同后再暴力跳父亲。复杂度 \(O(\sqrt{n})\)。

那么现在的关键任务就是对每个点维护 \(tp_i\) 表示 \(i\) 所在的关键链的链顶,而一个点的父亲是容易用分块维护的。这样子就可以实现求 lca 的操作。

\(tp_i\) 看起来很难维护,但是由于 \(a_i\) 只减不增,而且当 \(a\) 已经小于这个块最小的点的时候,\(tp_i=i\),所以 \(tp\) 是均摊会改变 \(O(n\sqrt n)\) 次的。

对于每个块,记录下他还有哪些点满足 \(a_i\) 大于等于块中的最小点,那么每次把这些点暴力改掉就行了。

时间复杂度 \(O(n\sqrt n)\),空间复杂度 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
const int B=650,N=4e5+5;
int a[N],ls,n,m,tg[N],tp[N],s[B][B],k[B],g[N],q,op,l,r,x;
int ask(int x)
{
	return max(1,g[x]-tg[x/B]);
}
void upd(int u,int l,int r,int x)
{
	if(l==u*B&&r==u*B+B-1)
		tg[u]=min(n,tg[u]+x);
	else
		for(int j=l;j<=r;j++)
			g[j]=max(g[j]-x,1);
	for(int j=1;j<=k[u];j++)
	{
		if(l<=s[u][j]&&s[u][j]<=r)
		{
			a[s[u][j]]=max(a[s[u][j]]-x,1);
			if(a[s[u][j]]<u*B||a[s[u][j]]==1)
			{
				if(a[s[u][j]]<u*B)
					tp[s[u][j]]=s[u][j];
				else
					tp[s[u][j]]=1;
				for(int i=j;i<k[u];i++)
					s[u][i]=s[u][i+1];
				--k[u],--j;
			}
			else
				tp[s[u][j]]=tp[a[s[u][j]]];
		}
		else
			tp[s[u][j]]=tp[a[s[u][j]]];
	}
}
void upd(int l,int r,int x)
{
	if(l/B==r/B)
		upd(l/B,l,r,x);
	else
	{
		upd(l/B,l,l/B*B+B-1,x);
		for(int i=l/B+1;i<r/B;i++)
			upd(i,i*B,i*B+B-1,x);
		upd(r/B,r/B*B,r,x);
	}
}
int ask(int u,int v)
{
	while(tp[u]^tp[v])
	{
		if(tp[u]<tp[v])
			swap(u,v);
		u=ask(tp[u]);
	}
	while(u^v)
	{
//		if(q==984)
//			printf("qzmlovehjh:%d %d\n",u,v);
		if(u<v)
			swap(u,v);
		u=ask(u);
	}
	return u;
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("b.out","w",stdout);
	scanf("%d%d",&n,&q);
	tp[1]=1;
	for(int i=2;i<=n;i++)
	{
		scanf("%d",a+i),g[i]=a[i];
		if(a[i]<i/B*B)
			tp[i]=i;
		else if(a[i]==1)
			tp[i]=1;
		else
			tp[i]=tp[a[i]],s[i/B][++k[i/B]]=i;
	}
	while(q--)
	{
		scanf("%d",&op);
		if(op==1)
			scanf("%d%d%d",&l,&r,&x),upd(l^ls,r^ls,x^ls);
		else
			scanf("%d%d",&l,&r),printf("%d\n",ls=ask(l^ls,r^ls));
	}
}

标签:CF1491H,Yuezheng,int,Dynamic,Ynoi,tp,leq,tg,操作
From: https://www.cnblogs.com/mekoszc/p/17917938.html

相关文章

  • Feedback Control of Dynamic Systems_P1
    GLOBALEDITION1.FeedbackControlofDynamicSystemsEIGHTHEDITIONFranklin\(\cdot\)Powell\(・\)Emami-NaeiniTableofLaplaceTransformsNumber$$F(s)$$$$f(t),t\geq0$$11$$\delta(t)$$2$$\frac{1}{s}$$$$1(t)$$3$$\frac{1}{s......
  • Feedback Control of Dynamic Systems_P2
    187.ProblemsforSection5.4:DesignUsingDynamicCompensation5.21Let\[G(s)=\frac{1}{s^{2}+7s+12}\\text{~}\text{and}\text{~}\D_{c}(s)=K\frac{(s+a)}{s+b}\]Usingroot-locustechniques,findthevaluesfortheparameters\(a,b\......
  • The Main Idea of Basic Dynamic Programming Side A
    Front对zjk的BasicDynamicProgrammingSideA的补充、总结以及Code。SideA:DP状态设计。常见的DP状态树树上DP常见的状态是考虑子树内的情况,然后通过子树的状态向上合并。复杂度一般是\(O(n^3)\),一些特殊的DP转移方程通常可以通过分析优化掉一个\(n\)。......
  • freesql orm 使用 DynamicFilterInfo 拼接日期查询条件时间格式一个难得的经验
    文本到时间条件的转换前端输入1253-3,后台提示"varchar数据类型到datetime数据类型的转换产生一个超出范围的值"经查询,mssql【datetime】数据类型:最大是9999年12月31日,最小是1753年1月1日所以要拼接限制一下,只是if(val.ToDate()<DateTime.MinValue||val.ToDa......
  • Could not load dynamic library 'libnvinfer.so.7' 解决方法
    1.首先安装TensorRTpipinstalltensorrt2.找到tensorrt_libs目录,一般在~/.local/lib/python3.10/site-packages/tensorrt_libs/。目录下可以看到libnvinfer.so.8等文件注:有些教程说的是tensorrt目录,但是我在这个目录下面没找到文件3.创建symbollinks,这样TensorFlow才能找到......
  • Solving 0/1 knapsack problem with dynamic programming (英语课汇报)
    Solving0/1knapsackproblemwithdynamicprogrammingIntroduction0/1knapsackproblemsAlongtimeago,anexplorerwenttoanislandwherethereweretreasures,buthisknapsackcouldonlyholdamaximumweightof\(W\).Eachtreasurehaditscorresp......
  • Dynamic CRM 组织服务对Word模版生成PDF文件
    目的:解决用户手动下载word模版再上传问题解决方案:组织服务直接对指定的word模版文件生成PDF文件流1.word模版必须上传到系统文档模版后:设置->模版->文档模版 2.组织调用“ExportpdfDocument”,返回PDF文件字节信息。另外实体信息需要把“注释”勾选上,否则执行代码会报错,如下:......
  • es定制 dynamic mapping template(type)
    定制dynamicmappingtemplate(type)PUT/my_index{"mappings":{"my_type":{"dynamic_templates":[{"en":{"match":"*_en","match_mapping_type":"string","mapping&quo......
  • C# 22H2之后的windows版本使用SetDynamicTimeZoneInformation设置时区失败处理
    使用SetDynamicTimeZoneInformation设置时区返回false,设置失败。使用PowerShell设置Set-TimeZone成功。///<summary>///设置本地时区///参数取值"ChinaStandardTime",即可设置为中国时区///</summary>///<paramname="timeZoneId"></param>///<retur......
  • asp.net core api 3.1 dynamic 入参转json对象
    比如接口publicobjectGetList(dynamicobj){//varjElement=(JsonElement)obj;//使用system.text.json处理varstr=obj.GetRawText(); if(val!=JsonValueKind.Undefined&&val!=JsonValueKind.Null)           {if(obj.valueKind==JsonValueKind.Array)......