专栏文章
题解: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
解题思路
本题有单点修改与区间查询的操作,不难想到线段树。
对于操作 ,由于身高与编号一一对应,可以用一个数组记录不同身高的位置,方便单点操作。
对于操作 ,询问区间是否连续,仅需要求出最大值与最小值的差即可。
完整代码
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 条评论,欢迎与作者交流。
正在加载评论...