F - A Simple Problem with Integers

Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu

Description

给出了一个序列，你需要处理如下两种询问。

"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。

"Q a b" 询问[a, b]区间中所有值的和。

Input

第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.

第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。

接下来Q行询问，格式如题目描述。

Output

对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。

Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample Output

//自己写，又超时了，网上看了别人的才过的，在类里面要增加一个积累量这个数据，这样，增加命令的时候只要将特定区间积累量加起来并且num+总和，不必遍历到每一个叶节点，但是在查询时，还是要释放，因为，可能查的区间，在积累的这个区间只占一部分。

这样节约了时间，好像叫lazy的思想

 #include <stdio.h>

 #include <string.h>

 struct

 {

     int l;

     int r;

     double num;

     double Inc;

 }shu[];

 void Init (int left,int right,int k)

 {

     shu[k].l=left;

     shu[k].r=right;

     shu[k].Inc=;

     if(left==right)

     {

         scanf("%lf",&shu[k].num);

         return;

     }

     int mid=(left+right)/;

     Init(left,mid,*k);

     Init(mid+,right,*k+);

     shu[k].num=shu[*k].num+shu[*k+].num;

 }

 void insert(int left,int right,double c,int k)

 {

     if (shu[k].l==left&&shu[k].r==right)//到某个区间

     {

         shu[k].Inc+=c;

         return;

     }

     shu[k].num+=(right-left+)*c;

     int mid=(shu[k].l+shu[k].r)/;

     if (right<=mid)

         insert(left,right,c,*k);

     else if (left>mid)

         insert (left,right,c,*k+);

     else

     {

         insert(left,mid,c,*k);

         insert(mid+,right,c,*k+);

     }

 }

 double query(int left,int right,int k)

 {

     if (shu[k].l==left&&shu[k].r==right)//

     {

         return shu[k].num+(shu[k].r-shu[k].l+)*shu[k].Inc;

     }

     int mid=(shu[k].l+shu[k].r)/;

     if(shu[k].Inc!=)//将这个区间的积累量释放

     {

         shu[k].num+=(shu[k].r-shu[k].l+)*shu[k].Inc;//自己先加上

         insert(shu[k].l,mid,shu[k].Inc,*k);

         insert(mid+,shu[k].r,shu[k].Inc,*k+);

         shu[k].Inc=;

     }

     if (left>mid)         return  query(left,right,*k+);

     else if (right<=mid)  return query(left,right,*k);

     else

         return query(left,mid,*k)+query(mid+,right,*k+);

 }

 int main()

 {

     int Q;

     int all_p,a,b;

     double c;

     char comend;

     while (scanf("%d%d",&all_p,&Q)!=EOF)

     {

         Init(,all_p,);

         while (Q--)

         {

             getchar();

             scanf("%c",&comend);

             scanf("%d%d",&a,&b);

             if (comend=='Q')    printf("%.0lf\n",query(a,b,));

             if (comend=='C')

             {

                 scanf("%lf",&c);

                 insert(a,b,c,);

             }

         }

     }

     return ;

 }

巴特西

A Simple Problem with Integers(线段树)

F - A Simple Problem with Integers

最新文章

热门文章