POJ 3468 A Simple Problem with Integers 解题报告

题意：区间更新，区间求和

解题思路：本来以为自己搞出了区间更新A这题很简单呢，没想到这里面还有这么多学问，不过幸好坚持没有看解题报告和代码，自己对线段树的理解又更深了一层！主要是向下更新的时候有问题，自己调试的时候又出现了一个非常sb的常识性错误，然后就wrong到现在，主要的解题思路还是线段树的区间操作

解题代码：

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #define MAXN 200005
  5 struct node
  6 {
  7     long long left ,right,mid;
  8     long long  num ;
  9     long long cover;
 10 } tree[MAXN*4];
 11 long long a[MAXN];
 12 long long L(long long c)
 13 {
 14     return 2*c;
 15 }
 16 long long R(long long c)
 17 {
 18     return 2*c + 1;
 19 }
 20 void up(long long c)
 21 {
 22     tree[c].num = tree[L(c)].num + tree[R(c)].num;
 23 }
 24 void build(long long c, long long p ,long long v )
 25 {
 26    tree[c].left = p ;
 27    tree[c].right = v;
 28    tree[c].mid = (p + v)/2;
 29    tree[c].num =0 ;
 30    tree[c].cover = 0 ;
 31    if(p == v )
 32    {
 33      tree[c].num = a[p];
 34      return ;
 35    }
 36   build(L(c),p,tree[c].mid);
 37   build(R(c),tree[c].mid +1,v);
 38   up(c);
 39 }
 40 
 41 void update(long long c, long long p , long long v , long long value)
 42 {
 43     if(p <= tree[c].left && v >= tree[c].right)
 44     {
 45         tree[c].num = tree[c].num + (tree[c].right - tree[c].left +1) * value;
 46         tree[c].cover =tree[c].cover +value ;
 47         return;
 48     }
 49    if(tree[c].cover != 0 )
 50    {
 51       tree[L(c)].cover = tree[L(c)].cover + tree[c].cover;
 52       tree[L(c)].num = tree[L(c)].num + (tree[L(c)].right - tree[L(c)].left +1) * tree[c].cover;
 53       tree[R(c)].cover =tree[R(c)].cover + tree[c].cover;
 54       tree[R(c)].num = tree[R(c)].num +(tree[R(c)].right - tree[R(c)].left + 1)* tree[c].cover ;
 55       tree[c].cover  = 0 ;
 56    }
 57    if(v <= tree[c].mid )  update(L(c),p,v,value);
 58    else if(p > tree[c].mid) update(R(c),p,v,value);
 59    else
 60    {
 61      update(L(c),p,tree[c].mid,value);
 62      update(R(c),tree[c].mid+ 1, v , value);
 63    }
 64    up(c);
 65 
 66 }
 67 
 68 long long  tsum = 0 ;
 69 void getsum(long long c, long long p ,long long v )
 70 {
 71     if(p <= tree[c].left && v >= tree[c].right)
 72     {
 73         tsum += tree[c].num;
 74         return;
 75     }
 76    if(tree[c].cover != 0 )
 77    {
 78      tree[L(c)].cover = tree[L(c)].cover + tree[c].cover;
 79       tree[L(c)].num = tree[L(c)].num + (tree[L(c)].right - tree[L(c)].left +1) * tree[c].cover;
 80       tree[R(c)].cover =tree[R(c)].cover + tree[c].cover;
 81       tree[R(c)].num = tree[R(c)].num +(tree[R(c)].right - tree[R(c)].left + 1)* tree[c].cover ;
 82       tree[c].cover  = 0 ;
 83    }
 84    if(v <= tree[c].mid) getsum(L(c),p,v);
 85    else if(p > tree[c].mid) getsum(R(c),p,v);
 86    else
 87    {
 88      getsum(L(c),p,tree[c].mid);
 89      getsum(R(c),tree[c].mid +1 ,v );
 90    }
 91 
 92 
 93 }
 94 int main()
 95 {
 96     long long  n ,m;
 97     while(scanf("%I64d %I64d",&n,&m) != EOF)
 98     {
 99 
100       for (long long i = 1;i <= n;i ++)
101         scanf("%I64d",&a[i]);
102       build(1,1,n);
103       char str[10];
104       for(long long i =1 ;i <= m;i ++)
105       {
106           long long a, b ,c;
107           scanf("%s",str);
108           if(str[0] == 'Q')
109           {
110             scanf("%I64d %I64d",&a,&b);
111             tsum = 0 ;
112             getsum(1,a,b);
113             printf("%I64d
",tsum);
114           }
115           else
116           {
117             scanf("%I64d %I64d %I64d",&a,&b,&c);
118             update(1,a,b,c);
119           }
120 
121 
122       }
123     }
124     return  0 ;
125 }

View Code

没有梦想，何谈远方