【POJ3468】A Simple Problem with Integers

题面

给定长度为N的数列,输入Q个操作

C l r d:数列第l~r个数都加d

Q l r:输出数列l~r个数的和

N<=105 Q<=105

分析

noip要来了,多打暴力呀!于是,分块模板

代码

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<cmath>  
  6. using namespace std;  
  7. #define N 100010  
  8. #define ll long long  
  9. ll n,m;  
  10. char op[3];  
  11. ll a[N],sum[N],add[N],L[N],R[N],pos[N];  
  12.   
  13. void update(ll l,ll r,ll v)  
  14. {  
  15.     ll p=pos[l],q=pos[r];  
  16.     if(p==q)  
  17.     {  
  18.         for(ll i=l;i<=r;i++)a[i]+=v;  
  19.         sum[p]+=v*(r-l+1);  
  20.     }  
  21.     else  
  22.     {  
  23.         for(ll i=p+1;i<=q-1;i++)add[i]+=v;  
  24.         for(ll i=l;i<=R[p];i++)a[i]+=v;  
  25.         sum[p]+=v*(R[p]-l+1);  
  26.         for(ll i=L[q];i<=r;i++)a[i]+=v;  
  27.         sum[q]+=v*(r-L[q]+1);  
  28.     }  
  29. }  
  30.   
  31. ll query(ll l,ll r)  
  32. {  
  33.     ll p=pos[l],q=pos[r],ret=0;  
  34.     if(p==q)  
  35.     {  
  36.         for(ll i=l;i<=r;i++)ret+=a[i];  
  37.         ret+=add[p]*(r-l+1);  
  38.     }  
  39.     else  
  40.     {  
  41.         for(ll i=p+1;i<=q-1;i++)ret+=sum[i]+(R[i]-L[i]+1)*add[i];  
  42.         for(ll i=l;i<=R[p];i++)ret+=a[i];  
  43.         ret+=add[p]*(R[p]-l+1);  
  44.         for(ll i=L[q];i<=r;i++)ret+=a[i];  
  45.         ret+=add[q]*(r-L[q]+1);  
  46.     }  
  47.     return ret;  
  48. }  
  49.   
  50. int main()  
  51. {  
  52.     scanf("%lld%lld",&n,&m);  
  53.     for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);  
  54.     int t=sqrt(n);  
  55.     for(ll i=1;i<=t;i++)L[i]=(i-1)*t+1,R[i]=i*t;  
  56.     if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;  
  57.     for(ll i=1;i<=t;i++)  
  58.         for(ll j=L[i];j<=R[i];j++)  
  59.             pos[j]=i,sum[i]+=a[j];  
  60.     while(m--)  
  61.     {  
  62.         ll l,r,d;  
  63.         scanf("%s%lld%lld",op,&l,&r);  
  64.         if(op[0]=='C')scanf("%lld",&d),update(l,r,d);  
  65.         else printf("%lld ",query(l,r));  
  66.     }  
  67. }  
原文地址:https://www.cnblogs.com/NSD-email0820/p/9845410.html