064.md

064 - Uplift (★3)

解答

#include <iostream>
#include <vector>
#include <numeric> // std::adjacent_difference(), std::accumulate()
#include <cmath> // std::abs()

int main()
{
	// N 個の区画, Q 回の地殻変動
	int N, Q;
	std::cin >> N >> Q;

	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}

	// 直前の区画からの標高差を格納する配列 (long long 型)
	std::vector<long long> diffs(A.size());

	// 隣接する要素間の差を計算
	//
	// 例:
	//     A = {  3,  1,  4,  1,  5 } のとき
	// diffs = {  3, -2,  3, -3,  4 }
	//
	std::adjacent_difference(A.begin(), A.end(), diffs.begin());

	// diffs[1] ～ diffs[N - 1] の絶対値の合計が「不便さ」の初期値 (long long 型で計算)
	long long a = std::accumulate(diffs.begin() + 1, diffs.end(), 0LL,
		[](auto x, auto y) { return (x + std::abs(y)); });

	// それぞれの地殻変動について
	for (int i = 0; i < Q; ++i)
	{
		int L, R, V;
		std::cin >> L >> R >> V;

		// 今回の地殻変動における不便さの変化
		long long delta = 0;

		////////////////////////
		//
		// 地殻変動の開始地点における変化
		//
		if (2 <= L) // L == 1 のときは不便さの変化に寄与しないのでスキップ
		{
			const auto oldDiff = diffs[L - 1];

			// (L-2) 区から (L-1) 区に行くときの不便さを更新
			diffs[L - 1] += V;

			// 不便さがどれだけ変化したか
			delta += (std::abs(diffs[L - 1]) - std::abs(oldDiff));
		}

		////////////////////////
		//
		// 地殻変動の終了地点における変化
		//
		if (R < N) // R == N のときは不便さの変化に寄与しないのでスキップ
		{
			const auto oldDiff = diffs[R];

			// (R-1) 区から (R) 区に行くときの不便さを更新
			diffs[R] -= V;

			// 不便さがどれだけ変化したか
			delta += (std::abs(diffs[R]) - std::abs(oldDiff));
		}

		// 全体の不便さを更新
		a += delta;

		// 解答を出力
		std::cout << a << '\n';
	}
}