【计蒜客】2018ICPC徐州赛区网络赛H Ryuji doesn't want to study（树状数组）

题目链接

 

【题意】

Ryuji不想学习，但他会学习一段时间，但是每天的学习效率会下降，其实题目说了一堆就是一个式子。

[r，l]是Ryuji学习时间的一个区间，然后有q次查询，当a=1时，查询l-r的总知识量，当a=2时，更新第l本书的知识量为r。

 

【解题思路】

将上述式子化简后可得

所以只需要用树状数组或线段树维护a[i]和a[i]*(n-i+1)这两个前缀和即可，因为a[i]*(n-i+1)可能会爆int，所以这里用long long。

 

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
LL t1[maxn],t2[maxn],n,m,q,a[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void update1(int x,LL v)
{
    while(x<=n)
    {
        t1[x]+=v;
        x+=lowbit(x);
    }
}
void update2(int x,LL v)
{
    while(x<=n)
    {
        t2[x]+=v;
        x+=lowbit(x);
    }
}
LL query1(int x)
{
    LL sum=0;
    while(x)
    {
        sum+=t1[x];
        x-=lowbit(x);
    }
    return sum;
}
LL query2(int x)
{
    LL sum=0;
    while(x)
    {
        sum+=t2[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        update1(i,a[i]);
        update2(i,a[i]*(n-i+1));
    }
    while(m--)
    {
        int k;
        LL b,c;
        scanf("%d%lld%lld",&k,&b,&c);
        if(k==1)
        {
            LL sum1=query1(c)-query1(b-1);
            LL sum2=query2(c)-query2(b-1);
            LL ans=sum2-(n-c)*sum1;
            printf("%lld\n",ans);
        }
        else
        {
            update1(b,c-a[b]);
            update2(b,(c-a[b])*(n-b+1));
            a[b]=c;
        }
    }
    return 0;
}