#include<cstdio>
#include<iostream>

using namespace std;
const int maxn=1e5+1;
typedef long long ll;

ll N,Q;
ll sum1[maxn],sum2[maxn];
ll a[maxn];
char c;

ll lowbit(ll x){return x&-x;}

void add(ll *arr,ll x,ll c)
{
    while(x<=N)
    {
        arr[x]+=c;
        x+=lowbit(x);
    }
}
ll query(ll *arr,ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=arr[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    cin>>N>>Q;
    ll x;
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&a[i]);
        //a[i]+=a[i-1];
        add(sum1,i,a[i]-a[i-1]);
        add(sum2,i,i*(a[i]-a[i-1]));
    }
    for(int i=1;i<=Q;i++)
    {
        cin>>c;
        if(c=='Q')
        {
            ll cur=0;
            ll x,y;
            cin>>y>>x;
            //cur=a[y]-a[x-1];
            //cur+=query(b,)
            cur+=(x+1)*query(sum1,x)+query(sum2,y-1);
            cur-=y*query(sum1,y-1)+query(sum2,x);
            cout<<cur<<endl;
        }
        else{
                ll a,b,c;
                cin>>a>>b>>c;
                add(sum1,a,c),add(sum1,b+1,-c);
                add(sum2,a,a*c),add(sum2,b+1,-(b+1)*c);
        }
    }
    return 0;
}

• Re:WA用树状数组 qwq 有大佬帮忙看一下吗 (1365) 1769157748 2020-03-31 15:51:29
  • Re:WA用树状数组 qwq 有大佬帮忙看一下吗 (101) 1769157748 2020-03-31 15:53:06