http://cplusoj.com/d/senior/p/SS241007B

显然这题是一个二维数点问题，我们要求在确定 $[l,r]$ 下 $i$ 个数的最大值：

• $l<i<r$
• $a_r<i<a_l$

考场上想了各种扫描线，cdq，kdtree，可持久化，树套树都想不起这个套路是啥，这其实是一个经典的套路，窗口的星星

矩阵和点的相互转化

而在此题，我们也就看每个 $i$ 能作用哪些 $[l,r]$，我们把这个覆盖区域变成一个矩形，那么就是求最多矩形覆盖的有多少，这个可以就是裸的二维数点了

而为了让它张成一个矩形，我们发现只需要维护前后的上升/下降序列作为关键点即可

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)#define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else#define debug(...) void(0)#define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k, T;
int a[N], x, y, s1, s2; 
int lmx[N], rmx[N], lst, ans; int find_L(int i) {int l = 1, r = lmx[i], mid; while(l < r) {mid = (l + r) >> 1; if(a[lmx[mid]] >= a[i]) r = mid; else l = mid + 1; }return l; 
}int find_R(int i) {int l = rmx[i], r = n, mid; while(l < r) {mid = (l + r + 1) >> 1; if(a[rmx[mid]] <= a[i]) l = mid; else r = mid - 1; }return r; 
}namespace Scan {struct Segment_tree {#define ls (k << 1)#define rs (k << 1 | 1) #define mid ((l + r) >> 1)int tag[N << 2], mx[N << 2]; void push_down(int k) {tag[ls] += tag[k]; tag[rs] += tag[k]; mx[ls] += tag[k]; mx[rs] += tag[k]; tag[k] = 0; }void add(int k, int l, int r, int x, int y, int z) {if(l >= x && r <= y) return tag[k] += z, mx[k] += z, void(); push_down(k); if(x <= mid) add(ls, l, mid, x, y, z); if(y >= mid + 1) add(rs, mid + 1, r, x, y, z); mx[k] = max(mx[ls], mx[rs]); }#undef ls#undef rs#undef mid}Seg;struct node { int l, r, v; };vector<node>G[N]; void insert(int lx, int ly, int rx, int ry) {
//		debug("Polygon\n%lld %lld\n%lld %lld\n%lld %lld\n%lld %lld\n", 
//			lx, rx, lx, ry + 1, ly + 1, ry + 1, ly + 1, rx); debug("%lld %lld %lld %lld\n", lx, ly, rx, ry); G[rx].pb({lx, ly, 1}); G[ry + 1].pb({lx, ly, -1}); }int run() {int i, ans = 0; for(i = 1; i <= n; ++i) {for(auto t : G[i]) {Seg.add(1, 1, n, t.l, t.r, t.v); }ans = max(ans, Seg.mx[1]); }return ans; }
}signed main()
{freopen("inverse.in", "r", stdin);freopen("inverse.out", "w", stdout);
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}n = read(); for(i = 1; i <= n; ++i) a[i] = read(); for(i = 1, lst = 0; i <= n; ++i) {if(a[i] > lst) lst = a[i], lmx[i] = i; else lmx[i] = lmx[i - 1]; }for(i = n, lst = 1e9; i >= 1; --i) {if(a[i] < lst) lst = a[i], rmx[i] = i; else rmx[i] = rmx[i + 1]; }for(i = 1; i <= n; ++i) debug("%lld ", lmx[i]); debug("\n"); for(i = 1; i <= n; ++i) debug("%lld ", rmx[i]); debug("\n"); for(i = 1; i <= n; ++i) {int L = find_L(i), R = find_R(i); Scan :: insert(L, lmx[i], rmx[i], R); }ans = Scan :: run(); printf("%lld", 2 * ans - 3); return 0;
}