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は過ぎました.
コード:
最初のシーケンスは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);
}
}
・