poj3486分块实现

传送门
区间加和区间查询
分块实现(是真慢。。。)

#include<cstdio>
#include<cmath>
#include<iostream>
#define ls rt<<1
#define rs rt<<1|1
#define warn printf("!!**!!\n")
using namespace std;
typedef  long long LL;
typedef pair<int,int>pii;
const int maxn=1e6;
const int mod=1e9+7;
const int oo=1e9;
LL a[maxn+6],pos[maxn+6],L[maxn+6],R[maxn+6],cnt,len,x,y,z,n,q;
LL sum[maxn+6],add[maxn+5];
void update(int x,int y,int z)
{
    int p=pos[x],q=pos[y];
    if(p==q){
        for(int i=x;i<=y;i++) a[i]+=z*1ll,sum[p]+=z*1ll;
        return;
    }

    for(int i=p+1;i<=q-1;i++)sum[i]+=z*1ll*(len),add[i]+=z*1ll;
    int r=R[x],l=L[y];
    for(int i=x;i<=r;i++) a[i]+=z*1ll,sum[p]+=z*1ll;
    for(int i=l;i<=y;i++) a[i]+=z*1ll,sum[q]+=z*1ll;
}
LL query(int x,int y)
{
    int p=pos[x],q=pos[y];
    LL ans=0;
    if(p==q) {
        for(int i=x;i<=y;i++){
            ans=ans+a[i]+add[p];
        }
        return ans;
    }
    for(int i=p+1;i<=q-1;i++) ans=ans+sum[i];
    int r=R[x],l=L[y];
    for(int i=x;i<=r;i++) ans=ans+a[i]+add[p];
    for(int i=l;i<=y;i++) ans=ans+a[i]+add[q];
    return ans;
}
int main()
{

    scanf("%lld %lld",&n,&q);
    len=sqrt(n);
    for(int i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        if(i%len==0){
            cnt++;
            for(int j=i-len+1;j<=i;j++){
                pos[j]=cnt;
                L[j]=i-len+1;R[j]=i;
                sum[cnt]+=a[j];
            }
        }
    }
    if(n%len!=0){
        cnt++;
        for(int i=n-n%len+1;i<=n;i++){
            pos[i]=cnt;
            L[i]=n-n%len+1;R[i]=n;
            sum[cnt]+=a[i];
        }
    }

    char op[10];
    while(q--){
        scanf("%s%lld%lld",op,&x,&y);
        if(op[0]=='C') scanf("%d",&z);

        if(op[0]=='C'){
            update(x,y,z);
        }
        else {
            printf("%lld\n",query(x,y));
        }
    }
}