[典型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;
}
}