自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:30:54，当前版本为作者最后更新于2021-05-30 20:36:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

在校内 $\text{OJ}$ 看到的一道题，在 $\text{Luogu}$ 找到了，发现没有题解，于是来写一个。

sto zltzlt orz.

题意

给你一个序列 $a$，支持 $4$ 个操作：

• $\text{merge x e}$，删除结点 $x,x+1$，在 $x$ 的位置插入一个节点，权值为 $e$；
• $\text{insert x e}$，在 $x$ 和 $x+1$ 之间插入一个节点，权值为 $e$；
• $\text{max l r}$，查询区间 $[l,r]$ 中任意子区间的区间极差的最大值；
• $\text{min l r}$，查询区间 $[l,r]$ 中任意子区间的区间极差的最小值。

$1\le n,m\le 10^5$.

思路

看到插入、删除就可以想到使用文艺平衡树来解决问题，这里我使用 $\text{Splay}$，操作 $1,2$ 十分显然。

$3$ 操作可以直接维护区间的最大值和最小值，答案就是它们做差。

$4$ 操作中，我们设答案的子区间为 $[l',r']$，设其中最大值为 $a$，最小值为 $b$，若区间中加入一个数 $v$，则 $a\gets \max(a,v),b\gets\min(b,v),\max(a,v)-\min(b,v)\ge a-b$，即插入一个数显然不会更优，所以答案区间长度为 $2$。所以我们可以维护每个数与其左右的差的绝对值，分别设为 $lb_x,rb_x$，再维护 $ms_x$ 代表 $x$ 子树内 $lb,rb$ 的最小值，答案即为 $ms$。注意需要特判 $l+1=r$ 的情况，直接取 $rb_l$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=5e5+10,INF=1e9+10;
int s[N];
int n,m;
struct Splay{
	#define ls a[x].son[0]
	#define rs a[x].son[1]
	int rt,sz;
	struct node{
		int f,val,son[2],sz;
		int minn=INF,maxn,lb,rb,ms;
		inline void clear(){
			f=maxn=son[0]=son[1]=val=sz=0;
			minn=ms=lb=rb=INF;
		}
	}a[N];
	inline bool isr(int x){return a[a[x].f].son[1]==x;}
	inline void upd(int x){
		node &p=a[x];
		p.maxn=p.minn=p.val;
		p.ms=min(p.lb,p.rb);
		if(ls) p.maxn=max(p.maxn,a[ls].maxn),p.minn=min(p.minn,a[ls].minn),p.ms=min(p.ms,a[ls].ms);
		if(rs) p.maxn=max(p.maxn,a[rs].maxn),p.minn=min(p.minn,a[rs].minn),p.ms=min(p.ms,a[rs].ms);
		p.sz=a[ls].sz+1+a[rs].sz;
	}
	inline int newnode(int v){
		sz++;
		a[sz].minn=a[sz].maxn=a[sz].val=v;
		return sz;
	}
	inline void rotate(int x){
		int f=a[x].f,gf=a[f].f;
		int id=isr(x);
		a[f].son[id]=a[x].son[id^1];
		a[a[f].son[id]].f=f;
		a[x].son[id^1]=f;
		a[f].f=x;
		a[x].f=gf;
		if(gf){
			a[gf].son[a[gf].son[1]==f]=x;
		}
		upd(f);
	}
	inline void splay(int x,int goal=0){
		goal=a[goal].f;
		for(int f;(f=a[x].f)!=goal;rotate(x)){
			if(a[f].f!=goal){
				rotate(isr(x)==isr(f)?f:x);
			}
		}
		if(!goal)
		rt=x;
	}
	inline int build(int l,int r,int f){
		if(l>r)return 0;
		int mid=l+r>>1;
		sz++;
		int now=sz;
		a[now].f=f;
		a[now].val=s[mid];
		a[now].lb=mid?abs(s[mid]-s[mid-1]):INF;
		a[now].rb=mid!=n+1?abs(s[mid]-s[mid+1]):INF;
		a[now].son[0]=build(l,mid-1,now);
		a[now].son[1]=build(mid+1,r,now);
		upd(now);
		return now;
	}
	inline int find(int x){
		int now=rt;
		while(1){
			if(x<=a[a[now].son[0]].sz){
				now=a[now].son[0];
			}else{
				x-=a[a[now].son[0]].sz+1;
				if(!x){
					return now;
				}
				now=a[now].son[1];
			}
		}
	}
	inline int split(int l,int r){
		int x=find(l);
		splay(x,rt);
		int y=find(r+2);
		splay(y,a[x].son[1]);
		return a[y].son[0];
	}
	inline void MoMerge(int wz,int v){
		int x=split(wz,wz+1),f=rt,y=a[f].son[1];
		a[x].val=v;
		if(ls) a[ls].clear(),ls=0;
		if(rs) a[rs].clear(),rs=0;
		a[f].rb=a[x].lb=abs(v-a[f].val);
		a[x].rb=a[y].lb=abs(v-a[y].val);
		upd(x),upd(y),upd(f);
	}
	inline void MoInsert(int wz,int v){
		int x=split(wz,wz),f=rt,y=a[f].son[1],z=newnode(v);
		a[z].f=x;
		a[x].son[1]=z;
		a[x].rb=a[z].lb=abs(v-a[x].val);
		a[z].rb=a[y].lb=abs(v-a[y].val);
		upd(z),upd(x),upd(y);
	}
	inline int QuMax(int l,int r){
		int x=split(l,r);
		return a[x].maxn-a[x].minn;
	}
	inline int QuMin(int l,int r){
		int x;
		if(r-l<=1){
			x=split(l,r-1);
			return a[x].rb;
		}else{
			x=split(l+1,r-1);
			return a[x].ms;
        }
	}
}t;
int main(){
	n=read(),m=read();
	s[0]=INF;
	for(int i=1;i<=n;i++){
		s[i]=read();
	}
	s[n+1]=INF;
	t.sz=n+2;
	t.rt=t.build(0,n+1,0);
	while(m--){
		char opt=getc();
		switch(opt){
			case 'e':{
				int wz=read(),v=read();
				t.MoMerge(wz,v);
				break;
			}
			case 'n':{
				int wz=read(),v=read();
				t.MoInsert(wz,v);
				break;
			}
			case 'a':{
				int l=read(),r=read();
				write(t.QuMax(l,r));
				putc('\n');
				break;
			}
			case 'i':{
				int l=read(),r=read();
				write(t.QuMin(l,r));
				putc('\n');
				break;
			}
		}
	}
	flush();
}

再见 qwq~