codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<stdio.h> const int MAX = (1 << 3); int query; int arr[2 * MAX], v[MAX],tme[2*MAX],vv[2*MAX]; void B (int idx, int L, int R) { if (L == R) { arr[idx] = v[L]; return; } int mid = (L + R) / 2; B (2 * idx + 1, L, mid); B (2 * idx + 2, mid + 1, R); arr[idx] = arr[2 * idx + 1] + arr[2 * idx + 2]; return; } int Q1(int idx,int x,int y,int L,int R,int val,int tm); void U (int idx, int x, int y, int L, int R, int val) { if (x > R || y < L) return; if (x <= L and R <= y) { arr[idx] += (R-L+1)*val; if((R-L) >0){ int mid = (L + R) / 2; arr[2*idx] +=(mid-L+1)*val; arr[2*idx+1] +=(R-mid)*val; vv[2*idx] +=val; vv[2*idx + 1] +=val; vv[idx]=0; // printf("(L,mid,R)=(%d,%d,%d) %d:%d,%d\n",L,mid,R,arr[idx],arr[2*idx],arr[2*idx +1]); } else vv[idx]+=val; tme[idx]=query; // printf("idx=%d,%d:%d,val=%d,arr[idx]=%d\n",idx,L,R,val,arr[idx]); return; } int mid = (L + R) / 2; U (2 * idx , x, y, L, mid, val + vv[idx]); U (2 * idx + 1, x, y, mid + 1, R, val+ vv[idx]); //arr[idx] = Q1(1,L,mid,1,MAX,0,0) + Q1(1,mid+1,R,1,MAX,0,0); arr[idx]=arr[2*idx] + arr[2*idx +1]; // printf("(l,R)=(%d,%d) %d,%d\n",L,R,arr[2*idx],arr[2*idx +1]); } int Q1(int idx,int x,int y,int L,int R,int val,int tm) { if (x > R || y < L) return 0; if(x<=L and R<=y) return arr[idx]+ val; int mid=(L+R)/2; int z1,z2; if(tme[idx] > tme[2*idx]) z1=vv[idx]; else z1=vv[2*idx]; if(tme[idx] > tme[2*idx+1]) z2=vv[idx]; else z2=vv[2*idx+1]; return Q1 (2 * idx , x, y, L, mid,vv[idx]+val,tm) + Q1 (2 * idx + 1, x, y, mid + 1, R,vv[idx]+val,tm); } int main () { int n, items = 1; scanf (" %d", &n); while (n--) { query++; int t, x, val,i; scanf (" %d", &t); for(i=0;i<2*MAX;i++) printf("%d,",arr[i]); printf("\n"); if (t == 1) { scanf (" %d %d", &x, &val); U(1,1,x,1,MAX,val); printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items); } if (t == 2) { scanf (" %d", &val); items++; U(1,items,items,1,MAX,val); printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items); } if (t == 3) { int lastele=Q1(1,items,items,1,MAX,0,0); //printf("lastele=%d\n",lastele); U(1,items,items,1,MAX,-lastele); items--; printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items); } for(i=0;i<2*MAX;i++) printf("%d,",arr[i]); printf("\n"); } return 0; }
Private
[
?
]
Run code
Submit