[典型90] 064 - Uplift（★3）

Q. https://atcoder.jp/contests/typical90/tasks/typical90_bl

クエリが範囲で与えられるけど、その通りにA[]を更新するとO(N^2)で間に合わないのはわかる。どうしよう？
1. 差に着目して考察
2. クエリの両端2か所だけが更新箇所とわかる。

1. 差をとってみる。

Q. N=6
A[] = 3   6   9  12  15  18
D[] =   3   3   3   3   3 
    (A[1]-A[0])

とする。
1) クエリ[3, 6, 1]がきた場合
L, Rを0-indexedとみなして、
[2, 5, 1]とする。

A[] = 3   6  [10  13  16  19]
D[] =   3   4    3   3   3
           ~~~ 増えるのはD[1]だけ
D[1] += 1
D[L-1] += V が一般化。

1) クエリ[1, 4, 1]がきた場合
L, Rを0-indexedとみなして、
[0, 3, 1]とする。

A[] = [4   7  11   14]  16  19
D[] =    3   4    3   2   3
                     ~~~ 減るのはD[3]だけ
D[3] -= 1
D[R] -= V が一般化。

Dの取り方が、A[i+1] - A[i]なので、
L側を処理するときに、(A[i+1]+V) - A[i] として "+V" の処理。
R側を処理するときに、A[i+1] - (A[i]+V) として "-V" の処理になっている。

[L,R], V が与えられたときに、
D[L-1] += V
D[R] -= Vすればいい。

2. 解答はなんだろう
1. 最初に差の総和 = 不便さをとっておく。
2. クエリがきたら、差の更新箇所だけに着目。その不便さを除いて、更新後に不便さを取得しなおす

Q. N=6
A[] = 3   6   9  12  15  18
D[] =   3   3   3   3   3 
    (A[1]-A[0])

1.) 不便さ
ans = 3+3+3+3+3 // 15

1) クエリ[3, 6, 1]がきた場合
L, Rを0-indexedとみなして、
[2, 5, 1]とする。

A[] = 3   6  [10  13  16  19]
D[] =   3   4    3   3   3
           ~~~ 増えるのはD[1]だけ

1.) 不便さが変わらない場所の総和を求める。
                     
ans -= abs(D[1]) // 3 0 3 3 3
                      ~ D[1]がこの後変わるから、D[1]以外の総和だけにする。
2.) 地殻変動
D[1] += 1

3.) 不便さの適応
ans += abs(D[1]) // 3 4 3 3 3 
                      ~ D[1]が適応された。


1) クエリ[1, 4, 1]がきた場合
L, Rを0-indexedとみなして、
[0, 3, 1]とする。

A[] = [4   7  11   14]  16  19
D[] =    3   4    3   2   3
                     ~~~ 減るのはD[3]だけ

1.) 不便さが変わらない場所の総和を求める。
                     
ans -= abs(D[3]) // 3 4 3 0 3
                          ~ D[3]がこの後変わるから、D[3]以外の総和だけにする。
2.) 地殻変動
D[3] -= 1

3.) 不便さの適応
ans += abs(D[3]) // 3 4 3 2 3 
                          ~ D[3]が適応された。

実装

ll N, Q;
ll A[100010];
ll D[100010];

int main() {
 cincout();

 cin >> N >> Q;
 rep(i, N) cin >> A[i];
 ll sum = 0;
 rep(i, N - 1) {
   D[i] = A[i + 1] - A[i];
   sum += abs(D[i]);
 }

 rep(i, Q) {
   ll L, R, V;
   cin >> L >> R >> V;
   --L, --R;

   // L
   if (L > 0) {
     sum -= abs(D[L - 1]);
     D[L - 1] += V;
     sum += abs(D[L - 1]);
   }

   // R
   if (R < N - 1) {
     sum -= abs(D[R]);
     D[R] -= V;
     sum += abs(D[R]);
   }
   cout << sum << endl;
 }
}

https://atcoder.jp/contests/typical90/submissions/28364268