题意：给你一个长n（1-1e5）数列，和m(1-1e5)个询问，问你l - r 中是否出现下凹。
解题思路：一开始以为直接找下凹就行，后来发现数组元素相等时比较难处理，所以还是需要一个映射删掉相等的再处理比较好。
解题代码：
1 // File Name: 279c.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月09日 星期一 08时19分05秒 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 26 using namespace std; 27 int n ,m ; 28 int a[100005]; 29 int dp[100005]; 30 int fa[100005]; 31 int tmp[100005]; 32 int main(){ 33 scanf("%d %d",&n,&m); 34 for(int i = 1;i <= n;i ++) 35 scanf("%d",&tmp[i]); 36 int ok = 0 ; 37 int t = 1 ; 38 a[1] = tmp[1]; 39 fa[1] = 1; 40 for(int i = 2;i <= n;i ++) 41 { 42 if(tmp[i] == a[t]) 43 { 44 fa[i] = t; 45 continue; 46 }else{ 47 t ++ ; 48 fa[i] = t; 49 a[t] = tmp[i]; 50 } 51 } 52 for(int i = 2;i < t;i ++) 53 { 54 if(a[i] < a[i-1] && a[i] <a[i+1]) 55 { 56 dp[i] = 1 ; 57 } 58 } 59 for(int i = 1;i <= t;i ++) 60 { 61 dp[i] = dp[i-1] +dp[i]; 62 //printf("%d ",dp[i]); 63 } 64 //printf(" "); 65 int l, r; 66 for(int i = 1;i <= m;i ++) 67 { 68 scanf("%d %d",&l,&r); 69 if(dp[fa[r]-1] - dp[fa[l]] > 0 ) 70 printf("No "); 71 else printf("Yes "); 72 } 73 return 0; 74 }