洛谷 4915 帕秋莉的魔导书

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

根据期望的定义，操作 1 求的其实就是 i∈[x,y] 的前缀和的平均值。
所以此题转化为求前缀和的前缀和。

再想想，修改位置 i 的数，只会影响到 i 及其之后的的前缀和。
所以此题再次转化为区间（后缀）修改，区间查询。

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

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

代码：

#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);
    }
}