题意：给你一个数组，现在让你分割这个数组，要求是数组每一块最少 L 个数 且 每一块中 极值 不超过 s
解题思路：
1）dp，从1 到 n 预处理左边的不能更新 离i 最近的点 ，然后线段树找出最小值。
2）当丑的人还在想着如何二分线段树，帅的人已经用STL解决了所有问题，可以用 STL 维护从左到右 极值 不超过 s的 最长连续段，第一次看到这么写。Orz。
解题代码：
1 // File Name: 487b.1.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月23日 星期一 15时24分56秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define N 100007 26 using namespace std; 27 multiset<int> st,rt; 28 int dp[N],n,l,s,a[N]; 29 int main(){ 30 scanf("%d %d %d",&n,&s,&l); 31 for(int i = 1;i <= n;i ++) 32 scanf("%d",a+i); 33 for(int i = 1,j = 1;i <= n;i ++) 34 { 35 st.insert(a[i]); 36 for(;*st.rbegin() - *st.begin() > s;j ++) 37 { 38 st.erase(st.find(a[j])); 39 if(i - j >= l) rt.erase(rt.find(dp[j-1])); 40 } 41 if(i - j + 1 >= l) rt.insert(dp[i-l]); 42 if(rt.begin() == rt.end()) dp[i] = N; 43 else dp[i] = *rt.begin() + 1; 44 } 45 printf("%d ",dp[n] >= N?-1:dp[n]); 46 return 0; 47 }