4bitにっき

ぽよ

Codeforces Round #333 (Div. 1) B. Lipshitz Sequence

解説をチラチラ見た。

問題

Problem - B - Codeforces

数列h[1...n]を引数とする関数L(h)を以下のように定義する。
f:id:winjii:20160523001152j:plain

サイズがn(n<=10^5)の数列aと、q(q<=100)個のクエリ (l_{1}, r_{1}) ... (l_{q}, r_{q}) が与えられる。
各クエリについて、L(数列aの [l_{i}, r_{i}] の区間に含まれる、全ての連続的な部分列)を計算せよ。

解法

まず、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;
}