网易互娱最后一道洪水题求思路

首尾都加最小负值，O(N)记录峰值和谷值，排序峰值，排序谷值，对于每次洪水输出=高于洪水高度的峰值数量-高于洪水高度的谷值数量O(lgN)。我大概是这么写的。。

让人感觉应该是树状数组之类的

遍历一遍判断，只能过40%。过10%可定是特殊情况错了。

#include<bits/stdc++.h> using namespace std; int main() {     int n,q;     int y,tmp;     vector<int> a;     cin>>n;     for(int i=0;i<n;i++){         cin>>tmp;         a.push_back(tmp);     }     cin>>q;     for(int i=0;i<q;i++){         cin>>y;         int ans = 0;         for(int j=0;j<n;j++)             if(j==0&&a[j]>y|| j>0&&a[j]>y && a[j-1]<=y)                 ans++;           cout<<ans<<endl;     } } 暴力过了40%

你看一下这样，时间复杂度为N，如果第一个塔小于洪水高度，设置为0，count加1，以后的每个塔高度小于洪水并且它前一个塔为0的话就加1，同时塔的高度设置为0。遍及一遍即可，不知道能不能过。抛砖引玉，大佬勿嘲

暴力过了40…