题解 | #奇怪的函数#

T4 奇怪的函数 题解

题目链接

Case1

当询问操作均为操作 $44$ 时。容易发现 $F(x)F(x)$ 的取值有固定范围，在此处先感性理解，具体见下面情况。

Case2

当操作序列中不存在操作 $11$ 时。

我们设一段区间的操作进行过后得到的答案范围为 $[L,R][L,R]$。我们考虑合并两个有先后顺序的区间 $aa$ 和 $bb$。

当两个区间的值域不相交时：

• 左区间值域更小。此时左区间出来的值在右区间被提拔至最小值。

  即 if(a.R<b.L)return (Tree){b.L,b.L}。

• 左区间值域更大。此时左区间出来的值在右区间被降级至最大值。

  即 if(a.L>b.R)return (Tree){b.R,b.R}。

当两个区间的值域相交时：取相交的部分。即 return (Tree){max(a.L,b.L),min(a.R,b.R)}。

我们将操作 $22$ 的值域看为 $[-inf,val][-inf,val]$，将操作 $33$ 的值域看为 $[val,inf][val,inf]$，那么所有值域合并之后得到的也是一个值域，从而证明了 $F(x)F(x)$ 的取值有固定范围。（什么垃圾证明）

Case3

无特殊性质时。

我们可以把对 $xx$ 的 $+val+val$ 操作改为先让后续操作的值域 $-val-val$，在最后计算时再将所有的 $valval$ 记入答案。

当两个区间的值域不相交时：（以下小和大均为转化后的值域意义下）

• 左区间值域更小。此时左区间出来的值在右区间被提拔至最小值。

  即 if(a.R<b.L-a.D)return (Tree){b.L-a.D,b.L-a.D,a.D+b.D}。

• 左区间值域更大。此时左区间出来的值在右区间被降级至最大值。

  即 if(a.L>b.R-a.D)return (Tree){b.R-a.D,b.R-a.D,a.D+b.D}。

当两个区间的值域相交时：取相交的部分。即 return (Tree){max(a.L,b.L-a.D),min(a.R,b.R-a.D),a.D+b.D}。

那么最后求答案时只要判断 $xx$ 所在区域，加上全局 $valval$ 值总和就可以得到答案。

附上代码：

#include<bits/stdc++.h>
#define Max(a,b) ((a<b)&&(a=b))
#define Min(a,b) ((a>b)&&(a=b))
using namespace std;

const int M=1e5+5;
const int inf=0x3f3f3f3f;

inline int read()
{
	int x=0,f=1;static char ch;
	while(ch=getchar(),ch<48)if(ch ==45)f=0;
	do x=(x<<1)+(x<<3)+(ch^48);
	while(ch=getchar(),ch>=48);
	return f?x:-x;
}

int n,q;
struct Tree
{
	int L,R,D;
	#define ls p<<1
	#define rs p<<1|1
	Tree operator+(const Tree&t)const
	{
		if(R<t.L-D)return (Tree){t.L-D,t.L-D,D+t.D};
		if(L>t.R-D)return (Tree){t.R-D,t.R-D,D+t.D};
		return (Tree){max(L,t.L-D),min(R,t.R-D),D+t.D};
	}
}t[M<<2];
void update(int p,int l,int r,int op,int x,int v)
{
	if(l==r)
	{
		if(op==1)t[p]=(Tree){-inf,inf,v};
		if(op==2)t[p]=(Tree){-inf,v,0};
		if(op==3)t[p]=(Tree){v,inf,0};
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(ls,l,mid,op,x,v);
	else update(rs,mid+1,r,op,x,v);
	t[p]=t[ls]+t[rs];
}
int calc(int val)
{
	if(val<t[1].L)return t[1].L+t[1].D;
	if(val>t[1].R)return t[1].R+t[1].D;
	return val+t[1].D;
}

int main()
{
	n=read();
	for(int i=1,op,val;i<=n;i++)
	{
		op=read(),val=read();
		update(1,1,n,op,i,val);
	}
	q=read();
	for(int i=1,op,pos,val;i<=q;i++)
	{
		op=read();
		if(op==4)val=read(),printf("%d\n",calc(val));
		else pos=read(),val=read(),update(1,1,n,op,pos,val);
	}
	
	return 0;
}