poj 3468 块状链表区间修改+区间查询

经典的线段树题目，也可以用块链来做。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cmath>
  5 using namespace std;
  6 
  7 typedef __int64 ll;
  8 const ll M = 400;
  9 ll b[M][M];
 10 ll add[M];
 11 ll sum[M];
 12 ll n, m, ps;
 13 
 14 ll query( ll l, ll r )
 15 {
 16     ll cur = l / ps, ncur = r / ps;
 17     l = l % ps, r = r % ps;
 18     ll res = 0;
 19     for ( ll i = cur + 1; i <= ncur - 1; i++ )
 20     {
 21         res += sum[i] + ps * add[i];
 22     }
 23     if ( cur != ncur )
 24     {
 25         for ( ll j = l; j < ps; j++ )
 26         {
 27             res += b[cur][j];
 28         }
 29         res += add[cur] * ( ps - l );
 30         for ( ll j = 0; j <= r; j++ )
 31         {
 32             res += b[ncur][j];
 33         }
 34         res += ( r + 1 ) * add[ncur];
 35     }
 36     else
 37     {
 38         for ( ll j = l; j <= r; j++ )
 39         {
 40             res += b[cur][j];
 41         }
 42         res += add[cur] * ( r - l + 1 );
 43     }
 44     return res;
 45 }
 46 
 47 void update( ll l, ll r, ll d )
 48 {
 49     ll cur = l / ps, ncur = r / ps;
 50     l = l % ps, r = r % ps;
 51     for ( ll i = cur + 1; i < ncur; i++ )
 52     {
 53         add[i] += d;
 54     }
 55     if ( cur != ncur )
 56     {
 57         for ( ll j = l; j < ps; j++ )
 58         {
 59             b[cur][j] += d;
 60         }
 61         sum[cur] += d * ( ps - l );
 62         for ( ll j = 0; j <= r; j++ )
 63         {
 64             b[ncur][j] += d;
 65         }
 66         sum[ncur] += d * ( r + 1 );
 67     }
 68     else
 69     {
 70         for ( ll j = l; j <= r; j++ )
 71         {
 72             b[cur][j] += d;
 73         }
 74         sum[cur] += ( r - l + 1 ) * d;
 75     }
 76 }
 77 
 78 int main ()
 79 {
 80     ps = 350;
 81     while ( scanf("%I64d%I64d", &n, &m) != EOF )
 82     {
 83         memset( sum, 0, sizeof(sum) );
 84         memset( add, 0, sizeof(add) );
 85         for ( ll i = 0; i < n; i++ )
 86         {
 87             ll tmp; scanf("%I64d", &tmp);
 88             b[i / ps][i % ps] = tmp;
 89             sum[i / ps] += tmp;
 90         }
 91         char op[2];
 92         ll l, r, d;
 93         while ( m-- )
 94         {
 95             scanf("%s%I64d%I64d", op, &l, &r);
 96             l--, r--;
 97             if ( op[0] == 'Q' )
 98             {
 99                 printf("%I64d
", query( l, r ));
100             }
101             else
102             {
103                 scanf("%I64d", &d);
104                 update( l, r, d );
105             }
106         }
107     }
108     return 0;
109 }
poj 3468 块状链表 区间修改+区间查询

poj 3468 块状链表区间修改+区间查询
