POJ 3468 线段树成段更新懒惰标记-白红宇

POJ 3468 线段树成段更新懒惰标记

阅读量：6292 次

发布时间：2019-06-22

本文共 3244 字，大约阅读时间需要 10 分钟。

A Simple Problem with Integers

Time Limit:5000MS Memory Limit:131072K

Case Time Limit:2000MS

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

题解：本题也是线段树系列的模板题之一，要求的是成段更新+懒惰标记。PS：原题的说明有问题，上面说的“C a b c”中的c的范围其实在int32之外，需要使用long long，否则定是WA，真心坑爹，连WA多次，还是在discuss中看到的原因。

稍微讲解下代码中的一些细节: step<<1 与 step<<1|1，意思分别是step*2 和step*+1，具体为什么，可以回去复习一下位运算

转自

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
             9 10 #define N 100010 11 #define M 15 12 #define mod 1000000007 13 #define mod2 100000000 14 #define ll long long 15 #define maxi(a,b) (a)>(b)? (a) : (b) 16 #define mini(a,b) (a)<(b)? (a) : (b) 17 18 using namespace std; 19 20 int n,q; 21 int x[N]; 22 char ch; 23 int a,b,c; 24 25 struct node 26 { 27 ll mark,sum; 28 }tree[4*N]; 29 30 void update(int l,int r,int i) 31 { 32 if(!tree[i].mark) return; 33 int mid=(l+r)/2; 34 tree[2*i].sum+=tree[i].mark*(ll)(mid-l+1); 35 tree[2*i+1].sum+=tree[i].mark*(ll)(r-mid); 36 tree[2*i].mark+=tree[i].mark; 37 tree[2*i+1].mark+=tree[i].mark; 38 tree[i].mark=0; 39 40 } 41 42 ll query(int tl,int tr,int l,int r,int i) 43 { 44 if(tl>r || tr
             
              r || tr
              
               =r){ 59 tree[i].sum+=val*(ll)(r-l+1); 60 tree[i].mark+=val; 61 return; 62 } 63 update(l,r,i); 64 int mid=(l+r)/2; 65 addd(tl,tr,l,mid,2*i,val); 66 addd(tl,tr,mid+1,r,2*i+1,val); 67 tree[i].sum=tree[2*i].sum+tree[2*i+1].sum; 68 } 69 70 void build_tree(int l,int r,int i) 71 { 72 if(l==r){ 73 tree[i].sum=x[l]; 74 return; 75 } 76 int mid=(l+r)/2; 77 build_tree(l,mid,2*i); 78 build_tree(mid+1,r,2*i+1); 79 tree[i].sum=tree[2*i].sum+tree[2*i+1].sum; 80 } 81 82 int main() 83 { 84 int i; 85 // freopen("data.in","r",stdin); 86 //scanf("%d",&T); 87 //for(int cnt=1;cnt<=T;cnt++) 88 //while(T--) 89 while(scanf("%d%d",&n,&q)!=EOF) 90 { 91 // printf(" %d %d \n",n,q); 92 for(i=1;i<=n;i++) scanf("%d",&x[i]); 93 // printf(" 1\n"); 94 memset(tree,0,sizeof(tree)); 95 build_tree(1,n,1); 96 97 98 // printf(" 2\n"); 99 getchar();100 while(q--){101 // printf(" 3\n");102 scanf("%c",&ch);103 // printf(" %c\n",ch);104 if(ch=='C'){105 //printf(" 31\n");106 scanf("%d%d%d",&a,&b,&c);107 getchar();108 addd(a,b,1,n,1,c);109 110 }111 else{112 // printf(" 32\n");113 scanf("%d%d",&a,&b);114 getchar();115 ll ans=query(a,b,1,n,1);116 printf("%I64d\n",ans);117 }118 }119 }120 121 return 0;122 }

转载于:https://www.cnblogs.com/njczy2010/p/3917501.html

你可能感兴趣的文章