Codeforces Round #174 (Div. 1)A

题不怎么难,按线段树的解法 就是延迟标记,更新 因为找错找了N久 记一篇吧

向下更新时把+=写成了= 还做在了2W组的数据上 那个错找得真费劲。。

Codeforces Round #174 (Div. 1)A
 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 }
View Code

Codeforces Round #174 (Div. 1)A

上一篇:AI网格渐变锥体的快速方便的做法


下一篇:PS将偏暗的童星照片打造出怀旧风格效果