No Monotone Triples

题目传送门

引

$Dilworth定理$ 有点意思

解法

---

首先 $|b|\le 4$ ,考虑证明，证明如下：

用反证法证明
假设 $|b|>4$ , $len$ 为 $b$ 的最长不降子序列的长度.
若 $len\ge 3$ ,显然存在单调三元组，取最长不降子序列中的任意三个元素即可；
若 $len<3$ , 则 $b$ 至少由 $3$ 个不降子序列覆盖完，根据 $Dilworth定理$ ，我们知道 $b$ 的最长下降子序列的长度至少为 $3$ .
故该假设不成立，所以 $|b|\le 4$ , $QED$ .

关于 $Dilworth定理$ 的证明 ，可以根据偏序关系建立有向边，形成 $DAG$ ,自己尝试证明一下

---

接下来考虑求出以 $i$ 为右端点 ，最大的左端点
先考虑 $|b|=3$ 时
那么 $b_2$ 一定是 $b$ 的极值，枚举 $b_2$ , 找到最大的 $b_1$ 与 最小的 $b_3$ ，更新 $b_3$ 的左端点
用个数据结构维护
为 $O(n\log n)$的

---

$|b|=4$ 时
有 $b_1,b_4$ 一定不是极值 ，
从前往后维护 单增 和 单减 的 单调栈
对于每个位置 $i$ ,找到最大的 $j$ 满足 不在两个栈中，且 区间 $（j,i）$ 可以取到两个栈的的元素
用 $Set$ 维护就好
为 $O(n\log n)$ 的

---

Code

#include

using namespace std;

template  void setmax(T& a, const T& b) { if (b > a) a = b; }

int N,Q;

int main() {
  scanf("%d%d",&N,&Q);
	vector A(N);
	for (int &x:A) scanf("%d",&x);

	vector> ans3(N, array({-1, -1, -1}));
	vector> ans4(N, array({-1, -1, -1, -1}));

	vector highs, lows;

	vector inHighs(N), inLows(N);

	set nonHigh,nonLow,neither;
  
	for (int i = 0; i < N; i++) {
		while (!highs.empty() && A[i] > A[highs.back()]) {
			inHighs[highs.back()] = false;
			nonHigh.insert(highs.back());
			if (!inLows[highs.back()]) neither.insert(highs.back());
			highs.pop_back();
		}
		while (!lows.empty() && A[i] < A[lows.back()]) {
			inLows[lows.back()] = false;
			nonLow.insert(lows.back());
			if (!inHighs[lows.back()]) neither.insert(lows.back());
			lows.pop_back();
		}//maintain the monotonic stack

		inHighs[i] = inLows[i] = true;
		highs.push_back(i); lows.push_back(i);

		auto highIt = lower_bound(highs.begin(), highs.end(), i, [&A](int x, int y) { return A[x] > A[y]; } );
		auto lowIt = lower_bound(lows.begin(), lows.end(), i, [&A](int x, int y) { return A[x] < A[y]; } );
		int lastHigh = highIt == highs.begin() ? -1 : *--highIt;
		int lastLow = lowIt == lows.begin() ? -1 : *--lowIt;

		if (!highs.empty() && !lows.empty() && !neither.empty() && *neither.begin() < min(lastHigh, lastLow)) {
			auto it = neither.lower_bound(min(lastHigh, lastLow));
			--it;
			int bestNeither = *it;
			int c = *lower_bound(highs.begin(), highs.end(), bestNeither);
			int d = *lower_bound(lows.begin(), lows.end(), bestNeither);
			ans4[i] = {bestNeither, min(c, d), max(c, d), i};
		}

		if (!highs.empty() && !nonHigh.empty() && *nonHigh.begin() < lastHigh) {
			auto it = nonHigh.lower_bound(lastHigh);
			--it;
			int bestNonHigh = *it;
			setmax(ans3[i], {bestNonHigh, *lower_bound(highs.begin(), highs.end(), bestNonHigh), i});
		}
		if (!lows.empty() && !nonLow.empty() && *nonLow.begin() < lastLow) {
			auto it = nonLow.lower_bound(lastLow);
			--it;
			int bestNonLow = *it;
			setmax(ans3[i], {bestNonLow, *lower_bound(lows.begin(), lows.end(), bestNonLow), i});
		}
	}

	for (int i = 1; i < N; i++) {
		ans3[i] = max(ans3[i], ans3[i-1]);
		ans4[i] = max(ans4[i], ans4[i-1]);
	}

	for (int q = 0; q < Q; q++) {
		int L, R; cin >> L >> R;
		L--, R--;
		if (ans4[R][0] >= L) {
			puts("4");
      for(int x:ans4[R]) printf("%d ",x+1);
		} else if (ans3[R][0] >= L) {
      puts("3");
      for(int x:ans3[R]) printf("%d ",x+1);
		} else {
      puts("0");
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

结

另外，这题对代码实现能力要求也挺高的