Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Description

給定一長串的數字 a[]，
找到一段最長的區間 [l, r]，符合 a[l] <= a[k] <= a[r] for k in [l, r]。

Input Format

第一行有一個正整數 T，代表有幾組測試資料。

每組側資的第一行有一個正整數 n (n < 100,000)。
第二行有 n 個正整數表示 a[1], a[2], ..., a[n]，所有數字介於 1 和 n 之間。

Output Format

對於每組測資，輸出一行符合的最長區間長度。

Sample Input

3
5
1 2 3 4 5
5
5 4 3 2 1
5
3 1 2 5 4

Sample Output

5
1
3

---

題目解法：

窮舉區間最右側，找到相對應的最左側。
對於區間最右側的 a[l]，先找到 a[right_possible] >= a[l]。
其中符合 right_possible >= l, right_possible 符合的最小值。

接著查找 a[l, right_possible] 的最大值在哪個位置即可。

很明顯地，第一段落可以藉由掃描線的思路從左邊掃描到右邊，依序查找 tree[0, a[l]] 的最小值。
同時也逐步更新 tree[a[l]] = min(tree[a[l]], l)。

而在 "查找 a[l, right_possible] 的最大值在哪個位置" 可以藉由線段樹的區間查找來完成。

這個思路慢了些，不過還算是相當直觀的作法。

#include <stdio.h> 
#include <stack>
#include <algorithm>
using namespace std;
int A[100005];
pair<int, int> Tree[262144 + 10];
#define oo 0x7f7f7f7f
void build(int k, int l, int r) {
	if(l > r)	{
		Tree[k] = make_pair(-oo, -1);
		return ;
	}
	if(l == r) {
		Tree[k] = make_pair(A[l], l);
		return ;
	}
	int m = (l+r)/2;
	build(k<<1, l, m);
	build(k<<1|1, m+1, r);
	Tree[k] = max(Tree[k<<1], Tree[k<<1|1]);
}
pair<int, int> query(int k, int l, int r, int ql, int qr) {
    if(l > r)    return make_pair(-oo, -1);
    if(ql <= l && r <= qr)
        return Tree[k];
    int m = (l + r)/2;
    if(m >= qr)
        return query(k<<1, l, m, ql, qr);
    if(m < ql)
        return query(k<<1|1, m+1, r, ql, qr);
    return max(query(k<<1, l, m, ql, qr),
                query(k<<1|1, m+1, r, ql, qr));
}
int BIT[262144];
void modifyBIT(int idx, int val, int L) {
	while(idx <= L) {
		BIT[idx] = min(BIT[idx], val);
		idx += idx&(-idx);
	}
}
int queryBIT(int idx) {
	int ret = oo;
	while(idx) {
		ret = min(ret, BIT[idx]);
		idx -= idx&(-idx);
	}
	return ret;
}
int main() {
	int testcase, n;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &n);
		int ret = 1, x;
		stack<int> stk;
		for(int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		build(1, 0, n-1);
		for(int i = n; i >= 1; i--)
			BIT[i] = oo;
		for(int i = n-1; i >= 0; i--) {
			modifyBIT(A[i], i, n);
			int r = queryBIT(A[i]-1);
			if(r == oo)
				r = n-1;
			pair<int, int> LL = query(1, 0, n-1, i, r);
			ret = max(ret, LL.second - i + 1);
		}
		printf("%d\n", ret);
	}
	return 0;
}