Description

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

Input Format

每組側資的第一行有一個正整數 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;
}