[CF85D] Sum of Medians

题目链接

Solution

值域线段树。

线段树节点上存储信息：$sum_{0,1,2,3,4}$，$sum_i$ 表示该节点对应区间内第模 $5$ 余 $i$ 的所有数之和，注意这里的第 $i$ 个数是这个区间内的第 $i$ 个数，与前面的区间有多少数无关。考虑更新 $sum_i$ 的值：一个节点的左右儿子更新上来时，左儿子的第 $i$ 个数还是该节点的第 $i$ 个数，但是右儿子的第 $i$ 个数实际上是该节点的第 $i+size(左儿子)$ 个数，所以顺带维护一个节点大小信息 $size$ 即可。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 100005;

int n, t[N], maxx, func[N];
struct Query{
    char s[10];
    int x, dx;
}q[N];

inline void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= n; i++){
        q[i].dx = lower_bound(t+1, t+t[0]+1, q[i].x) - t;
        maxx = max(maxx, q[i].dx);
        func[q[i].dx] = q[i].x;
    }
}

inline LL getMod(LL x){ return (x % 5 + 5) % 5; }

struct segTree{
    int l, r, size;
    LL sum[5];
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
    for(int i = 0; i < 5; i++)
        tr[id].sum[i] = tr[lid].sum[i] + tr[rid].sum[getMod(i - tr[lid].size)];
    tr[id].size = tr[lid].size + tr[rid].size;
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].size = 0;
    for(int i = 0; i < 5; i++)  tr[id].sum[i] = 0;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int pos, int val){
    if(tr[id].l == tr[id].r){
        tr[id].sum[1] = (val == 1) * func[tr[id].l];
        tr[id].size += val;
        return;
    }
    if(pos <= mid)  add(lid, pos, val);
    else    add(rid, pos, val);
    pushup(id);
}

int main(){
    read(n);
    for(int i = 1; i <= n; i++){
        scanf("%s", q[i].s);
        if(q[i].s[0] == 'a'){
            read(q[i].x);
            t[++t[0]] = q[i].x;
        }
        else if(q[i].s[0] == 'd'){
            read(q[i].x);
            t[++t[0]] = q[i].x;
        }
    }
    disc();
    build(1, 1, maxx);
    for(int i = 1; i <= n; i++){
        if(q[i].s[0] == 'a')    add(1, q[i].dx, 1);
        if(q[i].s[0] == 'd')    add(1, q[i].dx, -1);
        if(q[i].s[0] == 's')    cout << tr[1].sum[3] << endl;
    }
    return 0;
}