题不怎么难,按线段树的解法 就是延迟标记,更新 因为找错找了N久 记一篇吧
向下更新时把+=写成了= 还做在了2W组的数据上 那个错找得真费劲。。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 #define N 200012 10 int n; 11 #define LL long long 12 LL s[N<<2],lz[N<<2]; 13 void down(int w,int m) 14 { 15 if(lz[w]) 16 { 17 s[w<<1]+=lz[w]*(m-m/2); 18 s[w<<1|1]+=lz[w]*(m/2); 19 lz[w<<1] += lz[w]; 20 lz[w<<1|1]+=lz[w]; 21 lz[w] = 0; 22 } 23 } 24 void up(int w) 25 { 26 s[w] = s[w<<1]+s[w<<1|1]; 27 } 28 void update(int a,int b,int d,int l,int r,int w) 29 { 30 if(a<=l&&b>=r) 31 { 32 s[w]+=(r-l+1)*d; 33 lz[w]+=d; 34 return ; 35 } 36 int m = (l+r)>>1; 37 down(w,r-l+1); 38 if(a<=m) 39 update(a,b,d,l,m,w<<1); 40 if(b>m) 41 update(a,b,d,m+1,r,w<<1|1); 42 up(w); 43 } 44 void set(int p,int d,int l,int r,int w) 45 { 46 if(l==r) 47 { 48 s[w] = d; 49 return ; 50 } 51 int m = (l+r)>>1; 52 down(w,r-l+1); 53 if(p>m) 54 set(p,d,m+1,r,w<<1|1); 55 else 56 set(p,d,l,m,w<<1); 57 up(w); 58 } 59 int main() 60 { 61 62 int i,t,x,y,g=1; 63 cin>>n; 64 LL sum=0; 65 for(i = 1; i <= n ; i++) 66 { 67 cin>>t; 68 if(t==1) 69 { 70 cin>>x>>y; 71 update(1,min(g,x),y,1,N-5,1); 72 sum = s[1]; 73 printf("%.6f\n",double(sum)/g); 74 } 75 else if(t==2) 76 { 77 cin>>x; 78 set(g+1,x,1,N-5,1); 79 sum = s[1]; 80 g++; 81 printf("%.6f\n",double(sum)/g); 82 } 83 else 84 { 85 if(g>1) 86 { 87 set(g,0,1,N-5,1); 88 g--; 89 sum = s[1]; 90 } 91 printf("%.6f\n",double(sum)/g); 92 } 93 } 94 return 0; 95 }