uva 11402 Ahoy, Pirates!

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

离散化 + 线段树

题意:很纠结的题意,直接从输出格式来说明题目

T //case数,10个case

n //有多少块字符串

m1 //表示将s1字符串重复复制m1次

s1

m2 //表示将s2字符串重复复制m2次

s2

…………

mn //将sn字符串复制mn次

sn

nq //nq个询问

F,a,b //将[a,b]区间的字符全部变为1

E,a,b //将[a,b]区间的字符全部变为0

I,a,b //将[a,b]区间的字符全部取反,0变1,1变0

S,a,b //查询[a,b]内有多少个1

//注意整个字符串长度为len,从0到len-1标号,所以[a,b]在这个区间以内

例如sample中的case 1

1
2
3
4
5
2
5
10
2
1000

就是10复制5次,1000复制2次,变为101010101010001000

注意将给出的小字符串复制并拼接为一个完整的字符步骤,要手写复制过程,不要利用库函数,会超时

这题很明显的想到用线段树来做,但是将字符串复制好后,就直接对这个总区间进行线段树的一系列操作时会超时的,因为区间太大了,达到百万级别。

但是留意到所有的操作数只有1000,每个操作对应一个区间,即取得2个端点,所以实际用到的端点只有2000个,所以利用离散化,这里的离散化比较巧妙,整个问题通过离线算法来解决

看例子

1
2
3
4
x,4,5
x,2,7
x,7,15
x,20,34

读入所有的操作,将所有端点保存下来,排序,去重,映射老三步得到

2,4,5,7,15,20,34 , 可见原串当中只有这部分是有用的,其余部分可以删除掉。我们利用这些端点重新建立一个新的完整区间,建立新区间的方法就是,每个端点作为一个区间单元,相邻两个端点之间的部分作为一个区间单元

2,作为一个单元 0

[3,3]作为一个单元 1

4,作为一个单元 2

[4,5]之间没有空格跳过

5,作为一个单元 3

[6,6]作为一个单元 4

7,作为一个单元 5

[8,14]作为一个单元 6

15,作为一个单元 7

[16,19],作为一个单元 8

20,作为一个单元 9

[21,33]作为一个单元 10

34,作为一个单元 11

一共有12个单元,新区间的长度就是13,这个13就是我们要线段树的总区间

对于一个区间单元,要记录3个信息,sum,one,zero,即这个区间有多少个字符,多少个1,多少个0

例如单元[21,33],字符总数当然是23,然后看看原串中,[21,33]里面有多少1和多少0即可

例如单元2,那么字符总数当然是1(只有1个字符),看看原串中2这个位置是1还是0,然后记录

这样做的道理是什么?

看看原操作x,7,15 , 7就是新区间的单元5,15就是新区间的单元7,对应过来就是这新区间[5,7]中进行操作

然后说说线段树的各种操作怎么实现

线段树要记录的信息

1
2
3
4
5
6
7
8
9
10
11
struct SegTree{
int l,r; //区间左右端点
int sum,one,zero,lazy; //区间包含多少个字符,1,0,lazy标记
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; lazy = -1;
}
int mid(){
return (l+r)>>1;
}
}t[4*4*Q];

F,E,I操作,都是更新操作,即更新一个区间内的信息,需要用到lazy思想。

lazy = 1,表示进行变1操作,lazy = 0表示变0操作, lazy = 2表示取反操作,lazy = -1 无操作

对于F操作,找到目标区间后,one = sum,zero = 0,lazy = 1,即全部字符变为1,无字符为0

对于E操作,找到目标区间后,zero = sum,one = 0,lazy = 0,即全部字符变为0,无字符为1

对于I操作,这个可以写得很复杂,但是理清关系后又可以很简单。

如果目标区间lazy = -1,那么直接操作目标区间,将其元素取反,swap(one,zero)

如果目标区间lazy = 1,那么就是之前做个一次变1操作,现在取反,相当于做了一次变0操作,zero = sum,lazy = 0

如果目标区间lazy = 0,那么就是i之前做了一次变0操作,现在取反,相当于做了一次变1操作,one = sum,lazy = 1

如果目标区间lazy = 2,那么就是之前做了一次取反操作,现在再做 一次,等于什么都没做,swap(one,zero),lazy = -1

查询,就直接查询吧。。。。。。。。

可以加一个优化,时间快了200ms

查询[a,b]有多少1,就是来到一个区间,如果t[rt].lazy = 1 / 0,也就是这个区间全部是1或0,那么没必要深入下去了。如果是1,直接返回[a,b]的长度。如果是0,说明没有1,返回0

这里有个问题,[a,b]的长度是多少,注意这个区间是我们重新建立的区间,不是原区间,如果是原区间,元素总数就是(b-a+1),但是新区间中,每个单元的字符个数不一定为1

我们在建立新区间的时候,是知道每个每个单元有多少字符的,那么我们用一个数组来记录一个前缀和

presum[a],表示新区间中的a单元以及之前的单元包含了多少个字符

那么[a,b]里面的字符总数就是presum[b] - presum[a] + tot[a]

下面说明一个代码中的一些变量,另外代码写得比较乱

保存所有的操作,a,b是原来的区间,ha,hb是经过处理后对应新区间的

1
2
3
4
5
struct ask{
char op[5];
int a,b;
int ha,hb;
}que[Q];

新区间的每个单元,记录每个单元有多少个字符,字符中多少是1,多少是0,这是为了一开始建立线段树用的

1
2
3
struct Node{
int sum,zero,one;
}node[Q<<2];

一些数组

1
2
3
4
char str[MAX]; //保存由小字符复制拼接成的完整字符串
int Hash[MAX]; //将新区间和旧区间对应起来
int presum[Q<<2]; //上面说的,新区间的前缀和
int point[MAX]; //保存所有操作的端点,进行排序,去重
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1024100
#define Q 1010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,tot,nq;
char str[MAX];
int Hash[MAX];
int presum[Q<<2];
int point[MAX];

struct ask{
char op[5];
int a,b;
int ha,hb;
}que[Q];

struct Node{
int sum,zero,one;
}node[Q<<2];

struct SegTree{
int l,r;
int sum,one,zero,lazy;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; lazy = -1;
}
int mid(){
return (l+r)>>1;
}
}t[4*4*Q];

void Init(){
//******************* 离散化所有询问中的点 *********************
int index = 0;
sort(point,point+tot); //排序
for(int i = 0; i < tot; i++) //去重
if(i == 0 || point[i] != point[i-1]){
point[index++] = point[i];
}
tot = index;
//******************* 建立新的总区间 *************************
cl(Hash,-1);
index = 0;
for(int i = 0; i < tot; i++){
node[index].sum = 1;
if(str[point[i]] == '1'){
node[index].one = 1; node[index].zero = 0;
}
else{
node[index].zero = 1; node[index].one = 0;
}
Hash[point[i]] = index;
if(index == 0) presum[index] = 1;
else presum[index] = presum[index-1] + 1;
index++;
if(i == tot-1) continue;
int sum,one = 0,zero = 0;
sum = point[i+1] - point[i] + 1 - 2;
if(sum <= 0) continue;
for(int k = point[i]+1; k < point[i+1]; k++)
if(str[k] == '1') one++;
else zero++;
node[index].sum = sum;
node[index].one = one; node[index].zero = zero;
presum[index] = presum[index-1] + node[index].sum;
index++;
}
n = index; //离散化全部完成,新的总区间长度为n
for(int i = 0; i < nq; i++){
que[i].ha = Hash[que[i].a]; que[i].hb = Hash[que[i].b];
}
}

void Del(int rt,int k){
if(k == 2){
t[rt].lazy = 1 - t[rt].lazy;
swap(t[rt].one,t[rt].zero);
}
else{
if(k == 1){
t[rt].one = t[rt].sum; t[rt].zero = 0; t[rt].lazy = 1;
}
else{
t[rt].zero = t[rt].sum; t[rt].one = 0; t[rt].lazy = 0;
}
}
}

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

void PushDown(int rt){
if(t[rt].lazy == -1) return ;
Del(lson(rt),t[rt].lazy);
Del(rson(rt),t[rt].lazy);
t[rt].lazy = -1;
}

void Build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b){
t[rt].sum = node[a].sum;
t[rt].one = node[a].one;
t[rt].zero = node[a].zero;
if(t[rt].one == t[rt].sum) t[rt].lazy = 1;
else if(t[rt].zero == t[rt].sum) t[rt].lazy = 0;
return ;
}
int mid = t[rt].mid();
Build(lson(rt),a,mid);
Build(rson(rt),mid+1,b);
PushUp(rt);
}

void Updata(int rt,int a,int b,int k){
if(t[rt].l == a && t[rt].r == b){
Del(rt,k);
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
Updata(lson(rt),a,b,k);
else if(a > mid)
Updata(rson(rt),a,b,k);
else{
Updata(lson(rt),a,mid,k);
Updata(rson(rt),mid+1,b,k);
}
PushUp(rt);
}

int Query(int rt,int a,int b){
if(t[rt].lazy == 1)
return presum[b]-presum[a]+node[a].sum;
else if(t[rt].lazy == 0)

if(t[rt].lazy == 0) return 0;
if(t[rt].l == a && t[rt].r == b)
return t[rt].one;
PushDown(rt);
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{
int res1 = Query(lson(rt),a,mid);
int res2 = Query(rson(rt),mid+1,b);
return res1 + res2;
}
}

int main(){
int cas,m,q;
char s[55];
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
/*********************** 读入数据 ***********************/
int id = 0;
str[id] = '&#92;&#48;';
scanf("%d",&n);
while(n--){
scanf("%d%s",&m,s);
while(m--){ //复制,手写,不要用库函数会超时
for(int i = 0; s[i]; i++)
str[id++] = s[i];
str[id] = '&#92;&#48;';
}
}
tot = 0;
scanf("%d",&nq);
for(int i = 0; i < nq; i++){
scanf("%s%d%d",que[i].op,&que[i].a,&que[i].b);
point[tot++] = que[i].a; point[tot++] = que[i].b;
}
//
Init();
Build(1,0,n-1);
q = 0;
printf("Case %d:\n",c);
for(int i = 0; i < nq; i++){
if(que[i].op[0] == 'F') //变1
Updata(1,que[i].ha,que[i].hb,1);
else if(que[i].op[0] == 'E') //变0
Updata(1,que[i].ha,que[i].hb,0);
else if(que[i].op[0] == 'I') //取反
Updata(1,que[i].ha,que[i].hb,2);
else{
int res = Query(1,que[i].ha,que[i].hb);
printf("Q%d: %d\n",++q,res);
}
}
}
return 0;
}