本文共 2913 字，大约阅读时间需要 9 分钟。
注意添加到集合中的数是升序的，先将数据读入，再离散化。
sum[rt][i]表示此节点的区域位置对5取模为i的数的和，删除一个数则右边的数循环左移一位，添加一个数则右边数循环右移一位，相当于循环左移4位，线段树与树状数组结合，树状数组确定位置。
le[rt]表示左移的位数，区间更新懒惰标记
#include #include #include #include #include #include using namespace std;const int N = 100008;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;int C[N];//注意初始化ninline int lowbit(int x){ return x&-x;}void add(int x, int val, int n){//将第x个数增加val，从1计数 for(int i=x;i<=n;i+=lowbit(i)){ C[i] += val; }}int getsum(int x){//求1到x的和 int ret = 0; for(int i=x;i>0;i-=lowbit(i)){ ret+=C[i]; } return ret;}LL sum[N<<2][5];int le[N<<2];LL a[N], b[N];void PushDown(int l, int r, int rt){ le[rt] %= 5; if(le[rt]){ if(l < r){ le[rt<<1] = (le[rt] + le[rt<<1]) % 5; le[rt<<1|1] = (le[rt] + le[rt<<1 | 1]) % 5; } int t = le[rt]; while(t--){ LL tp = sum[rt][0]; for(int i = 0; i <= 3; i++){ sum[rt][i] = sum[rt][i + 1]; } sum[rt][4] = tp; } le[rt] = 0; }}void PushUp(int l, int r, int rt){ if(l < r){ int m = (l + r)>>1; if(le[rt<<1]){//注意 PushDown(lson); } if(le[rt << 1 |1]){ PushDown(rson); } for(int i = 0; i < 5; i++){ sum[rt][i] = sum[rt <<1 ][i] + sum[rt<<1|1][i]; } }}void build(int l,int r,int rt){ if(l == r){ for(int i = 0 ; i < 5; i++){ sum[rt][i] = 0; } le[rt] = 0; return ; } int m = (l + r)>>1; build(lson); build(rson); PushUp(l, r, rt);}void update(int x, int rdx, int val, int l, int r, int rt){\ PushDown(l, r, rt); if(l == r){ if(rdx == -1){ for(int i = 0; i < 5; i++){ sum[rt][i] = 0; } }else{ sum[rt][rdx] = val; } le[rt] = 0; }else{ int m = (l + r)>>1; if(x <= m){ update(x, rdx, val, lson); }else{ update(x, rdx, val, rson); } } PushUp(l, r, rt);}void shift(int p, int a, int b, int l , int r, int rt){ PushDown(l ,r , rt); if(a <= l && b >= r){ le[rt] += p; PushDown(l, r, rt); }else{ int m = (l + r)>>1; if(a <= m){ shift(p, a, b, lson); } if(b > m){ shift(p, a, b, rson); } } PushUp(l, r, rt);}int main(){ int n; while(~scanf("%d", &n)){ memset(C, 0, sizeof(int) * (n + 2)); char str[10]; int cnt = 0; for(int i = 1; i <= n; i++){ scanf("%s", str); LL x; if(str[0] == 'a'){ scanf("%I64d", &x); a[i] = x << 1|1; b[cnt++] = x; }else if(str[0] == 'd'){ scanf("%I64d", &x); a[i] = x << 1; }else{ a[i] = -1; } } sort(b, b + cnt); cnt = unique(b, b + cnt) - b; build(1, cnt, 1); for(int i = 1; i <= n; i++){ if(a[i] == -1){ PushDown(1, cnt, 1); printf("%I64d\n", sum[1][3]); }else if(a[i] & 1){ a[i] >>= 1; int pos= lower_bound(b, b + cnt, a[i]) - b + 1; int rdx = getsum(pos) + 1; add(pos, 1, cnt); update(pos, rdx % 5, a[i], 1, cnt, 1); if(pos + 1 <= cnt){ shift(4, pos + 1, cnt, 1, cnt, 1); } }else{ a[i] >>= 1; int pos= lower_bound(b, b + cnt, a[i]) - b + 1; add(pos, -1, cnt); update(pos, -1, 0, 1, cnt, 1); shift(1, pos +1, cnt, 1, cnt, 1); } } } return 0;}
为什么我线段树总是写不好，总是要好长时间的debug……
转载于:https://www.cnblogs.com/IMGavin/p/5802719.html