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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
inline ll read() {
ll x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}
ll ttt, n, m;
char s[5];
struct segtree{
ll l, r, mx, sum, tag;
} tr[200005];
void build(ll ind, ll l, ll r) {
tr[ind].l = l; tr[ind].r = r; tr[ind].tag = 1;
if (l == r) {
tr[ind].mx = tr[ind].sum = 1;
return;
}
ll mid = (l + r) >> 1;
build(ind<<1, l, mid); build(ind<<1|1, mid+1, r);
tr[ind].mx = max(tr[ind<<1].mx, tr[ind<<1|1].mx);
tr[ind].sum = tr[ind<<1].sum + tr[ind<<1|1].sum;
}
inline void pushdown(ll ind) {
ll v = tr[ind].tag; tr[ind].tag = 1;
tr[ind<<1].tag *= v; tr[ind<<1].mx *= v; tr[ind<<1].sum *= v;
tr[ind<<1|1].tag *= v; tr[ind<<1|1].mx *= v; tr[ind<<1|1].sum *= v;
}
void update(ll ind, ll pos, ll v) {
ll l = tr[ind].l, r = tr[ind].r;
if (l == r) {
tr[ind].mx += v;
tr[ind].sum += v;
return;
}
pushdown(ind);
ll mid = (l + r) >> 1;
if (pos <= mid) update(ind<<1, pos, v);
else update(ind<<1|1, pos, v);
tr[ind].mx = max(tr[ind<<1].mx, tr[ind<<1|1].mx);
tr[ind].sum = tr[ind<<1].sum + tr[ind<<1|1].sum;
}
void update2(ll ind, ll x, ll y, ll v) {
if (x > y) return;
ll l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
tr[ind].tag *= v;
tr[ind].mx *= v;
tr[ind].sum *= v;
return;
}
pushdown(ind);
ll mid = (l + r) >> 1;
if (x <= mid) update2(ind<<1, x, y, v);
if (mid < y) update2(ind<<1|1, x, y, v);
tr[ind].mx = max(tr[ind<<1].mx, tr[ind<<1|1].mx);
tr[ind].sum = tr[ind<<1].sum + tr[ind<<1|1].sum;
}
pii find(ll ind, ll k, ll tp) {
ll l = tr[ind].l, r = tr[ind].r;
if (l == r) {
if (!tp) return make_pair(l, tr[ind].sum - k + 1);
else return make_pair(l, k);
}
pushdown(ind);
if (k <= tr[ind<<1].sum) return find(ind<<1, k, tp);
else return find(ind<<1|1, k - tr[ind<<1].sum, tp);
}
ll query(ll ind, ll x, ll y) {
if (x > y) return 0ll;
ll l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
return tr[ind].mx;
}
pushdown(ind);
ll mid = (l + r) >> 1, ret = 0;
if (x <= mid) ret = max(ret, query(ind<<1, x, y));
if (mid < y) ret = max(ret, query(ind<<1|1, x, y));
return ret;
}
int main() {
ttt = read();
for (ll kkk = 1; kkk <= ttt; kkk++) {
printf("Case #%lld:\n", kkk);
n = read(); m = read();
build(1, 1, n);
for (ll i = 1, x, y; i <= m; i++) {
scanf("%s", s); x = read(); y = read();
if (s[0] == 'Q') {
ll ans = 0;
pii l = find(1, x, 0), r = find(1, y, 1);
if (l.first == r.first) {
ans = y - x + 1;
} else {
ans = max(l.second, r.second);
ans = max(ans, query(1, l.first+1, r.first-1));
}
printf("%lld\n", ans);
} else {
pii l = find(1, x, 0), r = find(1, y, 1);
if (l.first == r.first) {
update(1, l.first, y - x + 1);
} else {
update(1, l.first, l.second); update(1, r.first, r.second);
update2(1, l.first + 1, r.first - 1, 2);
}
}
}
}
return 0;
}
|
