题意：
给一个长度为n（n <= 200000） 的序列，，你删除一段连续的子序列，使得剩下的序列拼接起来，有一个最长的连续递增子序列
思路：
设f[i] 和g[i] 分别表示 以i为开始 和 以i为结束 的最长连续递增序列长度
首先可以想到枚举i和j，然后计算max_len = f[i] + g[i];
但是这种枚举方法的时间复杂度是O(n^2),这是在加上预处理f[i] 和g[i] 的前提下
所以需要想一个更加优化的方法，避免那么多枚举：
所以想到 只枚举f[i], 通过某种方法快速的找到合适的 g[j]
在这个查找的过程中，首先可以排除掉一些不可能成为最优解的元素。这是一个常见的思路，在求解LIS的O(n*log(n))算法中，也用到了这种思路。
然后就是在查找的过程中，借助了数据结构中的SET来实现快速的插入(insert)和查询（lower_bound ）和查找（find）,另外对其迭代器的正确操作也是很重要的（iterater）
code:
#include<cstdio>#include<cstring>#include<algorithm>#include<set>using namespace std;typedef pair<int,int> pii;const int maxn = 200005;int a[maxn],g[maxn],f[maxn];set<pii> s;int n;void init(){for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}g[1] = 1;for(int i = 2; i <= n; i++){if(a[i] > a[i-1]) g[i] = g[i-1] + 1;else g[i] = 1;}f[n] = 1;for(int i = n-1; i >= 1; i–){if(a[i] < a[i+1]) f[i] = f[i+1] + 1;else f[i] = 1;}s.clear();s.insert(make_pair(a[1],g[1]));int ans = 1;for(int i = 2; i <= n; i++){pii c = make_pair(a[i],g[i]);set<pii>::iterator it = s.lower_bound(c);bool keep = true;if(it != s.begin()){pii last = *(–it);int len = f[i] + last.second;ans = max(ans, len);if(last.second >= c.second) keep = false;}if(keep){s.erase(c);s.insert(c);it = s.find(c);it++;while(it != s.end() && it->first > c.first && it->second <= c.second) s.erase(it++);}}printf("%d\n",ans);}int main(){int t;scanf("%d",&t);while(t–){scanf("%d",&n);init();//solve();}return 0;}
这道题目确实能让我学到很多东西。包括思路方面，STL的使用上，以及对问题的预处理等等
人生，一场人喧鼓响的戏，我只是一个平凡的过客，
