转载

Codeforces Round #239 (Div. 1)C， 407C

题目链接：http://codeforces.com/contest/407/problem/C

题目大意：给一个长度为n的数列，m次操作，每次操作由（li, ri, ki）描述，表示在数列li到ri这段数字上分别加上C(j-li+ki, ki)，要求输出最后得到的序列。（% 1e9+7）

数据范围：1<=n, m<=10^5, a[i]<=10^9

思路：区间上加一个函数，在线求和，这种题目之前遇到过。记得是在区间上加kd(l<=k<=r)，解法是线段树处理，由于等差+等差=等差，所以满足线段树lazy所要求的一致性和可计算性。在上题中我发现他所加的值是杨辉三角的某一列，通过观察发现是一个k阶等差数列。因此我便用了上述思想解决。然而绞尽脑汁思考一天并没有想到可行的标记方法，不能做到不同阶等差数列的统一。因此看了官方题解，竟然是离线做法，方法如下：

先考虑简单情况，k=0时，问题演变成一个传统的问题：区间加1，离线询问各值。在l处+1，r + 1处-1，求前缀和即可。我们称1，-1的操作为原态，如果对原态做一次前缀和，我们便轻松得到了在各区间加上一个数字之后的结果，继续拓展，对这个区间再取前缀和，便得到了各区间加上一个一阶等差数列之后的结果，以此类推，对原态数列做k次取前缀和的操作，便得到了各区间加上首项为1的k - 1阶等差数列的结果，这里的前提是在r + 1的位置原态时并不是-1，应当是一个-比较大的数字（仔细考虑）。

回归原题，如果原题中的所有操作k都相同，我们就可以对于每个操作在初始全部为0的数列中“搭好原态”，也就是在l处+1，在r + 1处减一个什么值，然后再对原态序列做k + 1次取前缀和操作，加上题目中给的序列，便得到了答案。然而题目中的k不尽相同，如令K=Max（ki）,我们最多做K次迭代前缀，在中途“不失时机”地插入原态，让他们“搭顺风车”，达到目标，不失为一种不错的策略。

上述思路大体描述完，对于实现官方给了一个很值得借鉴的技巧。由于“搭顺风车”的想法可想不可写，于是我们把原全为0的序列拉开变成K层这种初始序列，每一层代表了某阶等差数列的原态，最终我们逐层递推更新既清晰有简单。代码中是k阶等差把原态插入k + 1层，最后从K倒推到0，经过迭代，a[0][i]数列加上题目给的数字便是答案。

最后一个问题就是上述原态中r + 1中究竟该减多少的问题，其实就是各阶等差数列的前r-l+r项和，在杨辉三角里很容易发现是通过有规律的组合数表示的，这样对于每次操作，把k + 1层的l处+1, 前0 - k + 1层的r + 1处减掉相应的组合数即可。

1 #include <cstdio>  2 #include <cstdlib>  3 #include <cstring>  4 #include <cmath>  5 #include <ctime>  6 #include <cctype>  7 #include <climits>  8 #include <string>  9 #include <algorithm> 10 using namespace std; 11 typedef long long LL; 12 13 const int MaxN = 1e5, MaxK = 100, Pt = 1e9 + 7; 14 int n, m; 15 LL orig[MaxN + 5], a[MaxK + 5][MaxN + 5], c[MaxN + 3 * MaxK][MaxK + 5]; 16 17 void Init() 18 { 19 scanf("%d%d", &n, &m); 20 for (int i = 1; i <= n; i++) scanf("%I64d", &orig[i]); 21 c[0][0] = 1; 22 for (int i = 1; i <= n + 2 * MaxK; i++) 23  { 24 c[i][0] = 1; 25 for (int j = 1; j <= MaxK; j++) 26 c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Pt; 27  } 28 } 29 30 void Solve() 31 { 32 int l, r; 33 int K = 0, k; 34 for (int i = 1; i <= m; i++) 35  { 36 scanf("%d%d%d", &l, &r, &k); 37 K = max(K, k); 38 a[k + 1][l] = (a[k + 1][l] + 1) % Pt; 39 for (int j = 1; j <= k + 1; j++) 40 a[j][r + 1] = (a[j][r + 1] - c[r - l + k - j + 1][k - j + 1] + Pt) % Pt; 41  } 42 for (int i = K; i >= 0; i--) 43  { 44 LL s = 0; 45 for (int j = 1; j <= n; j++) 46  { 47 s = (s + a[i + 1][j]) % Pt; 48 a[i][j] = (s + a[i][j]) % Pt; 49  } 50  } 51 for (int i = 1; i <= n; i++) a[0][i] = (a[0][i] + orig[i]) % Pt; 52 for (int i = 1; i <= n; i++) printf("%I64d ", a[0][i]); 53 } 54 55 int main() 56 { 57  Init(); 58  Solve(); 59 }  View Code

总结：

1.高阶等差数列可由多次前缀和迭代定义，这样就更贴近了阶的定义（迭代的过程）。用线性的递推代替了求通项等等麻烦的事情。

2.一维操作过于繁琐时可考虑把一维的拉开变成多维，逐层处理，最后叠加。可以让代码清晰简单。

正文到此结束