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