BZOJ 3155 Preprefix sum

3155: Preprefix sum

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 1820  Solved: 794
[Submit][Status][Discuss]

Description

 

Input

第一行给出两个整数N，M。分别表示序列长度和操作个数

接下来一行有N个数，即给定的序列a1,a2,....an

接下来M行，每行对应一个操作，格式见题目描述

Output

对于每个询问操作，输出一行，表示所询问的SSi的值。

Sample Input

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

Sample Output

35
32

HINT

1<=N,M<=100000,且在任意时刻0<=Ai<=100000

Source

Katharon+#1

维护前缀和最有力的工具当然是树状数组了

我们维护题目上所说的两个树状数组a[i]的前缀和和a[i]*(n-i)的前缀和

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0;ll f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
} 
const ll MAXN=1e6+10;
ll c[MAXN][3],n,m,a[MAXN];
inline ll lowbit(ll x){
    return x&-x;
}
inline void change(ll xx,ll vv,ll val){
    while(xx<=100000){
        c[xx][val]+=vv;
        xx+=lowbit(xx);
    }
}
inline ll get(ll xx,ll val){
    ll ans=0;
    while(xx){
        ans+=c[xx][val];
        xx-=lowbit(xx);
    }
    return ans;
}
void init(){
    memset(c,0,sizeof(c));
    n=read();m=read();
    for(ll i=1;i<=n;i++){
        a[i]=read();
        change(i,a[i],0);
        change(i,(ll)(n-i+1)*a[i],1);
    }
    for(ll i=1;i<=m;i++){
        char str[10];
        scanf("%s",&str);
        //cout<<str[0]<<endl;
        if(str[0]=='M'){
            ll xx=read();ll yy=read();
            change(xx,yy-a[xx],0);
            change(xx,(ll)(yy-a[xx])*(n-xx+1),1);
            //cout<<a[xx]<<' '<<yy<<endl;
            a[xx]=yy;
            
        }
        else{
            //cout<<1<<endl;
            ll xx=read();
            printf("%lld
",get(xx,1)-get(xx,0)*(n-xx));
        }
    }
}
int main(){
    //freopen("All.in","r",stdin);
    //freopen("aa.out","w",stdout);
    init();
    return 0;
}