蓝书紫书上都有的一道题。。。这里就懒得说题解了。
但是我竟然WA了6次！为什么呢？？？
一开始没看见连续子序列。。。。。
后来插入的时候忘判断了是不是比前驱大。。。。
所以我们只需要维护一个权值递增(这个set已经帮你维护好了)并且长度递增(这个需要插入的时候判断)的set就好了、。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<algorithm>
#define ll long long
#define maxn 200005
using namespace std;
struct node{
int num,len;
bool operator <(const node &U)const{
return num==U.num?len<U.len:num<U.num;
}
};
set<node> s;
set<node> ::iterator it;
int f[maxn],n,m,ky,ans;
int qz[maxn],hz[maxn];
int num[maxn],a[maxn],T;
inline void init(){
s.clear(),ans=0;
}
inline void ins(int x,int y){
node now=(node){x,y};
it=s.lower_bound((node){x,0});
while(it->len<=y){
s.erase(it);
it=s.lower_bound((node){x,0});
}
s.insert(now);
}
inline void solve(){
s.insert((node){0,0});
s.insert((node){1<<30,1<<30});
qz[1]=1;
for(int i=2;i<=n;i++) qz[i]=(a[i]>a[i-1]?qz[i-1]:0)+1;
hz[n]=1;
for(int i=n-1;i;i--) hz[i]=(a[i]<a[i+1]?hz[i+1]:0)+1;
for(int i=1;i<=n;i++){
it=s.lower_bound((node){a[i],0});
node now=*(--it);
ans=max(ans,hz[i]+now.len);
if(qz[i]>it->len) ins(a[i],qz[i]);
}
}
int main(){
scanf("%d",&T);
while(T--){
init();
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i),num[i]=a[i];
sort(num+1,num+n+1);
ky=unique(num+1,num+n+1)-num-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(num+1,num+ky+1,a[i])-num;
solve();
printf("%d\n",ans);
}
return 0;
}