原题链接：https://vjudge.net/problem/UVA-1471
分类：数据结构
备注：使用数据结构加速算法
好题，有时间回来再试一试。
f[i]表示往右最长延申长度，g[i]表示往左的长度。
val[i]<val[j]时，答案为g[i]+f[j]
枚举每一个点val[i]，要找左边值小于val[i]的val[j]点，其中g[j]最大，那么可以一直保存前面遍历过的点，如果有val[j]<=val[j’]&&g[j]>=g[j’]，那么val[j’]就应该删去。
一直动态维护，按val从大到小排列。每次二分查找第一个val[j]<val[i]的地方，这个g[j]必定是最大的。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int t,n,val[maxn],f[maxn],g[maxn];
struct node{int val,g;node(int _v,int _g):val(_v),g(_g){}bool operator < (const node& rhs) const {return val<rhs.val;}
};
set<node>st;
int main(void){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",val+i);if(n==1){printf("1\n");continue;}g[0]=1;for(int i=1;i<n;i++)if(val[i]>val[i-1])g[i]=g[i-1]+1;else g[i]=1;f[n-1]=1;for(int i=n-2;i>=0;i--)if(val[i+1]>val[i])f[i]=f[i+1]+1;else f[i]=1;int ans=1;st.clear();st.insert(node(val[0],g[0]));for(int i=1;i<n;i++){node x(val[i],g[i]);set<node>::iterator it=st.lower_bound(x);//<=bool flg=true;if(it!=st.begin()){--it;int len=(*it).g+f[i];ans=max(ans,len);if((*it).g>=x.g)flg=false;}if(flg){st.erase(x);st.insert(x);it=st.find(x);++it;while(it!=st.end()&&(*it).g<=x.g&&(*it).val>=x.val)st.erase(it++);}} printf("%d\n",ans);}return 0;
}