线段树好题,和 15 年的广东省省赛 C 题有相似之处,一开始我的思路有偏差,看了别人的博客后感觉处处技巧都是精华,主要是区间合并的技巧一时很难想到,先附上代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define root int rt, int l, int r
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define makemid int mid = l + r >> 1
typedef long long LL;
const int N = ; int cnt[N << ];
LL sum[N << ][]; void build(root) {
cnt[rt] = ;
for(int i = ; i < ; ++i)
sum[rt][i] = ;
if(l == r) return ;
makemid;
build(lson);
build(rson);
} inline int mymod(int x, int mod) {
if(x < ) return (x % mod + mod) % mod;
return x % mod;
} inline void pushup(int rt) {
for(int i = ; i < ; ++i)
sum[rt][i] = sum[rt << ][i] + sum[rt << | ][mymod(i - cnt[rt << ], )];
} bool flag;
int pos, val; void update(root) {
flag ? ++cnt[rt] : --cnt[rt];
if(l == r) {
sum[rt][] = flag ? val: ;
return ;
}
makemid;
if(pos <= mid) update(lson);
else update(rson);
pushup(rt);
} int find(int *c, int low, int up, int x) {
int mid;
while(low <= up) {
mid = low + up >> ;
if(x == c[mid]) return mid;
else if(x < c[mid]) up = mid - ;
else low = mid + ;
}
return low;
} char op[N][];
int c[N], digit[N]; int main() {
int n,k;
while(~scanf("%d",&n)) {
k = ;
for(int i = ; i < n; ++i) {
scanf("%s",op[i]);
if(op[i][] != 's') {
scanf("%d", c + i);
digit[k++] = c[i];
}
}
sort(digit, digit + k);
int len = unique(digit, digit + k) - digit; if(len) build(,,len); for(int i = ; i < n; ++i) {
if(op[i][] == 's') printf("%I64d\n",sum[][]);
else {
flag = op[i][] == 'a';
pos = find(digit, , len - , c[i]) + ;
val = c[i];
update(,,len);
}
}
}
return ;
}
做 100 道水题,不如做一道难题来得更有意义。