欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

luogu P5142 区间方差(线段树、乘法逆元)

程序员文章站 2022-07-14 08:34:29
...

luogu P5142 区间方差

luogu P5142 区间方差(线段树、乘法逆元)

本题要求维护模区间方差,很明显是一道数据结构题。

我们化简方差公式:

luogu P5142 区间方差(线段树、乘法逆元)
而平均数等于
luogu P5142 区间方差(线段树、乘法逆元)

可以发现,我们只需要维护序列的区间和和区间平方和,就可以维护平均数和方差。

区间和和区间平方和都满足结合律,因此可以用线段树维护。

题目要求分数取模, 所以我们使用乘法逆元即可。
最终答案为
psumsum2n%mod\frac {psum - sum^2}{n}\%mod

=(psumnmod2%mod+(sumnmod2%mod)2)%mod=(psum*n^{mod-2}\%mod+(sum*n^{mod-2}\%mod)^2)\%mod

其中
线段树维护的区间平方和 psumpsum
psum=i=1nxi2psum = \sum_{i = 1}^{n}{x_i^2}
线段树维护的区间和 sumsum
sum=i=1nxisum = \sum_{i = 1}^{n}{x_i}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define get_mod(x) (x % mod + mod ) % mod
using namespace std;
typedef long long ll;
const int N = 500007, mod = 1e9 + 7;

int n, m;
int a[N];
int cnt;

int qpow(int b, int p = mod - 2, int m = mod)
{//快速幂用于费马小定理求乘法逆元
    b %= m;
    int res = 1 % m;
    for(; p; p >>= 1, b = (ll)b * b % m)
        if(p & 1)res = (ll)res * b % m;
    return res;
}

namespace tree
{
    #define get_powsum(x) ((ll)(x)*(x)%mod) //!
    struct tree
    {
        int l, r;
        int sum, psum;
        //int lz;
    }tr[N];

    inline void pushup(int p)
    {
        tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % mod;
        tr[p].psum = (tr[p << 1].psum + tr[p << 1 | 1].psum) % mod;
    }

    void build(int p, int l, int r)
    {
        tr[p] = {l, r};
        if(l == r)
        {
            tr[p].sum = a[r] % mod;
            tr[p].psum = get_powsum(a[r]) % mod;
            return ;
        }
        int mid = l + r >> 1;
        build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
        pushup(p);
    }

    void modify(int p, int x, int k)
    {
        if(tr[p].l == tr[p].r)
        {
            tr[p].sum = k % mod;
            tr[p].psum = get_powsum(k) % mod;
            return ;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        if(x <= mid)modify(p << 1, x, k);
        else modify(p << 1 | 1, x, k);
        pushup(p);
        
    }
    int query_sum(int p, int l, int r)
    {
        if(tr[p].l >= l && tr[p].r <= r)
        {
            return tr[p].sum % mod;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        int res = 0;
        if(l <= mid)res = query_sum(p << 1, l, r) % mod;
        if(r > mid)res = (1ll * res +  query_sum(p << 1 | 1, l, r)) % mod;
        return res % mod;
    }
    int query_psum(int p, int l, int r)
    {
        if(tr[p].l >= l && tr[p].r <= r)
        {
            return tr[p].psum % mod;
        }
        int mid = tr[p].l + tr[p].r >> 1;
        int res = 0;
        if(l <= mid)res = query_psum(p << 1, l, r) % mod;
        if(r > mid)res = (1ll * res +  query_psum(p << 1 | 1, l, r)) % mod;
        return res % mod;
    }
}

int sum, psum, inv, ave, ans;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    tree::build(1, 1, n);
    for(int i = 1; i <= m; ++ i)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1)
        {
            tree::modify(1, x, y % mod);
        }
        else {
            sum = tree::query_sum(1, x, y % mod) % mod;   //区间和
            psum = tree::query_psum(1, x, y % mod) % mod; //区间平方和
            inv = qpow(y - x + 1);                  //区间长度(分母)的逆元
            ave = (ll)sum * inv % mod;
            ans = (ll)psum * inv % mod - (ll)ave * ave % mod;
            ans = get_mod(ans);
            printf("%d\n", ans);
            //cout << "ok" << cnt ++ << endl;
        }
    }
    return 0;
}