CodeChef Chef and Churu 分块

题意：

　　有一个长度为n的序列，有n个函数f(l, r) = Σai (l <= i <= r)，有两种操作，把某个数修改，查询区间函数和。

分析：

　　这是一道很经典的分块题目，具体算法就是大力分块。

　　把序列分块，块内记录数的前缀和，并记录块间的前缀和，对于一个函数的计算可以O(1)。

　　把函数分块，块内记录函数的前缀和，以及每个数的修改对该块的贡献次数，并记录块间的前缀和。

　　修改时，函数的块全部更新；查询时，中间的块直接O(1)，两边零碎的直接算O(1)。程序：

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <string>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 using namespace std;
  9 
 10 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
 11 #define mset(a, b) memset(a, b, sizeof(a))
 12 const int maxn = 1e5+10;
 13 typedef unsigned long long LL;
 14 int n, m, a[maxn], bel[maxn], st[350];
 15 struct Node
 16 {
 17     int l, r;
 18     Node(int l = 0, int r = 0): l(l), r(r) {}
 19 }b[maxn];
 20 int cnt[350][maxn], c[maxn];
 21 LL s1_a[maxn], s1_b[maxn];
 22 LL s2_a[maxn], s2_b[maxn];
 23 
 24 LL calc1(int l, int r)
 25 {
 26     if (bel[l] == bel[r]) return s1_a[r]-s1_a[l]+a[l];
 27     else
 28     {
 29         LL ret = s1_a[st[bel[l]+1]-1]-s1_a[l]+a[l];
 30         ret += s1_a[r]-s1_a[st[bel[r]]]+a[st[bel[r]]];
 31         ret += s2_a[bel[r]-1]-s2_a[bel[l]];
 32         return ret;
 33     }
 34 }
 35 
 36 void build_b1()
 37 {
 38     REP(i, 1, m)
 39     {
 40         REP(j, 1, n) c[j] = 0;
 41         REP(j, st[i], st[i+1]-1) c[b[j].l] ++, c[b[j].r+1] --;
 42         REP(j, 1, n) cnt[i][j] = cnt[i][j-1]+c[j];
 43     }
 44 }
 45 
 46 void build_a()
 47 {
 48     REP(i, 1, m)
 49     {
 50         s1_a[st[i]] = a[st[i]];
 51         REP(j, st[i]+1, st[i+1]-1) s1_a[j] = s1_a[j-1]+a[j];
 52         s2_a[i] = s2_a[i-1]+s1_a[st[i+1]-1];
 53     }
 54 }
 55 
 56 void build_b2()
 57 {
 58     REP(i, 1, m)
 59     {
 60         s1_b[st[i]] = calc1(b[st[i]].l, b[st[i]].r);
 61         REP(j, st[i]+1, st[i+1]-1) s1_b[j] = s1_b[j-1]+calc1(b[j].l, b[j].r);
 62         s2_b[i] = s2_b[i-1]+s1_b[st[i+1]-1];
 63     }
 64 }
 65 
 66 void modify(int x, int y)
 67 {
 68     LL t_sum = 0, k = y-a[x];
 69     a[x] = y;
 70     REP(i, x, st[bel[x]+1]-1) s1_a[i] += k;
 71     REP(i, bel[x], m) s2_a[i] += k;
 72     REP(i, 1, m) t_sum += cnt[i][x]*k, s2_b[i] += t_sum;
 73 }
 74 
 75 LL calc2(int l, int r)
 76 {
 77     LL ret = 0;
 78     if (bel[l] == bel[r])
 79         REP(i, l, r) ret += calc1(b[i].l, b[i].r);
 80     else
 81     {
 82         ret = s2_b[bel[r]-1]-s2_b[bel[l]];
 83         REP(i, l, st[bel[l]+1]-1) ret += calc1(b[i].l, b[i].r);
 84         REP(i, st[bel[r]], r) ret += calc1(b[i].l, b[i].r);
 85     }
 86     return ret;
 87 }
 88 
 89 int main()
 90 {
 91 //    freopen("a.in", "r", stdin);
 92 //    freopen("a.out", "w", stdout);
 93     scanf("%d", &n);
 94     REP(i, 1, n) scanf("%d", &a[i]);
 95     REP(i, 1, n) scanf("%d %d", &b[i].l, &b[i].r);
 96     int block_siz = int(sqrt(n));
 97     REP(i, 1, n) 
 98     {
 99         bel[i] = i/block_siz+1;
100         if (i == 1 || bel[i] != bel[i-1]) st[bel[i]] = i;
101     }
102     m = n/block_siz+1, st[m+1] = n+1;
103     build_b1(), build_a(), build_b2();
104     int Q;
105     scanf("%d", &Q);
106     while (Q --)
107     {
108         int ty, x, y;
109         scanf("%d %d %d", &ty, &x, &y);
110         if (ty == 1) modify(x, y);
111         else printf("%lld
", calc2(x, y));
112     }
113     return 0;
114 }

View Code