COdeVS——T 1082 线段树练习 3 (分块练习）

http://codevs.cn/problem/1082/

时间限制: 3 s

空间限制: 128000 KB

题目等级 : 大师 Master

题解

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

 #include <cstdio>

 #include <cmath>

 using namespace std;

 #define LL long long

 const int N();

 LL n,q,num[N*N],u,v,x,op;

 LL C,cnt,str[N],ove[N],bel[N*N],sum[N],tag[N];

 #define min(a,b) (a<b?a:b)

 #define max(a,b) (a>b?a:b)

 void Build()

 {

     C=sqrt(n);

     for(LL i=;i<=n;i+=C)

     {

         str[++cnt]=i;

         ove[cnt]=min(n,i+C-);

     }

     for(LL i=;i<=cnt;i++)

         for(LL j=str[i];j<=ove[i];j++)

             bel[j]=i,sum[i]+=num[j];

 }

 void Update(LL u,LL v,LL x)

 {

     for(LL i=bel[u];i<=bel[v];i++)

         if(str[i]>=u&&ove[i]<=v) tag[i]+=x,sum[i]+=(ove[i]-str[i]+)*x;

         else for(LL j=max(str[i],u);j<=min(ove[i],v);j++) num[j]+=x,sum[i]+=x;

 }

 LL Query(LL u,LL v)

 {

     LL ret=;

     for(LL i=bel[u];i<=bel[v];i++)

         if(str[i]>=u&&ove[i]<=v) ret+=sum[i];

         else for(LL j=max(str[i],u);j<=min(ove[i],v);j++) ret+=num[j]+tag[i];

     return ret;

 }

 int main()

 {

     scanf("%lld",&n);

     for(LL i=;i<=n;i++)

         scanf("%lld",num+i);

     Build();

     scanf("%lld",&q);

     for(;q--;)

     {

         scanf("%lld%lld%lld",&op,&u,&v);

         if(op==)

         {

             scanf("%lld",&x);

             Update(u,v,x);

         }

         else printf("%lld\n",Query(u,v));

     }

     return ;

 }

巴特西

COdeVS——T 1082 线段树练习 3 (分块练习）

http://codevs.cn/problem/1082/

最新文章

热门文章