A-Coder HDU-4288-線分樹

7079 ワード
知識体系 考え事をする 過ちを改めて反省する データ構造-線分ツリー
Think:1知識点:前処理は、秩序化した線分ツリーの結点対応関係を得て、次第にツリー2を構築します.順序正しいセットを維持する挿入操作/削除操作/要求と操作
vjudgeテーマリンク
以下はAcceeptedコードです.
#include 
#include 
#include 

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
", 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;
}
配列内の加算値がある数の2つの数を探します.