欢迎访问 My Luogu Space。
【题目大意】
有 n 个身高为 [1, n] 的且各不相同的人排成一个序列。
有两种操作:
- 让位置 x, y 的人交换位置。
- 给定一个范围[l, r],询问身高在该范围内的所有人是否排成了一个连续的序列。
输出操作二的询问。
【题解】
线段树。
操作一很简单。
对于操作二:
我们发现身高在 [l, r] 的人一共有 k=(r−l+1) 个。
我们只需要找到身高在这个范围内,且站在最左端和最右端的人的坐标。
(右坐标−左坐标 +1) 的值如果等于 k,那么这 k 个人就刚好排成了一个连续的序列。
如果大于就是这 k 个人当中被插入了一些其他人,不可能有小于的情况出现。
因此我们需要支持查询坐标的最大和最小值。
建一棵以身高为下标的线段树,值为身高对应的坐标,区间查询坐标的最大和最小值。
【代码】
// output format !!
// long long !!
#include <bits/stdc++.h>
#define H puts("HYX")
#define ls (x<<1)
#define rs (x<<1|1)
const int MAXN = 200000+10;
using std::max; using std::min; using std::swap;
struct TREE{int Max, Min;}t[MAXN*4];
int n, m, h[MAXN], loc[MAXN], L, R;
void build(int x, int l, int r){
if(l == r) return t[x].Max = t[x].Min = loc[l], void();
int mid = (l+r)>>1;
build(ls, l, mid), build(rs, mid+1, r);
t[x].Max = max(t[ls].Max, t[rs].Max);
t[x].Min = min(t[ls].Min, t[rs].Min);
}
void query(int x, int l, int r, int ql, int qr){
if(ql<=l && r<=qr){
L = min(L, t[x].Min);
R = max(R, t[x].Max);
return;
}
int mid = (l+r)>>1;
if(ql <= mid) query(ls, l, mid, ql, qr);
if(qr > mid) query(rs, mid+1, r, ql, qr);
}
void modify(int x, int l, int r, int p, int v){
if(l == r) return t[x].Max = t[x].Min = v, void();
int mid = (l+r)>>1;
if(p <= mid) modify(ls, l, mid, p, v);
else modify(rs, mid+1, r, p, v);
t[x].Max = max(t[ls].Max, t[rs].Max);
t[x].Min = min(t[ls].Min, t[rs].Min);
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) scanf("%d", h+i), loc[h[i]] = i;
build(1, 1, n);
while(m--){
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1){
modify(1, 1, n, h[y], x);
modify(1, 1, n, h[x], y);
swap(h[x], h[y]), swap(loc[h[x]], loc[h[y]]);
}
else{
L = 1e9, R = 0;
query(1, 1, n, x, y);
if(R-L+1 == y-x+1) puts("YES");
else puts("NO");
}
}
return 0;
}