题目大意

给出一个长度为$n$的数列{$A_1,A_2......A_n$}，有两种操作，一共需要执行$m$次操作

1. 把$A_i$的值改为$x$

2. 先求出原数列的前缀和$sum[i]$，再求出$sum[i]$的前缀和

数据范围

$1\leqslant n,m\leqslant 100000$,且在任意时刻$0<=A_i<=100000$

题解

用树状数组维护两个和

1. $\sum_{i=1}^{x}A_i(1\leqslant x\leqslant n)$

2. $\sum_{i=1}^{x}A_i\times (n-i+1)(1\leqslant x\leqslant n)$

则$result(x)=\sum_{i=1}^{x}A_i\times (n-i+1)-(\sum_{i=1}^{x}A_i)\times (n-x)$

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
using namespace std;

ll a[100050],t[2][100050];
int n,m;
inline int lowbit(int x){return x&-x;}

inline void updata(int f,int x,ll y){
    for(int i=x;i<=n;i+=lowbit(i)) t[f][i]+=y;
}
inline ll query(int f,int x){
    ll sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=t[f][i];
    return sum;
}
int main(){
    scanf("%d%d",&n,&m);
    For(i,1,n){
        scanf("%d",&a[i]);
        updata(0,i,(ll)a[i]);
        updata(1,i,(ll)a[i]*(n-i+1));
    }
    For(i,1,m){
        char ch[10];
        scanf("%s",ch+1);
        if (ch[1]=='Q'){
            int x;scanf("%d",&x);
            printf("%lld\n",(ll)query(1,x)-query(0,x)*(n-x));
        }
        else{
            int x,y;scanf("%d%d",&x,&y);
            updata(0,x,(ll)y-a[x]);
            updata(1,x,(ll)(n-x+1)*(y-a[x]));
            a[x]=y;
        }
    }
    return 0;
}