本文主要是介绍21年广东工业大学第十五届文远知行杯程序设计竞赛 B 找山坡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
如果两个相同的数字x之间的数字都>=x，称之为山坡，求最长山坡距离。
解析
每个数字做一条映射链，存储每个数字的下标，遍历下标的映射链，用双指针的想法去取每个合法区间。每个区间用ST表维护预处理迅速得到结果。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int STMax[N][23];
int lg[N];
int query(int l,int r ){int k=lg[r-l+1];return min(STMax[l][k],STMax[r-(1<<k)+1][k]);
}
map<int,vector<int>>mp;
int main() {int n,m;for(int i=2;i<N;i++){lg[i]=lg[i/2]+1;}scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);STMax[i][0]=x;mp[x].push_back(i);}for(int j=1;j<=lg[n];j++){for(int i=1;i+(1<<j)-1<=n;i++){STMax[i][j]=min(STMax[i][j-1],STMax[i+(1<<(j-1))][j-1]);
// cout<<i<<" "<<j<<" "<<STMax[i][j]<<endl;}}int res=0;for(auto item : mp){auto list =item.second;int sz=list.size();if(sz>1){int i=0,j=i+1;while(j<sz){int L=list[i],R=list[j];int value=query(L,R);if(value>=item.first){res=max(res,R-L);}else{i=j;}j++;}}}cout<<res;
}这篇关于21年广东工业大学第十五届文远知行杯程序设计竞赛 B 找山坡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
