专栏文章

题解:SP24772 DWARFLOG - Manipulate Dwarfs

SP24772题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioi2eay
此快照首次捕获于
2025/12/02 19:33
3 个月前
此快照最后确认于
2025/12/02 19:33
3 个月前
查看原文

SP24772 DWARFLOG - Manipulate Dwarfs

解题思路

本题有单点修改与区间查询的操作,不难想到线段树。
对于操作 11,由于身高与编号一一对应,可以用一个数组记录不同身高的位置,方便单点操作。
对于操作 22,询问区间是否连续,仅需要求出最大值与最小值的差即可。

完整代码

CPP
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
const int MAXN=5e5+7,oo=0x3f3f3f3f;
using namespace std;
int n,m,a[MAXN],opt,x,y;
struct Tree{
	int id,l,r,s,t;
	#define id(x) tree[x].id
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define s(x) tree[x].s
	#define t(x) tree[x].t
}tree[MAXN<<2];
inline void PushUp(int p)
{
	s(p)=min(s(p<<1),s(p<<1|1));
	t(p)=max(t(p<<1),t(p<<1|1));
}
inline void Build(int p,int l,int r)
{
	if(l==r)
	{
		l(p)=r(p)=l,id(p)=p,s(p)=t(p)=a[l];
		return;
	}
	l(p)=l,r(p)=r,id(p)=p;
	int mid=l+r>>1;
	Build(p<<1,l,mid);
	Build(p<<1|1,mid+1,r);
	PushUp(p);
}
inline void Change(int p,int x){
	if(l(p)>x||r(p)<x)return;
	if(l(p)==r(p)){
		s(p)=t(p)=a[x];
		return;
	}
	Change(p<<1,x);
	Change(p<<1|1,x);
	PushUp(p);
}
inline int Min(int p,int L,int R)
{
	if(l(p)>R||r(p)<L)return oo;
	if(l(p)>=L&&r(p)<=R)return s(p);
	return min(Min(p<<1,L,R),Min(p<<1|1,L,R));
}
inline int Max(int p,int L,int R)
{
	if(l(p)>R||r(p)<L)return -oo;
	if(l(p)>=L&&r(p)<=R)return t(p);
	return max(Max(p<<1,L,R),Max(p<<1|1,L,R));
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)a[i]=i;
	Build(1,1,n);
	while(m--)
	{
		scanf("%d %d %d",&opt,&x,&y);
		if(opt&1)
		{
			swap(a[x],a[y]);
			Change(1,a[x]);
			Change(1,a[y]);
		}
		else{
			int l=Min(1,x,y),r=Max(1,x,y);
			if(abs(x-y)==abs(r-l))puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...