题目描述：

1276 岛屿的数量

有N个岛连在一起形成了一个大的岛屿，如果海平面上升超过某些岛的高度时，则这个岛会被淹没。原本的大岛屿则会分为多个小岛屿，如果海平面一直上升，则所有岛都会被淹没在水下。

给出N个岛的高度。然后有Q个查询，每个查询给出一个海平面的高度H，问当海平面高度达到H时，海上共有多少个岛屿。例如：

岛屿的高度为：{2, 1, 3, 2, 3}, 查询为：{0, 1, 3, 2}。

当海面高度为0时，所有的岛形成了1个岛屿。

当海面高度为1时，岛1会被淹没，总共有2个岛屿{2} {3, 2, 3}。

当海面高度为3时，所有岛都会被淹没，总共0个岛屿。

当海面高度为2时，岛0, 1, 3会被淹没，总共有2个岛屿{3} {3}。

收起

输入

第1行：2个数N, Q中间用空格分隔，其中N为岛的数量，Q为查询的数量(1 <= N, Q <= 50000)。第2 - N + 1行，每行1个数，对应N个岛屿的高度(1 <= A[i] <= 10^9)。第N + 2 - N + Q + 1行，每行一个数，对应查询的海平面高度(1 <= Q[i] <= 10^9)。

输出

输出共Q行，对应每个查询的岛屿数量。

输入样例

5 4213230132

思路：

先不考虑边界细节，每去掉一个 谷 峰，岛屿数量减少一个，每 去掉一个 谷底，岛屿数量增加 一个。

所以对于每次查询，就是寻找比当前查询高度小的谷底和谷峰数量，对本题而言，O（q*N）的复杂度显然超时，

所以可以对查询以及谷峰底序列排序，离线查询，遍历查询序列，用过的谷峰底不再用，时间复杂度O（Q+N+QlogQ

+NlogN）。

然后边界处理1和n的位置，可以发现当a【1】>a【2】、a【n】>a【n-1】时，是可以当作谷锋处理的。

特殊情况的处理即没有谷峰和谷底的时候，即高度全一样或者单调，此时特判即可。

代码实现：

#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<cstdio>#include<algorithm>#define LL long long#define INF 0x3f3f3f3fusing namespace std;const int N=2e5+100;int arr[N];pair<int,int>pek[N];int tot;pair<int,int> query[N];int ans[N];int main(){int n,q;while(cin>>n>>q){int maxs=INF;for(int i=1;i<=n;i++)cin>>arr[i],maxs=max(maxs,arr[i]);for(int i=2;i<n;i++){if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])pek[++tot]=make_pair(arr[i],1);if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])pek[++tot]=make_pair(arr[i],0);}if(tot==0||n==1){for(int i=1;i<=q;i++){int x;cin>>x;if(x>=maxs)ans[i]=0;else ans[i]=1;}for(int i=1;i<=q;i++)cout<<ans[i]<<endl;continue;}if(arr[1]>arr[2])pek[++tot]=make_pair(arr[1],1);if(arr[n]>arr[n-1])pek[++tot]=make_pair(arr[n],1);//for(int i=1;i<=tot;i++)cout<<pek[i].first<<" "<<pek[i].second<<endl;for(int i=1;i<=q;i++){cin>>query[i].first;query[i].second=i;}sort(query+1,query+1+q);sort(pek+1,pek+1+tot);int num1=0,num2=0;int p=1;for(int i=1;i<=q;i++){while(pek[p].first<=query[i].first&&p<=tot){if(pek[p].second==0){num2++;}else num1++;p++;}ans[query[i].second]=1+num2-num1;}for(int i=1;i<=q;i++)cout<<ans[i]<<endl;}return 0;}