摘要:线段树维护前缀和

luogu4915帕秋莉的魔导书

题面

题目分析

母亲的,打这题代码像见了鬼一样,各种莫名奇妙地掉精度,炸范围,开够的数组莫名被清空一怒之下开大10倍空间…

话说回来这个出题人出了好多姆q题啊,以后我题面也全写姆q了.

转化应该挺容易的,我们需要维护值域前缀和的部分和.

求得初始的前缀和后建出线段树维护部分和,考虑怎么带修,一个位置的值发生改变,那么这个位置后面的前缀和均会发生改变一个相同的值,区间修改即可.

因为值域太大考虑离散化,把作为在值域出现的值全部存下来离散化即可.

然而这样显然不可行,比如可爱的出题人给了这样一组hack:

1
2
3
4
5
6
7
8
9
in:
2 2
1 3
5 2
1 3 3
1 3 5
out:
3.0000
3.6667

因为题目是求期望,所以需要求得区间内的所有情况,但我们这样离散化仅保留了大小关系的信息,所以需要维护离散化之后的值域上两个数之间省略的原值域的大小,在维护前缀和的过程中,省略的值可以整体考虑,因为没有在其范围内的询问或插入,整体的值仅和省略区间的左端点的值有关.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#include "assert.h"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
#define lowbit(x) (x&-x)
typedef long long lxl;
typedef long double lbl;
const lxl big=300010,small=1000010;
lxl n,m,BCnt,QCnt,cut,NowQ,NowB,knoc,root,NodeCnt;
lxl val[big],kno[big],whi[small],siz[big];
lxl c[2][big<<2],sum[big<<2],sum2[big<<2],tag[big<<2],size[big<<2];
double di;
struct _Pachy
{
lxl a,w;
}b[small];
struct _Query
{
lxl l,r;
double len;
}q[small];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void PushUp(lxl t){sum[t]=sum[c[0][t]]+sum[c[1][t]];}
inline void PushDown(lxl t)
{
if(!tag[t])return;
lxl lson=c[0][t],rson=c[1][t];
sum[lson]+=tag[t]*size[lson],sum[rson]+=tag[t]*size[rson];
sum2[lson]+=tag[t]*(size[lson]-1),sum2[rson]+=tag[t]*(size[rson]-1);
tag[lson]+=tag[t],tag[rson]+=tag[t];
tag[t]=0;
}
void BuildTree(lxl &t,lxl l,lxl r)
{
if(!t)t=++NodeCnt;
if(l==r){size[t]=siz[l],sum[t]=val[l]*size[t],sum2[t]=val[l]*(size[t]-1);return;}
lxl mid((l+r)>>1);
BuildTree(c[0][t],l,mid),BuildTree(c[1][t],mid+1,r);
PushUp(t);
size[t]=size[c[0][t]]+size[c[1][t]];
}
void insert(lxl t,lxl l,lxl r,lxl x,lxl y,lxl kd)
{
if(x<=l&&y>=r){sum[t]+=kd*size[t],sum2[t]+=kd*(size[t]-1),tag[t]+=kd;return;}
PushDown(t);
lxl mid((l+r)>>1);
if(x<=mid)insert(c[0][t],l,mid,x,y,kd);
if(y>mid)insert(c[1][t],mid+1,r,x,y,kd);
PushUp(t);
}
lbl query(lxl t,lxl l,lxl r,lxl x,lxl y)
{
if(x<=l&&y>=r)return (lbl)sum[t]/di;
PushDown(t);
lxl mid((l+r)>>1);
double ret(0);
if(x<=mid)ret+=query(c[0][t],l,mid,x,y);
if(y>mid)ret+=query(c[1][t],mid+1,r,x,y);
return ret;
}
lbl query2(lxl t,lxl l,lxl r,lxl x)
{
if(l==r)return (lbl)sum2[t]/di;
PushDown(t);
lxl mid((l+r)>>1);
if(x<=mid)return query2(c[0][t],l,mid,x);
else return query2(c[1][t],mid+1,r,x);
}
int main(void)
{
// freopen("data.txt","r",stdin),freopen("test.out","w",stdout);
n=read(),m=read();
for(R int i(1);i<=n;++i)b[++BCnt].a=read(),b[BCnt].w=read(),kno[++knoc]=b[i].a;
for(R int i(1);i<=m;++i)
{
whi[i]=read();
if(whi[i]==1)
{
q[++QCnt].l=read(),q[QCnt].r=read(),q[QCnt].len=q[QCnt].r-q[QCnt].l+1;
kno[++knoc]=q[QCnt].l,kno[++knoc]=q[QCnt].r;
// debugf(q[QCnt].len),debug(q[QCnt].l),debug(q[QCnt].r),endl;
}
else b[++BCnt].a=read(),b[BCnt].w=read(),kno[++knoc]=b[BCnt].a;
}
// for(R int i(1);i<=QCnt;++i)debugf(q[i].len),debug(q[i].l),debug(q[i].r),endl;
std::sort(kno+1,kno+1+knoc),cut=std::unique(kno+1,kno+1+knoc)-kno-1;
for(R int i(1);i<=BCnt;++i)b[i].a=std::lower_bound(kno+1,kno+1+cut,b[i].a)-kno;
for(R int i(1);i<=QCnt;++i)
q[i].l=std::lower_bound(kno+1,kno+1+cut,q[i].l)-kno,
q[i].r=std::lower_bound(kno+1,kno+1+cut,q[i].r)-kno;
for(R int i(1);i<=n;++i)val[b[i].a]+=b[i].w;
for(R int i(1);i<=cut;++i)val[i]+=val[i-1],siz[i]=kno[i+1]-kno[i];
siz[cut]=1,NowB=n,BuildTree(root,1,cut);
// debugf(q[1].len);
for(R int i(1);i<=m;++i)
if(whi[i]==1)
{
++NowQ;
// assert(q[NowQ].len>0.01);
di=q[NowQ].len;
// if((lxl)di==0)debug(NowQ),debugf(q[NowQ].len),debugf(di),endl;
double all=query(root,1,cut,q[NowQ].l,q[NowQ].r)-query2(root,1,cut,q[NowQ].r);
// std::cout<<std::fixed<<std::setprecision(4)<<all;endl;
printf("%.4lf\n",all);
}
else ++NowB,insert(root,1,cut,b[NowB].a,cut,b[NowB].w);
return 0;
}
/*
2 2
1 3
5 2
1 3 3
1 3 5
*/