【题目描述】
翻译:初始时按顺序排着一排细胞 第$i$个的种类是$i$

两种操作 第一种是把当前的第$l\sim r$个细胞原地翻倍
第二种是查询当前第$l\sim r$个细胞中 数量最多的同种细胞有多少个

$n\le 5*10^4$,任何时候细胞总数不超过$5*10^{12}$

举个例子 原来的细胞序列是${1,2,3,3,4,5}$把$[2,5]$翻倍 得到${1,2,2,3,3,3,3,4,4,5}$

题解

大概1min就想到正解了QAQ(可能是因为这个是线段树专题 所以明示要用线段树) 但是调了1h才AC

非常显然 不管怎么超级加倍这个细胞序列肯定都是一个不降的序列 同种细胞全部都在连续的一段里面

那我们用线段树维护一下每种细胞有多少个 然后不管是修改还是查询 都先在线段树上二分找到第$l$个及第$r$个位置是什么细胞 不妨设第$l$个是$x$,第$r$个是$y$

然后我们还要查出来$[l,r]$中有多少个$x$多少个$y$这个其实在线段树二分的时候就可以顺便查到了 我实现的比较毒瘤 用了个pair。。。

那么种类为$x+1\sim y-1$的那些细胞肯定全部都被包含在$[l,r]$之间了 对于修改操作直接区间给乘个$2$就好 查询也就是查一下区间最大值

然后把$x,y$单独处理一下 修改操作的话就现在$[l,r]$区间里有多少个$x$(我们刚才已经求过了)就给$x$加上多少 查询就比一下大小。。。

完事啦 时间复杂度$O(n \log n)$

代码

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

评论