P11622 [Ynoi Easy Round 2025] TEST_176 题解

插入标记回收算法的板子题。

这个算法类似扫描线，可以解决的是一些离线的函数复合维护问题，要求维护的函数可以快速对多个数字进行变换。

比如这题出现的

f_i(x)=\max(x,a_i-x)

，如果要对多个数字同时进行

x\gets f_i(x)

，我们显然用平衡树维护，然后考虑拆

\max

，这个值域分裂成两部分，一部分不变，一部分取反再整体加就行，最后套一个平衡树合并。

我们从左到右扫描，当扫描到位置

i

时：

碰到一个询问的左端点 $L=i$ ，我们就在平衡树插入这个询问的初始值 $x$ 。
接下来对于整个平衡树，所有的值都 $x\gets f_i(x)$ ，按照前面的维护方式即可。
碰到一个询问的右端点 $R=i$ ，我们在平衡树中调用当时插入的节点的编号，此时的点值显然就是答案了。

时间复杂度

\mathcal O(n\log^2n)

，瓶颈是平衡树合并。

问题是李欣隆很邪恶，这题卡常，怎么办呢？考虑平衡树合并减小常数，我们分讨值域，值域大的时候我们跑经典的随机有交合并，值域小我们跑启发式合并。

CPP

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=3e5+5;
int n,m,Rt;
struct Tree
{
	int Ls,Rs,Fa,R,P;
	LL Lz,V;
}t[N];

LL A[N],Ans[N];
mt19937 Rnd(time(0));
struct Query{LL x;int Id;};
vector<Query>Q[N],C[N];
inline void Ad(int u,LL x)
{
	if(!u)return;
	t[u].V+=x,t[u].Lz+=x;
}
inline void Rv(int u,int x)
{
	if(!u||!x)return;
	t[u].V=-t[u].V,t[u].R^=x,t[u].Lz=-t[u].Lz;
	swap(t[u].Ls,t[u].Rs);
}
inline void Down(int u)
{
	if(t[u].R!=0)Rv(t[u].Ls,t[u].R),Rv(t[u].Rs,t[u].R),t[u].R=0;
	if(t[u].Lz!=0)Ad(t[u].Ls,t[u].Lz),Ad(t[u].Rs,t[u].Lz),t[u].Lz=0;
}
inline void Up(int u)
{
	if(t[u].Ls)t[t[u].Ls].Fa=u;
	if(t[u].Rs)t[t[u].Rs].Fa=u;
}
void Mrg(int &u,int u1,int u2)
{
	if(!u1||!u2)u=u1+u2;
	else
	{
		Down(u1),Down(u2);
		if(t[u1].P<t[u2].P)u=u1,Mrg(t[u1].Rs,t[u1].Rs,u2);
		else u=u2,Mrg(t[u2].Ls,u1,t[u2].Ls);		
		Up(u);
	}
}
void Spl(int u,int &u1,int &u2,LL x)
{
	if(!u)u1=u2=0;
	else
	{
		Down(u);
		if(t[u].V<=x)u1=u,Spl(t[u].Rs,t[u].Rs,u2,x);
		else u2=u,Spl(t[u].Ls,u1,t[u].Ls,x);
		Up(u);
	}
}
LL Min(int u)
{
	while(t[u].Ls)Down(u),u=t[u].Ls;
	return t[u].V;
}
void Merg(int &z,int x,int y)
{
	z=0;
	while(x&&y){
		LL vx=Min(x),vy=Min(y);
		if(vx>vy)swap(vx,vy),swap(x,y);
		int w;Spl(x,w,x,vy);
		Mrg(z,z,w);
	}
	Mrg(z,z,x),Mrg(z,z,y);
}
LL Mx=0;
void Merge(int &u,int u1,int u2)
{
	if(Mx<=1000000)return Merg(u,u1,u2),void();
	if(!u1||!u2)u=u1+u2;
	else
	{
		Down(u1),Down(u2);
		if(t[u1].P>t[u2].P)swap(u1,u2);
		u=u1;
		int u3,u4;
		Spl(u2,u3,u4,t[u1].V);
		Merge(t[u1].Ls,t[u1].Ls,u3),Merge(t[u1].Rs,t[u1].Rs,u4);
		Up(u);
	}	
}
inline void Ins(int u,LL x)
{
	t[u].V=x,t[u].P=Rnd();
	int u1,u2;
	Spl(Rt,u1,u2,x);
	Mrg(u1,u1,u),Mrg(Rt,u1,u2);
}
inline LL Qry(int x)
{
	int h=x;
	vector<int>F;
	while(t[x].Fa)F.pb(x),x=t[x].Fa;
	F.pb(x);
	reverse(F.begin(),F.end());
	for(int i:F)Down(i);
	return t[h].V;
}
inline void Work(LL x)
{
	int u1,u2;
	Spl(Rt,u1,u2,x>>1);
	Rv(u1,1),Ad(u1,x);
	Merge(Rt,u1,u2);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&A[i]),Mx=max(Mx,A[i]);
	for(int i=1,l,r;i<=m;i++)
	{
		LL x;
		scanf("%lld%d%d",&x,&l,&r);
		Q[r].pb({x,i}),C[l].pb({x,i});
	}
	for(int i=1;i<=n;i++)
	{
		for(auto x:C[i])Ins(x.Id,x.x);
		Work(A[i]);
		for(auto x:Q[i])Ans[x.Id]=Qry(x.Id);
	}
	for(int i=1;i<=m;i++)printf("%lld\n",Ans[i]);
}

P11622 [Ynoi Easy Round 2025] TEST_176 题解

文章操作

相关推荐

评论

P11622 [Ynoi Easy Round 2025] TEST_176 题解