【分块】【线段树】bzoj3212 Pku3468 A Simple Problem with Integers

线段树入门题……

因为poj原来的代码莫名RE，所以丧病地写了区间修改的分块……

其实就是块上打标记，没有上传下传之类。

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[100001],l[400],r[400],delta[400],num[100001],sum,sz,x,y,v;
char op[1];
long long sumv[400];
void makeblock()
{
    sz=sqrt(n);
    for(sum=1;sum*sz<n;sum++)
      {
        l[sum]=(sum-1)*sz+1;
        r[sum]=sum*sz;
        for(int i=l[sum];i<=r[sum];i++) {num[i]=sum; sumv[sum]+=a[i];}
      }
    l[sum]=sz*(sum-1)+1; r[sum]=n;
    for(int i=l[sum];i<=r[sum];i++) {num[i]=sum; sumv[sum]+=a[i];}
}
inline void update()
{
    if(num[x]+1>=num[y]){for(int i=x;i<=y;i++) a[i]+=v;}
    else
      {
          for(int i=x;i<=r[num[x]];i++) a[i]+=v;
          for(int i=l[num[y]];i<=y;i++) a[i]+=v;
          for(int i=num[x]+1;i<num[y];i++) delta[i]+=v;
      }
}
inline void query()
{
    long long ans=0;
    if(num[x]+1>=num[y]){for(int i=x;i<=y;i++) ans+=a[i];}
    else
      {
          for(int i=x;i<=r[num[x]];i++) ans+=(long long)(delta[num[x]]+a[i]);
          for(int i=l[num[y]];i<=y;i++) ans+=(long long)(delta[num[y]]+a[i]);
          for(int i=num[x]+1;i<num[y];i++) ans+=sumv[i]+(long long)((l[i]-r[i]+1)*delta[i]);
      }
    printf("%lld
",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
      {
          scanf("%s%d%d",op,&x,&y);
          if(op[0]=='Q') query();
          else {scanf("%d",&v); update();}
      }
    return 0;
}