POJ 3468 A Simple Problem with Integers

题意：给N个数，有两组操作：

(1)对某个区间[a, b]中所有的数都增加c

(2)求某个区间[a, b]个数的和

共操作Q次，每次只输出操作(2)的结果

第二棵线段树……TUT……

需要用到延迟标记，每次更新不用到达叶子节点，只需要在标记上进行累加，当询问的时候再将标记向下传递。

  1 #include <cstdio>
  2 #include <cstdlib>
  3 
  4 const int MAXN = 100000 + 5;
  5 
  6 struct TNode
  7 {
  8     int l, r;
  9     long long int sum;
 10     long long int mark;
 11     TNode *l_child, *r_child;
 12 };
 13 
 14 TNode Tree[ MAXN + MAXN ];
 15 int cnt;
 16 long long int Sum;
 17 
 18 void Build( int l, int r, TNode *Td )
 19 {
 20     Td -> l = l;
 21     Td -> r = r;
 22 
 23     Td -> mark = 0;
 24 
 25     if ( l == r )
 26     {
 27         scanf("%lld", &Td->sum );
 28         return;
 29     }
 30 
 31     ++cnt;
 32     Td -> l_child = &Tree[cnt];
 33     Build( l, ( l + r ) / 2, Td -> l_child );
 34 
 35     ++cnt;
 36     Td -> r_child = &Tree[cnt];
 37     Build( ( l + r ) / 2 + 1, r, Td -> r_child );
 38 
 39     Td -> sum = Td -> l_child -> sum + Td -> r_child -> sum;
 40 
 41     return;
 42 }
 43 
 44 void Update( int st, int ed, int &e, TNode *Td )
 45 {
 46     if ( st == Td -> l && ed == Td -> r )
 47     {
 48         Td -> mark += e;
 49         return;
 50     }
 51 
 52     Td -> sum += e * ( ed - st + 1 );
 53 
 54     int mid = ( Td -> l + Td -> r ) / 2;
 55 
 56     if ( ed <= mid )
 57         Update( st, ed, e, Td -> l_child );
 58     else if ( st > mid )
 59         Update( st, ed, e, Td -> r_child );
 60     else
 61     {
 62         Update( st, mid, e, Td -> l_child );
 63         Update( mid + 1, ed, e, Td -> r_child );
 64     }
 65 }
 66 
 67 void Query( int st, int ed, TNode *Td )
 68 {
 69     if ( st == Td -> l && ed == Td -> r )
 70     {
 71         Sum += Td ->sum + Td -> mark * ( ed - st + 1 );
 72         return;
 73     }
 74 
 75     if ( Td -> mark )
 76     {
 77         Td -> l_child -> mark += Td ->mark;
 78         Td -> r_child -> mark += Td ->mark;
 79         Td -> sum += Td -> mark * ( Td -> r - Td -> l + 1 );
 80         Td -> mark = 0;
 81     }
 82 
 83     int mid = ( Td -> l + Td -> r ) / 2;
 84 
 85     if ( ed <= mid )
 86         Query( st, ed, Td->l_child );
 87     else if ( st > mid )
 88         Query( st, ed, Td->r_child );
 89     else
 90     {
 91         Query( st, mid, Td->l_child );
 92         Query( mid + 1, ed, Td->r_child );
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     int N, Q;
 99     while ( scanf( "%d%d", &N, &Q ) != EOF )
100     {
101         Build( 1, N, Tree );
102 
103         char ch;
104         int a, b, e;
105         for ( int i = 0; i < Q; ++i )
106         {
107             getchar();
108             ch = getchar();
109             switch ( ch )
110             {
111             case 'Q':
112                 Sum = 0;
113                 scanf( "%d%d", &a, &b );
114                 Query( a, b, Tree );
115                 printf( "%lld\n", Sum );
116                 break;
117 
118             case 'C':
119                 scanf( "%d%d%d", &a, &b, &e );
120                 Update( a, b, e, Tree );
121                 break;
122             }
123         }
124     }
125     return 0;
126 }