UVA 1471 Defense Lines 单调队列 -

题目地址：http://vjudge.net/problem/UVA-1471

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b)  for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=200000+5;
int a[maxn],f[maxn],g[maxn];
struct Node
{int a,g;bool operator < (const Node& src) const {return a<src.a;}
};
set<Node> s;
int main(int argc, char const *argv[])
{int T,n; scanf("%d",&T);while(T--&&scanf("%d",&n)==1){REP(i,1,n) scanf("%d",&a[i]);if(n==1) {printf("1\n"); continue;}g[1]=1;REP(i,2,n) if(a[i]>a[i-1]) g[i]=g[i-1]+1;else g[i]=1;f[n]=1;REPD(i,n-1,1) if(a[i]<a[i+1]) f[i]=f[i+1]+1;else f[i]=1;s.clear(); s.insert(Node{a[1],g[1]});int ans=1;REP(i,2,n){Node c=Node{a[i],g[i]};set<Node>::iterator it=s.lower_bound(c);bool keep=true;if(it!=s.begin()){Node last=*(--it);ans=max(ans,f[i]+last.g);if(last.g>=g[i]) keep=false;}if(keep){s.erase(c);s.insert(c);it=s.find(c);it++;while(it!=s.end()&&c.a<=it->a&&c.g>=it->g) s.erase(it),it++;}}printf("%d\n", ans);}return 0;
}