Bakser's Blog

我是逗比。

bzoj3155 Preprefix sum [BIT]

| Comments

S1:A1
S2:A1 A2
S3:A1 A2 A3
S4:A1 A2 A3 A4
S5:A1 A2 A3 A4 A5
cnt:5 4 3 2 1
所以询问的就是

拆成

两项都可以用BIT维护
所以就水了。

bzoj3155
#include<bits/stdc++.h>
typedef unsigned long long LL;
const int N(100100);
#define lowbit(x) ((x&(-x)))
template<class T>
inline void read(T &x)
{
    char c=0;
    for(;c<'0'||c>'9';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
}
int n,m;
char s[20];
struct hh
{
    LL a[N];
    inline void modify(int x,LL delta)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            a[i]+=delta;
    }
    inline LL query(int x)
    {
        LL res(0);
        for(int i=x;i;i-=lowbit(i))
            res+=a[i];
        return res;
    }
}x,y;
LL a[N];
int main()
{
    read(n);read(m);
    for(int i(1);i<=n;i++)
        read(a[i]),x.modify(i,a[i]),y.modify(i,a[i]*(n-i+1));
    while(m--)
    {
        scanf("%s",s);
        int pos,val;
        read(pos);
        if(s[0]=='Q')printf("%lld\n",y.query(pos)-x.query(pos)*(n-pos));
        else if(s[0]=='M')
        {
            read(val);
            y.modify(pos,(val-a[pos])*(n-pos+1));
            x.modify(pos,val-a[pos]),a[pos]=val;
        }
    }
    return 0;
}

Comments

comments powered by Disqus