自动搬运

查看原文

来自洛谷，原作者为

	Amiyawasdonkey “怒りも喜びも哀しさも，全部ぶちこめ。”

搬运于2025-08-24 23:16:19，当前版本为作者最后更新于2025-05-21 13:41:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

作为少女乐队痴，我必须来写一写这个题解。

因为题目已有形式化题目描述，因此直接给出思路。

思路

我们可以看到，该题目包含区间查询与单点修改的要素，因此我们想到线段树。事实上，这是一道非常好的线段树板子题，可以拿来练手。

题目要点是查询在 $[l,r]$ 上未出现的最小正整数，假如我们从正面入手，很难想到该怎样在每个子节点存下这个值，但我们应该有正难则反的思维意识，想到查询在 $[1,l-1]$ 与 $[r+1,n]$ 上出现的最小值也是同样的效果。这样，我们可以在每个子节点存储该区间上出现的最小值，从而方便地查询到答案。

注：在进行单点修改操作时，我们可以维护一个数组来存储每个数字所在的位置，在修改操作完成时一并修改操作的数的位置，从而方便地进行单点修改操作。

Code

#include<bits/stdc++.h>
#define Iseri namespace
#define Nina std
#define Kawaragi int
#define Momoka main
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define ll long long
#define ull unsigned long long
#define endl "\n"
const int maxn=500005;

using Iseri Nina;

inline ll read(){//快读
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

//===========================================================

struct node{
	ll l,r;
	ll mn;
}t[maxn*4];

ll n,a[maxn],l,r,m,ans=0,pos[maxn];//pos是每个数的位置

inline void pushup(ll p){//更新区间最小值
	t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
	return;
}

inline void build(ll p,ll l,ll r){//建树
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].mn=a[l];
		return;
	}

	ll mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
	return;
}

inline ll ask(ll p,ll dl,ll dr){//查询操作
	if(t[p].l>=dl&&t[p].r<=dr)return t[p].mn;

	ll mid=(t[p].l+t[p].r)>>1,ans=1145141919;
	if(mid>=dl)ans=min(ans,ask(ls(p),dl,dr));
	if(mid<dr)ans=min(ans,ask(rs(p),dl,dr));
	return ans;
}

inline void change(ll p,ll x,ll d){//修改操作
	if(t[p].l==x&&t[p].r==x){
		t[p].mn=d;
		return;
	}

	ll mid=(t[p].l+t[p].r)>>1;
	if(mid>=x)change(ls(p),x,d);
	else change(rs(p),x,d);
	pushup(p);
	return;
}

Kawaragi Momoka(){
	n=read();
	for(ll i=1;i<=n;i++)a[i]=read(),pos[a[i]]=i;
	build(1,1,n);

	m=read();
	while(m--){
		l=read(),r=read();
		ll x=1145141919,y=1145141919;//设极大值
		if(l>1)x=ask(1,1,l-1);//注：在l=1的情况下，不能进行左边区间查询，无意义
		if(r<n)y=ask(1,r+1,n);//同理，r=n的情况下，不能进行右边区间查询，无意义
		ans=min(x,y);
		if(ans>=n)printf("peace\n");
		else{
			printf("%lld\n",ans);
			change(1,pos[ans],ans+1);//修改操作
			change(1,pos[ans+1],ans);
			swap(pos[ans],pos[ans+1]);//更新数字所在位置
		}
	}
	return 0;
}

提交记录：这里