学海泛舟

spoj DWARFLOG - Manipulate Dwarfs 题解

发表于 | 分类于 |

原题

传送门

题目大意

对于1~n个位置，对于任意一个位置i，都有一个身高为i的小矮人。有两种操作。
1 x y：将身高x，y的小矮人交换位置
2 x y：身高x到y的小矮人们所处位置是否连续

分析

关键在于如何判断是否连续。
身高x到y的小矮人的个数是固定的，若连续排列，他们所占的位置数也是固定的。
找出身高x到y的小矮人中所处位置的最大值和最小值，将y-x的值和最大值与最小值之差相比，就可判定。
将身高作为键，位置作为值，建立线段树，即可解决问题。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int Maxn=200010;
int n,m;
struct SegTree{
	int minn,maxn;
}seg[Maxn<<2];
void build(int p,int l,int r){
	seg[p].minn=l;
	seg[p].maxn=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
inline void change(int p,int l,int r,int x,int y){
	if(l==r){
		seg[p].minn=seg[p].maxn=y;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) change(p<<1,l,mid,x,y);
	else change(p<<1|1,mid+1,r,x,y);
	seg[p].minn=min(seg[p<<1].minn,seg[p<<1|1].minn);
	seg[p].maxn=max(seg[p<<1].maxn,seg[p<<1|1].maxn);
}
int findmax(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return seg[p].maxn;
	}
	int mid=(l+r)>>1;
	int ans=0;
	if(x<=mid){
		ans=max(ans,findmax(p<<1,l,mid,x,y));
	}
	if(y>mid){
		ans=max(ans,findmax(p<<1|1,mid+1,r,x,y));
	}
	return ans;
}
int findmin(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return seg[p].minn;
	}
	int mid=(l+r)>>1;
	int ans=Maxn;
	if(x<=mid){
		ans=min(ans,findmin(p<<1,l,mid,x,y));
	}
	if(y>mid){
		ans=min(ans,findmin(p<<1|1,mid+1,r,x,y));
	}
	return ans;
}
int main(){
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		if(a==1){
			int tmp1=findmax(1,1,n,b,b);
			int tmp2=findmax(1,1,n,c,c);
			change(1,1,n,b,tmp2);
			change(1,1,n,c,tmp1);
		} else {
			if(findmax(1,1,n,b,c)-findmin(1,1,n,b,c)==c-b){
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	}
	return 0;
}