[POJ3468] A Simple Problem with Integers（分块）

题目链接：http://poj.org/problem?id=3468
区间查询，区间更新。额外用一个add维护某个块内所有值的更新情况，查询的时候加上这个值。
  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <cassert>
  8 #include <cstdio>
  9 #include <bitset>
 10 #include <vector>
 11 #include <deque>
 12 #include <queue>
 13 #include <stack>
 14 #include <ctime>
 15 #include <set>
 16 #include <map>
 17 #include <cmath>
 18 using namespace std;
 19 
 20 typedef long long LL;
 21 const int maxn = 100100;
 22 int n, q, sz;
 23 int be[maxn];
 24 LL val[maxn], add[maxn], block[maxn];
 25 char cmd[5];
 26 
 27 void query(int& l, int& r) {
 28     LL ret = 0;
 29     for(int i = l; i <= r; ) {
 30         if(i % sz == 0 && i + sz <= r) {
 31             ret += block[be[i]];
 32             i += sz;
 33         }
 34         else {
 35             ret += val[i] + add[be[i]];
 36             i++;
 37         }
 38     }
 39     printf("%lld
", ret);
 40 }
 41 
 42 void update(int& l, int& r, LL& v) {
 43     for(int i = l; i <= r; ) {
 44         if(i % sz == 0 && i + sz <= r) {
 45             block[be[i]] += v * sz;
 46             add[be[i]] += v;
 47             i += sz;
 48         }
 49         else {
 50             val[i] += v;
 51             block[be[i]] += v;
 52             i++;
 53         }
 54     }
 55 }
 56 
 57 inline bool scan_d(int &num) {
 58     char in;bool IsN=false;
 59     in=getchar();
 60     if(in==EOF) return false;
 61     while(in!='-'&&(in<'0'||in>'9')) in=getchar();
 62     if(in=='-'){ IsN=true;num=0;}
 63     else num=in-'0';
 64     while(in=getchar(),in>='0'&&in<='9'){
 65         num*=10,num+=in-'0';
 66     }
 67     if(IsN) num=-num;
 68     return true;
 69 }
 70 
 71 inline bool scan_d(LL &num) {
 72     char in;bool IsN=false;
 73     in=getchar();
 74     if(in==EOF) return false;
 75     while(in!='-'&&(in<'0'||in>'9')) in=getchar();
 76     if(in=='-'){ IsN=true;num=0;}
 77     else num=in-'0';
 78     while(in=getchar(),in>='0'&&in<='9'){
 79         num*=10,num+=in-'0';
 80     }
 81     if(IsN) num=-num;
 82     return true;
 83 }
 84 
 85 int main() {
 86     // freopen("in", "r", stdin);
 87     // freopen("out", "w", stdout);
 88     int x, y;
 89     LL v;
 90     while(~scanf("%d", &n)) {
 91         scan_d(q);
 92         memset(block, 0, sizeof(block));
 93         sz = sqrt((double)n) * 2;
 94         for(int i = 0; i < n; i++) {
 95             scan_d(val[i]);
 96             block[be[i]=i/sz] += val[i];
 97             add[i] = 0;
 98         }
 99         while(q--) {
100             scanf("%s", cmd);
101             if(cmd[0] == 'Q') {
102                 scan_d(x); scan_d(y);
103                 query(--x, --y);
104             }
105             else {
106                 scan_d(x); scan_d(y); scan_d(v);
107                 update(--x, --y, v);
108             }
109         }
110     }
111     return 0;
112 }