本文共 1440 字，大约阅读时间需要 4 分钟。
RMQ + 二分
#include#include #include #include #include #include using namespace std;const int MAXN = 100000;const int MAXE = 25;//const int MAX = 30;int n;int m;int h[MAXN];//int bin[MAX];//int Log[MAXN]int mmax[MAXN][MAXE];int mmin[MAXN][MAXE];void RMQ_ST(){ for(int i = 1; i <= n; i++) { mmax[i][0] = h[i]; mmin[i][0] = h[i]; } int end_j = log(n + 0.0) / log(2.0); int end_i; for(int j = 1; j <= end_j; j++) { end_i = n + 1 - (1 << j); for(int i = 1; i <= end_i; i++) { mmax[i][j] = max(mmax[i][j - 1], mmax[i + (1 << (j - 1))][j - 1]); mmin[i][j] = min(mmin[i][j - 1], mmin[i + ( 1 << (j - 1))][j -1]); } }}int QueryMax(int l, int r){ int k = log(r - l + 1.0) / log(2.0); int x = max(mmax[l][k], mmax[r - (1 << k) + 1][k]); int y = min(mmin[l][k], mmin[r - (1 << k) + 1][k]); return x - y;}//int QueryMin(int l, int r)//{// int k = log(r - l + 1.0) / log(2.0);// return min(mmin[l][k], mmin[r - (1 << k) + 1][k]);//}int main(){ int T; cin >> T; while(T--) { int k; cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> h[i]; } RMQ_ST(); int l,r;// cin >> m;// for(int i = 1; i <= m; i++)// {// cin >> l >> r;// cout << QueryMax(l,r) << endl;// } long long int ans = 0; for(int i = 1; i <= n; i++) { l = i; r = n; while(l <= r) { int mid = (l + r) / 2; int cha = QueryMax(i,mid); if(cha < k) { l = mid + 1; } else r = mid - 1; } ans += l - i; } cout << ans << endl; } return 0;}
转载地址：http://vnwtb.baihongyu.com/