hdu 4638 Group

本文从WordPress迁移而来, 查看全部WordPress迁移文章

离散处理 + 树状数组 OR 线段树

【2013多校联合训练第四场】

题意：给出一个n的序列，里面只有1到n的数字每个出现且仅出现一次。有n个询问，每个询问给出一个[l,r]区间，问你这个区间可以分成多少段连续的序列（你可以把里面的数字发乱重新排列）。例如一段区间的序列为{2,3,5,6,1,9}，可以排成的连续的序列的{1,2,3}{5,6}{9},分成了3段，所以输出3

这题需要离线处理，通过一个val数组，将问题巧妙地转化为可以用线段树来解决的题目

首先我们来考虑一个前缀序列，即如果每次都问你[1,r]里面能分成多少段，要怎么做

  1. 从左到右地读入序列。没读入一个数字a[i]，我们先认为它自己成为一段。然后看看它的相邻数字a[i]-1,a[i]+1，之前是否已经出现了了。如果2者都已经出现，那么a[i]的出现可以合并两者，它对整个序列的贡献是-1，即它合并了两个段，令到原来的段数减1。如果2者只是出现了一个，那么a[i]可以并入它们当中连成一段，它对整个序列的贡献是0，即它没有使序列的段数增加。如果2者在之前都没有出现，那它就自成一段，它对整个串的贡献是1，即它令序列的段数增加了1

    你会发现，如果要求得[1,r]这样的询问，就只需要求sum{val[1] …… val[r]};

    但是对于要求[l,r]这样任意的询问，还要处理

  2. 我们读入全部的询问，并且对询问排序，按左端点升序排序
  3. 我们再次从左到右扫描整个串，这次做的是删除操作，并同时回答询问。

每在i这个位置时，先判断有没有询问的左端点是i，是的话就可以全部回答，这些询问，答案就是sum{val[i]……val[r]}

然后删除这个数字a[i]，这里有个很关键的地方，删除了a[i]只会对a[i]-1和a[i]+1这两个数字有影响。因为删除了a[i],必然使段断开，变成了2个段，如果a[i]-1这个数字在i位置之后，它就会收到影响，同样的，如果a[i]+1这个数字在i位置之后，也会收到影响，它们的val值要+1，因为新增了一个段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sample
10 2
3 1  2  5  8  9  10  4   6   7     序列
1 1 -1  1  1  0  0   -1  0   -1    一开始的val值

排序询问
[2,4]
[3,6]
进行删除和回答
在位置1，没有对应的询问，不用回答，做删除操作，删除了3，2,4对应的val发生变化
3 1  2  5  8  9  10  4   6   7     
     0               0          (+1)
在位置2，发现有对应的询问，那么先回答，sum{val[2] .... val[4]} = 0+1+1 = 2
然后删除操作，删除了1，对应的2发生变化
3 1  2  5  8  9  10  4   6   7
     1                          （+1）
在位置3，发现有对应的询问，那么先回答，sum{val[3] ... val[6]} = 1 + 1 + 1 + 0 = 3
然后删除2，对应的1,3的val要做出变化，但是1，和3都在2之前，所以不用变化了
这时候还可以继续做下去，但是所有询问已经完成了，所以也可以结束了

总结整个过程就是

  1. 初始化得到val
  2. 删除一个数字x，要找到x+1和x-1并修改他们的val值，其实就是一个单点修改
  3. 对于查询，就是求区间的val值的和，就是区间求和

单点修改，区间求和，是树状数组和线段树的基本功能

树状数组代码

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
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,a[N];
int val[N],pos[N],c[N];
struct ask{
	int l,r,id,res;
}q[N];

inline int lowbit(int x){
	return x&(-x);
}

void add(int p,int x){
	while(p <= n){
		c[p] += x;
		p += lowbit(p);
	}
}

int sum(int p){
	int res = 0;
	while(p){
		res += c[p];
		p -= lowbit(p);
	}
	return res;
}

bool cmp(ask x , ask y){
	return x.l < y.l;
}
bool __cmp(ask x ,ask y){
	return x.id < y.id;
}

int main(){
	int cas,m;
	scanf("%d",&cas);
	while(cas--){
		cl(pos,-1); cl(val,0); cl(c,0);
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
			pos[a[i]] = i;
			if(pos[a[i]-1] == -1 && pos[a[i]+1] == -1)
				val[i] = 1;
			else if(pos[a[i]-1] != -1 && pos[a[i]+1] != -1)
				val[i] = -1;
			else 
				val[i] = 0;
			add(i,val[i]);
		}
		for(int i = 0; i < m; i++){
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id = i;
		}
		sort(q,q+m,cmp);
		int cnt = 0;
		for(int i = 1; i <= n && cnt < m; i++){
			while(cnt < m && q[cnt].l == i){
				q[cnt].res = sum(q[cnt].r) - sum(q[cnt].l-1);
				cnt++;
			}
			int index;
			if(a[i] > 1){
				index = pos[a[i]-1];
				if(index > i){
					add(index,1); val[index]++;
				}
			}
			if(a[i] < n){
				index = pos[a[i]+1];
				if(index > i){
					add(index,1); val[index]++;
				}
			}
		}
		sort(q,q+m,__cmp);
		for(int i = 0; i < m; i++)
			printf("%d\n",q[i].res);
	}
	return 0;
}

线段树

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,a[N],val[N],pos[N];
struct SegTree{
	int l,r,sum;
	SegTree(){}
	SegTree(int _l,int _r){
		l = _l; r = _r;
	}
	int mid(){
		return (l+r)>>1;
	}
}t[N<<2];
struct ask{
	int l,r,id,res;
}q[N];

bool cmp(ask x , ask y){
	return x.l < y.l;
}
bool __cmp(ask x , ask y){
	return x.id < y.id;
}

void PushUp(int rt){
	t[rt].sum = t[lson(rt)].sum + t[rson(rt)].sum;
}

void build(int rt,int a,int b){
	t[rt] = SegTree(a,b);
	if(a == b){
		t[rt].sum = val[a];
		return ;
	}
	int mid = t[rt].mid();
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
	PushUp(rt);
}

int query(int rt,int a,int b){
	if(t[rt].l == a && t[rt].r == b)
		return t[rt].sum;
	int mid = t[rt].mid();
	if(b <= mid)
		return query(lson(rt),a,b);
	else if(a > mid)
		return query(rson(rt),a,b);
	else
		return query(lson(rt),a,mid) + query(rson(rt),mid+1,b);
}

void updata(int rt,int index,int v){
	if(t[rt].l == t[rt].r){
		t[rt].sum += v;
		return ;
	}
	int mid = t[rt].mid();
	if(index <= mid)
		updata(lson(rt),index,v);
	else
		updata(rson(rt),index,v);
	PushUp(rt);
}

int main(){
	int cas,m;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d%d",&n,&m);
		cl(pos,-1);
		for(int i = 1; i <= n; i++){
			scanf("%d",&a[i]);
			pos[a[i]] = i;
			if(pos[a[i]-1] == -1 && pos[a[i]+1] == -1)
				val[i] = 1;
			else if(pos[a[i]-1] != -1 && pos[a[i]+1] != -1)
				val[i] = -1;
			else val[i] = 0;
		}
		for(int i = 0; i < m; i++){
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id = i;
		}
		sort(q,q+m,cmp);
		build(1,1,n);
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			while(cnt < m && q[cnt].l == i){
				q[cnt].res = query(1,q[cnt].l,q[cnt].r);
				cnt++;
			}
			int index;
			if(a[i] > 1 && pos[a[i]-1] > i){
				index = pos[a[i]-1];
				updata(1,index,1);
			}
			if(a[i] < n && pos[a[i]+1] > i){
				index = pos[a[i]+1];
				updata(1,index,1);
			}
		}
		sort(q,q+m,__cmp);
		for(int i = 0; i < m; i++)
			printf("%d\n",q[i].res);
	}
	return 0;
}