Codeforces Round #333 (Div. 1) B. Lipshitz Sequence
解説をチラチラ見た。
問題
数列h[1...n]を引数とする関数L(h)を以下のように定義する。
サイズがn(n<=10^5)の数列aと、q(q<=100)個のクエリが与えられる。
各クエリについて、L(数列aのの区間に含まれる、全ての連続的な部分列)を計算せよ。
解法
まず、L(h)を計算するにあたって、明らかにj=i+1のところだけしか見なくていい。(気づけなかった)
クエリ(l, r)について、区間[l, l]からちょっとずつ右に増やしていって[l, r]の答えを求めることを考える。
部分列[l, i]を1つ右に伸ばした時、新たに追加された要素a[i + 1]より大きく、最も近い要素がa[w]であったとする。
すると、答えは (a[l] + ... + a[w]) + a[i + 1]*(i + 1 - w)だけ増える。
stack術を使えばwを探す処理はクエリ1つにつきO(n)で行える。(参考:
CODE FESTIVAL 予選B 解説 のD問題)
(a[l] + ... + a[w])の部分も累積和を持って更新しながらやれば一緒にO(n)で収まる。
クエリがq個なので全体でO(nq)。
実装
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 100000; int N, Q, A[MAX_N]; signed main() { cin >> N >> Q; for (int i = 0; i < N; i++) { cin >> A[i]; if (i > 0) A[i - 1] = abs(A[i] - A[i - 1]); } N--; for (int q = 0; q < Q; q++) { int l, r; cin >> l >> r; l--; r--; //[l, r) 0-indexed int sum[MAX_N] = {}; stack<int> s; int ans = 0; for (int i = l; i < r; i++) { while (!s.empty() && A[s.top()] <= A[i]) s.pop(); //ansの加算 int cnt = i - l + 1; if (!s.empty()) cnt = i - s.top(); ans += cnt*A[i]; if (!s.empty()) ans += sum[s.top()]; //sumの更新 sum[i] = cnt*A[i]; if (!s.empty()) sum[i] += sum[s.top()]; s.push(i); } printf("\t%lld\n", ans); } return 0; }