題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5289

題意：求滿足區間內最大值和最小值差為k的區間個數。

預處理出區間的最值，枚舉左端點，根據最值的單調性二分枚舉右端點，使得找到最右側max-min<k，區間數為[i,...hi]的個數，即hi-i+1個。

1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 typedef pair<int, int> pii; 6 const int maxn = 200200; 7 int dp[maxn][20][2]; 8 int a[maxn]; 9 int n, k; 10 11 void st(int* a, int* b, int n) { 12 for(int i = 1; i <= n; i++) dp[i][0][0] = b[i], dp[i][0][1] = a[i]; 13 for(int j = 1; (1 << j) - 1 <= n; j++) { 14 for(int i = 1; i + (1 << j) - 1 <= n; i++) { 15 dp[i][j][0] = min(dp[i][j-1][0], dp[i+(1<<(j-1))][j-1][0]); 16 dp[i][j][1] = max(dp[i][j-1][1], dp[i+(1<<(j-1))][j-1][1]); 17 } 18 } 19 } 20 21 pii query(int l, int r) { 22 int k = int(log(r-l+1) / log(2.0)); 23 return pii(min(dp[l][k][0], dp[r-(1<<k)+1][k][0]), max(dp[l][k][1], dp[r-(1<<k)+1][k][1])); 24 } 25 26 int main() { 27 // freopen("in", "r", stdin); 28 int T; 29 scanf("%d", &T); 30 while(T--) { 31 scanf("%d%d",&n,&k); 32 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 33 st(a, a, n); 34 LL ret = 0; 35 for(int i = 1; i <= n; i++) { 36 int lo = i, hi = n; 37 while(lo <= hi) { 38 int mid = (lo + hi) >> 1; 39 pii q = query(i, mid); 40 int minn = q.first, maxx = q.second; 41 if(maxx - minn < k) lo = mid + 1; 42 else hi = mid - 1; 43 } 44 ret += (hi - i + 1); 45 } 46 printf("%I64d\n", ret); 47 } 48 return 0; 49 }

?

轉載于:https://www.cnblogs.com/kirai/p/6095536.html

總結

以上是生活随笔為你收集整理的[HDOJ5289]Assignment（RMQ，二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。