#include < iostream > #include < algorithm > #include < cstdio > #include < cstring > #include < cmath > #include < map > using namespace std;
typedef long long LL;
map < int,
LL > mp;
map < int,
LL > mx;
LL ans;
int n,
m;
int pos[100];
void init() {
int tmp = n;
int deep = (int) log2(n) + 1;
for (int i = deep; i >= 1; i--) {
pos[i] = tmp;
tmp >>= 1;
}
}
void cal(int x) {
if (mp.count(x)) return;
if (x > n) {
mp[x] = 0;
return;
}
int deep = (int) log2(x) + 1;
LL tmp = 0;
for (int i = x; i <= n; i = (i << 1 | 1)) tmp += i;
if (pos[deep] == x) {
LL sum = 0;
for (int i = deep;; i++) {
sum += pos[i];
if (pos[i] == n) break;
}
tmp = max(tmp, sum);
}
mp[x] = tmp;
}
void update(int x) {
if (!x) return;
LL y;
if (mx.count(x) == 0) y = x;
else y = mx[x];
cal(x << 1);
cal(x << 1 | 1);
mp[x] = max(mp[x << 1], mp[x << 1 | 1]) + y;
update(x >> 1);
}
void query(LL sum, int x, int son) {
if (!x) return;
cal(x << 1);
cal(x << 1 | 1);
if (!mx.count(x)) mx[x] = x;
ans = max(ans, sum + mp[son ^ 1] + mx[x]);
sum += mx[x];
query(sum, x >> 1, x);
}
int main() {
char s[10];
while (scanf("%d", &n) != EOF) {
init();
mp.clear();
mx.clear();
scanf("%d", &m);
while (m--) {
scanf("%s", s);
if (s[0] == ‘q‘) {
int x;
scanf("%d", &x);
cal(x << 1);
cal(x << 1 | 1);
if (!mx.count(x)) mx[x] = x;
ans = mp[x << 1] + mp[x << 1 | 1] + mx[x];
cal(x);
query(mp[x], x >> 1, x);
printf("%lld\n", ans);
} else {
int x;
LL y;
scanf("%d%lld", &x, &y);
mx[x] = y;
update(x);
}
}
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2287203.html