A - Coder HDU - 4288——线段树

快来打我* 2022-06-10 01:57 139阅读 0赞

Think:  
1知识点：预处理得到有序线段树结点对应关系进而逐渐建树  
2题意：维护有序集合的插入操作/删除操作/求和操作

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1e5 + 4e2;
    
    struct Tree{
        int cnt;
        LL sum[5];
    }tree[N<<2];
    
    int data[N], tmp[N];
    char st[N][14];
    
    void Pushup(int rt);/*更新rt结点*/
    void Build(int l, int r, int rt);/*逐渐建立有序线段树*/
    void Updata(int flag, int p, int v, int l, int r, int rt);/*有序线段树的增加和删除操作*/
    
    int main(){
        int n, i, num;
        while(~scanf("%d", &n)){
            num = 0;
            for(i = 0; i < n; i++){
                scanf("%s", st[i]);
                if(st[i][0] != 's'){
                    scanf("%d", &data[i]);
                    tmp[num++] = data[i];
                }
            }
            sort(tmp, tmp+num);
            num = unique(tmp, tmp+num) - tmp;/*预处理得到有序建树结点*/
    
            Build(1, num, 1);
            for(i = 0; i < n; i++){
                int p = lower_bound(tmp, tmp+num, data[i]) - tmp;/*查找得到当前结点应在有序线段树结点中的位置*/
                if(st[i][0] == 's')
                    printf("%lld\n", tree[1].sum[2]);/*tree[1].sum[2]:记录了当前有序线段树中()%5=2的和*/
                else if(st[i][0] == 'a')
                    Updata(1, p, data[i], 1, num, 1);/*将当前结点增加到有序线段树中应插入的位置*/
                else
                    Updata(-1, p, 0, 1, num, 1);/*将当前结点从有序线段树中删除*/
            }
        }
        return 0;
    }
    void Build(int l, int r, int rt){
       /*更新rt结点*/
        memset(tree[rt].sum, 0, sizeof(tree[rt].sum));
        tree[rt].cnt = 0;
        if(l == r) return;
        int mid = (l+r)/2;
        Build(l, mid, rt<<1);
        Build(mid+1, r, rt<<1|1);
    }
    void Updata(int flag, int p, int v, int l, int r, int rt){
       /*逐渐建立有序线段树*/
        if(l == r){
            tree[rt].cnt += flag;/*flag = 1表示增加一个结点；flag = -1表示删除一个结点*/
            tree[rt].sum[0] = v;/*初始增加到0上则查询时输出tree[1].sum[2]*/
            return;
        }
        int mid = (l+r)/2;
        if(p <= mid)
            Updata(flag, p, v, l, mid, rt<<1);
        else
            Updata(flag, p, v, mid+1, r, rt<<1|1);
        Pushup(rt);
    }
    void Pushup(int rt){
       /*有序线段树的增加和删除操作*/
        for(int i = 0; i < 5; i++){
            tree[rt].sum[i] = tree[rt<<1].sum[i] + tree[rt<<1|1].sum[((i-tree[rt<<1].cnt)%5+5)%5];/*通过右子树已增加的有序结点个数得到左子树当前状态应对应的sum下标*/
        }
        tree[rt].cnt = tree[rt<<1].cnt + tree[rt<<1|1].cnt;
    }

[vjudge]: https://vjudge.net/contest/175272#problem/A