洛谷 4915.帕秋莉的魔导书

好久没写水题了,来玩一玩。

根据期望的定义,操作 11 求的其实就是 i[x,y]i \in [x,y] 的前缀和 j=iaj\sum\limits_{j = -\infty}^i a_j 的平均值。
所以此题转化为求前缀和的前缀和。

再想想,修改位置 ii 的数,只会影响到 [i,][i,\infty] 的前缀和。
所以此题再次转化为区间(后缀)修改,区间查询。

你看这题下标范围这么大,不如动态开点标记永久化(

然鹅貌似下标范围的下界不小于 00……

代码:

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
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int N = 1e5;
const long long C = INT_MAX;
int n,m;
struct node
{
long long sum,tag;
int ls,rs;
} seg[(N << 5) + 10];
int rt;
void update(long long l,long long r,long long k,int &p,long long tl,long long tr)
{
static int tot = 0;
if(!p)
p = ++tot;
seg[p].sum += k * (min(r,tr) - max(l,tl) + 1);
if(l <= tl && tr <= r)
{
seg[p].tag += k;
return ;
}
long long mid = tl + tr >> 1;
if(l <= mid)
update(l,r,k,seg[p].ls,tl,mid);
if(r > mid)
update(l,r,k,seg[p].rs,mid + 1,tr);
}
long long query(long long l,long long r,int p,long long tl,long long tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].sum;
long long mid = tl + tr >> 1;
long long ret = seg[p].tag * (min(r,tr) - max(l,tl) + 1);
if(l <= mid)
ret += query(l,r,seg[p].ls,tl,mid);
if(r > mid)
ret += query(l,r,seg[p].rs,mid + 1,tr);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
long long x,y;
for(register int i = 1;i <= n;++i)
scanf("%lld%lld",&x,&y),update(x,C,y,rt,0,C);
int op;
while(m--)
{
scanf("%d%lld%lld",&op,&x,&y);
if(op == 1)
printf("%.4f\n",(double)query(x,y,rt,0,C) / (y - x + 1));
else
update(x,C,y,rt,0,C);
}
}