【题目描述】
翻译：初始时按顺序排着一排细胞 第(i)个的种类是(i)
两种操作 第一种是把当前的第(lsim r)个细胞原地翻倍
第二种是查询当前第(lsim r)个细胞中 数量最多的同种细胞有多少个
(nle 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+1sim y-1)的那些细胞肯定全部都被包含在([l,r])之间了 对于修改操作直接区间给乘个(2)就好 查询也就是查一下区间最大值
然后把(x,y)单独处理一下 修改操作的话就现在([l,r])区间里有多少个(x)(我们刚才已经求过了)就给(x)加上多少 查询就比一下大小。。。
完事啦 时间复杂度(O(n log n))
代码
#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:
", 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
", 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;
}