blob: 32702f6c534d20938a66491e38354b1bb47e311d (
plain) (
blame)
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
|
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
typedef pair<long long, long long> Query;
char S[2000005] = { '\0' };
char Supdate[2000005] = { '\0' };
long long QN = 0;
Query qs[2000005] = {{0,0}};
long long leader[2000005] = { 0 }, ssize[2000005] = { 0 }, mem[2000005] = { 0 };
long long getLeader(long long l) {
while (leader[l] != l) {
leader[l] = leader[leader[l]];
l = leader[l];
}
return l;
}
int main() {
scanf("%s", S);
scanf("%lld", &QN);
for (long long i = 0; i < QN; i++) {
Query qi = {0,0};
scanf("%lld %lld", &qi.first, &qi.second);
qs[i] = qi;
}
strcpy(Supdate, S);
// Fill Supdate
for (long long i = 0; i < QN; i++) {
if (qs[i].first == 1) continue;
Supdate[qs[i].second] = '#';
}
// cout << endl;
// for (int i = 0; i <QN; i++) {
// cout << qs[i].first << " " << qs[i].second << endl;
// }
// Fill leader and ssize
for (long long i = 0; Supdate[i] != '\0'; i++) {
if (Supdate[i] == '#') {
ssize[i] = 1;
leader[i] = i;
continue;
}
long long j = i;
while (Supdate[i] == Supdate[j]) j++;
long long ib = i;
for (; i < j; i++) {
ssize[i] = j - ib;
leader[i] = ib;
}
i--;
}
// Fix leader and size
long long mi = 0;
for (long long i = QN - 1; i >= 0; i--) {
if (qs[i].first == 2) {
Supdate[qs[i].second] = S[qs[i].second];
if (qs[i].second > 0 && Supdate[qs[i].second - 1] == Supdate[qs[i].second]) {
long long l = getLeader(qs[i].second - 1);
leader[l] = qs[i].second;
ssize[qs[i].second] += ssize[l];
}
if (Supdate[qs[i].second] == Supdate[qs[i].second+1]) {
long long l = getLeader(qs[i].second + 1);
leader[l] = qs[i].second;
ssize[qs[i].second] += ssize[l];
}
}
else {
mem[mi++] = ssize[getLeader(qs[i].second)];
// cout << Supdate << endl;
// for (int i = 0; i < 15; i++)
// cout << leader[i] << " ";
// cout << endl;
// for (int i = 0; i < 15; i++)
// cout << ssize[i] << " ";
// cout << endl;
// cout << qs[i].second << " " << leader[qs[i].second] << " " << ssize[qs[i].second] << endl;
}
}
// Output
while(--mi >= 0)
printf("%lld\n", mem[mi]);
}
|
