链接:http://codeforces.com/problemset/problem/284/C
思路:唯一需要注意的是操作1的区间修改,由于查询的时候只会查询最后一个元素并且区间总是从1开始
所以只需用一个s【】数组维护就行
树状数组:令c【i】为原数列,我们让s【i】为c【i】的差分数列即s【i】=c【i】-c【i-1】后
数组s的前i项和即为c【i】
对于区间x~y 加w 的操作 :update(x,w);update(y+1,-w);仍不改变求和操作的正确性
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Accepted 0
LL q,t,a,x,k,num[200010],s[200010];
LL sum=0,cnt=1;
int main()
{
scanf("%lld",&q);
num[1]=0;
while(q--){
scanf("%lld",&t);
if(t==1){
scanf("%lld %lld",&a,&x);
s[a]+=x;
sum=sum+a*x;
}
else if(t==2){
scanf("%lld",&k);
sum+=k;
cnt++;
num[cnt]=k;
}
else {
sum=sum-num[cnt]-s[cnt];
num[cnt]=0;
cnt--;
s[cnt]+=s[cnt+1];
s[cnt+1]=0;///999
}
printf("%.6f\n",1.0*sum/(1.0*cnt));
}
return Accepted;
}