题解：SP24772 DWARFLOG - Manipulate Dwarfs

海洋守卫者 · 2025-08-06 10:37:37 · 题解

SP24772 DWARFLOG - Manipulate Dwarfs

解题思路

本题有单点修改与区间查询的操作，不难想到线段树。

对于操作 1，由于身高与编号一一对应，可以用一个数组记录不同身高的位置，方便单点操作。

对于操作 2，询问区间是否连续，仅需要求出最大值与最小值的差即可。

完整代码

#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;
}