题目链接： https://vjudge.net/problem/SPOJ-DWARFLOG
题意：
题意
N个小矮人的身高为1，2，…，N，初始按照身高从1到N的顺序排列，给出m次操作
.1 X Y 将身高为X和Y的小矮人交换位置
.2 A B 询问身高为A，A+1，…，B的小矮人是否位于连续的位置
数据
第一行为N和M，2 <= N <= 200000，2 <= M <= 200000
接下来M行为“1 X Y”（1 <= X，Y <= N，X != Y）或者“2 A B”（1 <= A <= B）
输入
4 5
2 2 3
2 2 4
1 1 3
2 3 4
1 4 3
输出
YES
YES
NO

解题思路： 是bzoj 1067 的弱化版，不过判断连续都是一样方法，我们只要知道A到B的位置中最大的一个pd和最小的一个px，A到B连续当前仅当B-A=pd-px。所以我们直接用线段树维护就可以了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, m, a[maxn];
int mx[maxn<<2], mi[maxn<<2], L, R, P, m1, m2;
void build(int l, int r, int o){
    if(l == r){
        mx[o] = mi[o] = a[l];
    }
    else{
        int mid = (l + r) / 2;
        build(l, mid, o * 2);
        build(mid + 1, r, o * 2 + 1);
        mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
        mi[o] = min(mi[o * 2], mi[o * 2 + 1]);
    }
}
void update(int l, int r , int o){
    if(l == r && l == P){
        mx[o] = mi[o] = a[l];
    }
    else{
        int mid = (l + r) / 2;
        if(P <= mid) update(l, mid, o * 2);
        else update(mid + 1, r, o * 2 + 1);
        mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
        mi[o] = min(mi[o * 2], mi[o * 2 + 1]);
    }
}
void query(int l, int r, int o){
    if(L <= l && r <= R){
        m1 = max(m1, mx[o]);
        m2 = min(m2, mi[o]);
    }
    else{
        int mid = (l + r) / 2;
        if(L <= mid) query(l, mid, o * 2);
        if(mid < R) query(mid + 1, r, o * 2 + 1);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) a[i] = i;
    build(1, n, 1);
    while(m--){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1){//update
            swap(a[x], a[y]);
            P = x; update(1, n, 1);
            P = y; update(1, n, 1);
        }
        else{ //query
            m1 = 0; m2 = n + 1;
            L = x, R = y;
            query(1, n, 1);
            //cout << m1 << " " << m2 << endl;
            if(m1 - m2 == R - L){
                puts("YES");
            }
            else{
                puts("NO");
            }
        }
    }
    return 0;
}