POJ/3468.cc

   1 #pragma comment(linker, "/STACK:16777216")
   2 #include <stdio.h>
   3 #define maxn 100000
   4
   5 typedef long long int64;
   6
   7 int cnt=0;
   8
   9 struct Segment {
  10         int l,r;
  11         int64 sum,add;
  12         struct Segment *ch[2];
  13 } pool[maxn*8],*T,*nil;
  14
  15 typedef struct Segment Segment;
  16
  17 void down(Segment *T) {
  18         if (T->add) {
  19                 T->ch[0]->add+=T->add;
  20                 T->ch[1]->add+=T->add;
  21                 T->ch[0]->sum+=((T->ch[0]->r - T->ch[0]->l + 1)*T->add);
  22                 T->ch[1]->sum+=((T->ch[1]->r - T->ch[1]->l + 1)*T->add);
  23                 T->add=0;
  24         }
  25 }
  26
  27 Segment* Init(int l, int r) {
  28         Segment *T=&pool[cnt++];
  29         T->l=l;
  30         T->r=r;
  31         if (l==r) {
  32                 scanf("%lld",&T->sum);
  33                 T->ch[0]=T->ch[1]=nil;
  34                 return T;
  35         }
  36         int mid=(l+r)>>1;
  37         T->ch[0]=Init(l,mid);
  38         T->ch[1]=Init(mid+1,r);
  39         T->sum = T->ch[0]->sum + T->ch[1]->sum;
  40         return T;
  41 }
  42
  43 int64 Query(Segment *T, int l, int r) {
  44         if (l <= T->l && T->r <= r) return T->sum;
  45         down(T);
  46         int mid=(T->l + T->r)>>1;
  47         int64 res=0;
  48         if (l<=mid) res+=Query(T->ch[0],l,r);
  49         if (r>mid) res+=Query(T->ch[1],l,r);
  50         return res;
  51 }
  52
  53 void Modify(Segment *T, int l, int r, int64 val) {
  54         if (l <= T->l && T->r <= r) {
  55                 T->sum+=(T->r - T->l + 1)*val;
  56                 T->add+=val;
  57                 return;
  58         }
  59         down(T);
  60         int mid=(T->l + T->r)>>1;
  61         if (l<=mid) Modify(T->ch[0],l,r,val);
  62         if (r>mid) Modify(T->ch[1],l,r,val);
  63         T->sum = T->ch[0]->sum + T->ch[1]->sum;
  64 }
  65
  66 int main() {
  67         int n,m,l,r;
  68         int64 val;
  69         char opt;
  70         scanf("%d%d",&n,&m);
  71         nil=&pool[cnt++];
  72         T=Init(1,n);
  73         while (m--) {
  74                 scanf(" %c %d %d",&opt,&l,&r);
  75                 switch (opt) {
  76                         case 'Q':
  77                                 printf("%lld\n",Query(T,l,r));
  78                                 break;
  79                         case 'C':
  80                                 scanf("%lld",&val);
  81                                 Modify(T,l,r,val);
  82                                 break;
  83                 }
  84         }
  85         return 0;
  86 }