codeforce 284-C Cows and Sequence(線分樹)

1765 ワード

タイトル:http://codeforces.com/problemset/problem/284/C
最初のシーケンスは0要素しかありません.3つの操作1:前のx個の数にyを加え、2:後にyを追加し、3:最後の数をイジェクトする.操作のたびに、数列の平均値を聞きます.
構想:線分樹、区間加算、単点修正.境界に注意して、初めの2 e 5はずっと間違っていて、2 e 5+5は過ぎました.
コード:

#include 
#define LL long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int maxn = 2e5+10;

LL n, op, x, y, a[maxn<<2], tag[maxn<<2], siz=1;
void pushup(int rt){a[rt] = a[ls] + a[rs];}
void pushdown(int rt, int l, int r){
    if(tag[rt]){
        int mid = l+r >> 1;
        tag[ls] += tag[rt]; tag[rs] += tag[rt];
        a[ls] += tag[rt]*(mid-l+1);
        a[rs] += tag[rt]*(r-mid);
        tag[rt] = 0;
    }
}
void update(int rt, int l, int r, int L, int R, LL v, int f){
    if(L <= l && R >= r){
        if(f==1) a[rt] = v;
        else a[rt] += v*(r-l+1), tag[rt] += v;
        return ;
    }
    pushdown(rt, l, r);
    int mid = l+r >> 1;
    if(L <= mid) update(ls, l, mid, L, R, v, f);
    if(R > mid) update(rs, mid+1, r, L, R, v, f);
    pushup(rt);
}
int main()
{
    scanf("%lld", &n);
    while(n--){
        scanf("%lld", &op);
        if(op == 1){
            scanf("%lld%lld", &x, &y);
            update(1, 1, 2e5+5, 1, x, y, 2);
        }else if(op == 2){
            scanf("%lld", &x);
            siz ++;
            update(1, 1, 2e5+5, siz, siz, x, 1);
        }else if(op == 3){
            update(1, 1, 2e5+5, siz, siz, 0, 1);
            siz --;
        }
        printf("%.9f
", (double)(a[1])/siz); } }