题目链接：Problem - 91B - Codeforces
题目大意： 给你一个长度为n的数组， 让求对于每个数，比它小的数值。即满足： （i < j）a[i] > a[j], 让求 j - i - 1 最大。 没有输出 -1
原题见链接
看到有最小值，容易想到采用特殊的数据结构来维护， 然后再思考其他的方法来利用。
思路：
1.采用ST表或者线段树维护好最小值， 然后再到上做dfs， 求满足情况的最远下标。
2. 首先后面先判断是否还有比他小的数，没有直接 打印 -1， 有的话， 再到[i+1, n] 上做dfs, 对于dfs的简化， 由于发现 如果 [l, mid] , [mid+1, r], 都满足， 其实可以直接搜索右边， 因为要的是最大下标。 l, mid, r 见代码。 而对于判断是否有数满足， 可通过建立好的 ST表与线段树维护。
3. 类似于二分搜索， 分治。
此代码用的ST表， 线段树仿写即可。
#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;struct ST{vector<vector<int>> data;vector<int> lg2;int n;ST(){}ST(int n){innt(n);}void innt(int n){this->n = n;data.resize(n+1, vector<int>(32));lg2.resize(n+1);lg2[0] = -1;for(int i=1; i<=n; i++) {lg2[i] = lg2[i>>1] + 1;}}int gcd(int a, int b){return b==0? a : gcd(b, a%b);}void buildGcd(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1 <= n; i++) {data[i][p] = gcd(data[i][p - 1], data[i + (1 << (p-1))][p-1]);}}}int queryGcd(int l, int r){int p = lg2[r-l+1];return gcd(data[l][p], data[r-(1<<p)+1][p]);}void buildMax(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = max(data[i][p-1], data[i + (1<<(p-1))][p-1]);}}}int queryMax(int l, int r){int p = lg2[r-l+1];return max(data[l][p], data[r-(1<<p)+1][p]);}void buildMin(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = min(data[i][p-1], data[i + (1<<(p-1))][p-1]);}}}int queryMin(int l, int r){int p = lg2[r-l+1];return min(data[l][p], data[r-(1<<p)+1][p]);}void buildAnd(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = data[i][p-1] & data[i + (1<<(p-1))][p-1];}}}int queryAnd(int l, int r){int p = lg2[r-l+1];return data[l][p] & data[r-(1<<p)+1][p];}void buildOr(){for(int p=1; p<=lg2[n]; p++) {for(int i=1; i + (1<<p) - 1<=n; i++) {data[i][p] = data[i][p-1] | data[i + (1<<(p-1))][p-1];}}}int queryOr(int l, int r){int p = lg2[r-l+1];return data[l][p] | data[r-(1<<p)+1][p];}
}; // 提前封装的ST表int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;ST st = ST(n); vector<int> a(n+1);for(int i=1; i<=n; i++) {cin >> a[i];st.data[i][0] = a[i];}st.buildMin(); // 建表// 分治搜索最值， 注意当在右边的值一定比左边的大， 就可以 log 级 类似于二分auto dfs = [&](int l, int r,int v, auto&&dfs)->int{if(l==r) {return l; // 到只有一个满足的数了，返回下标}int mid = (l+r)>>1;int res = -1;if(st.queryMin(mid+1, r) >= v) {// 不做}else{return max(dfs(mid+1, r, v, dfs), res);//右边一定比左边大}if(st.queryMin(l, mid) >= v) {}else{res = max(dfs(l,mid,v,dfs), res);}return res;};for(int i=1; i<n; i++) {int mi = st.queryMin(i+1, n);if(mi >= a[i]) {cout << -1 << " ";continue;}int dl = dfs(i+1, n, a[i], dfs);cout << dl - i - 1 << " ";}// 最后一个数一定是-1cout << "-1\n";return 0;
}
欢迎大佬指正， 感谢你的收看与点赞。
)
