[TIOJ] 2039. AI-666 賺多少

題目連結:https://tioj.infor.org/problems/2039

---

注意！以下是努力壓常數後過的$O(N \log N)$作法(雖然好像大家也都是$O(N \log C)$的aliens優化解)。
這裡講一下我的作法好了，首先我們將題目視成不斷將k變大並詢問當前最大是多少。若是只有一個k的時候，我們顯然是要找一組左低右高的區間$[a_l, a_r]$，那變成兩個的時候，我們發現其實有幾種可能，一種是在$l$左邊繼續找一組左低右高的區間，或是在$r$右邊找一組左低右高的區間，或是在$(l, r)$中找一組左高右低的區間，把他們的差加進答案即可。
所以我們可以用線段樹維護我們想知道某個區間內左高右低或左低右高的最大值，這樣我們就是每次從heap拿出一個最大的區間加進答案後，把它左右中三個區間同時再塞到heap裡，繼續做到直到沒有東東可以拿，或達到k就好。
不過一般的線段樹實作會TLE，所以我寫了個zkw加上自己寫heap後就可以AC了XD

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

namespace {
#define FORCE_INLINE __attribute__((always_inline))

constexpr int INF = 1 << 30;
constexpr int maxn = 2'000'000;

template <typename T1, typename T2> struct Pair {
	T1 first;
	T2 second;
};

struct V {
	int val, pos_small, pos_big;
};

struct S {
	Pair<int, int> lo, hi;
	V v[2];
	FORCE_INLINE S(Pair<int, int> small, Pair<int, int> big, V v0,
				   V v1) noexcept
		: lo{small}, hi{big}, v{v0, v1} {};
	FORCE_INLINE S(Pair<int, int> small = {INF, -1},
				   Pair<int, int> big = {-INF, -1}) noexcept
		: lo{small}, hi{big}, v{{hi.first - lo.first, lo.second, hi.second},
								{hi.first - lo.first, lo.second, hi.second}} {};
} s[maxn * 2];

template <int type> S comb(const S &lhs, const S &rhs) {
	S ret;
	ret.lo = lhs.lo.first < rhs.lo.first ? lhs.lo : rhs.lo;
	ret.hi = lhs.hi.first > rhs.hi.first ? lhs.hi : rhs.hi;
	if (type != 1) {
		ret.v[0] = {rhs.hi.first - lhs.lo.first, lhs.lo.second, rhs.hi.second};
		if (ret.v[0].val < lhs.v[0].val)
			ret.v[0] = lhs.v[0];
		if (ret.v[0].val < rhs.v[0].val)
			ret.v[0] = rhs.v[0];
	}
	if (type != 0) {
		ret.v[1] = {lhs.hi.first - rhs.lo.first, rhs.lo.second, lhs.hi.second};
		if (ret.v[1].val < lhs.v[1].val)
			ret.v[1] = lhs.v[1];
		if (ret.v[1].val < rhs.v[1].val)
			ret.v[1] = rhs.v[1];
	}
	return ret;
}

template <bool rev> V query(int l, int r, int n) {
	S lhs, rhs;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1)
			lhs = comb<rev>(lhs, s[l++]);
		if (r & 1)
			rhs = comb<rev>(s[--r], rhs);
	}
	return comb<rev>(lhs, rhs).v[rev];
}

class {
	bool has_popped;
	size_t n;
	tuple<V, int, int> a[maxn / 2 + 1];
	void remove_popped() noexcept {
		if (not has_popped)
			return;
		size_t i = 1;
		auto o = move(a[n + 1]);
		int val = get<0>(o).val;
		while (i <= n / 2) {
			size_t child = i * 2;
			if (child + 1 <= n and
				get<0>(a[child]).val < get<0>(a[child + 1]).val)
				child += 1;
			if (val < get<0>(a[child]).val) {
				a[i] = move(a[child]);
				i = child;
			} else {
				break;
			}
		}
		a[i] = move(o);
		has_popped = false;
	}

  public:
	FORCE_INLINE bool empty() const noexcept { return n == 0; }
	void emplace(const V &v, int x, int y) noexcept {
		n += 1;
		size_t i;
		if (has_popped) {
			for (i = 1; i <= n / 2;) {
				size_t child = i * 2;
				if (child + 1 <= n and
					get<0>(a[child]).val < get<0>(a[child + 1]).val)
					child += 1;
				if (v.val < get<0>(a[child]).val) {
					a[i] = move(a[child]);
					i = child;
				} else {
					break;
				}
			}
			has_popped = false;
		} else {
			for (i = n; i > 1;) {
				if (get<0>(a[i / 2]).val < v.val) {
					a[i] = move(a[i / 2]);
					i = i / 2;
				} else {
					break;
				}
			}
		}
		a[i] = {v, x, y};
	}
	FORCE_INLINE tuple<V, int, int> pop() noexcept {
		remove_popped();
		n -= 1;
		has_popped = true;
		return a[1];
	}
} pq;

#undef FORCE_INLINE

} // namespace

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		s[i + n] = {{x, i}, {x, i}};
	}
	for (int i = n - 1; i > 0; --i)
		s[i] = comb<2>(s[i * 2], s[i * 2 + 1]);
	pq.emplace(query<0>(0, n, n), 0, n);
	int ans = 0;
	while (not pq.empty()) {
		auto [o, l, r] = pq.pop();
		if (o.val <= 0)
			break;
		ans += o.val;
		if (--k == 0)
			break;
		if (o.pos_small < o.pos_big) {
			if (o.pos_small != l)
				pq.emplace(query<0>(l, o.pos_small, n), l, o.pos_small);
			if (o.pos_small + 1 != o.pos_big)
				pq.emplace(query<1>(o.pos_small + 1, o.pos_big, n),
						   o.pos_small + 1, o.pos_big);
			if (o.pos_big + 1 != n)
				pq.emplace(query<0>(o.pos_big + 1, r, n), o.pos_big + 1, r);
		} else {
			if (o.pos_big != l)
				pq.emplace(query<1>(l, o.pos_big, n), l, o.pos_big);
			if (o.pos_big + 1 != o.pos_small)
				pq.emplace(query<0>(o.pos_big + 1, o.pos_small, n),
						   o.pos_big + 1, o.pos_small);
			if (o.pos_small + 1 != n)
				pq.emplace(query<1>(o.pos_small + 1, r, n), o.pos_small + 1, r);
		}
	}
	cout << ans << '\n';
	return 0;
}