給定個整數和個詢問,對于每個詢問給定一個常數k,你需要找到有多少個區間滿足序列的内所有元素。注意序列無序。
,顯然需要一個高效的算法,首先考慮雙指針求解。
首先對于一段區間,如果其區間最大值和區間最小值之差大于,那麼目前區間可以産生個符合條件的區間:設分别表示目前區間的最大值、最小值,如果,那麼說明該區間一定符合要求,那麼包含該區間的區間也一定符合要求(值隻會越來越小,值指揮越來越大),是以符合要求的區間數
那麼我們可以每次固定區間左端點,右端點向後找到第一個滿足區間最大值和區間最小值之差大于的點,然後将符合要求的區間數累加到答案中即可。
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
int stmax[N][22], stmin[N][22], mn[N];
int a[N];
int t, q, n, x, y;
void init(){
mn[0]=-1;
for (int i=1;i<=n;i++){
mn[i]=((i & (i-1))==0) ? mn[i-1]+1 : mn[i-1];
stmax[i][0]=stmin[i][0]=a[i];
}
for (int j=1;j<=mn[n];j++)
for (int i=1;i+(1<<j)-1<=n;i++){
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}
}
int rmq_max(int L,int R){
int k=mn[R-L+1];
return max(stmax[L][k],stmax[R-(1<<k)+1][k]);
}
int rmq_min(int L,int R){
int k=mn[R-L+1];
return min(stmin[L][k],stmin[R-(1<<k)+1][k]);
}
signed main(){
cin >> n >> q;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
init();
while (q--){
int k = 0; cin >> k;
long long ans = 0;
int l = 1, r = 0, maxn, minn;
while(l <= n){
r = max(r, l);
maxn = rmq_max(l, r), minn = rmq_min(l, r);
while (maxn - minn <= k && r < n) {
r++;
maxn = max(maxn, a[r]), minn = min(minn, a[r]);
}
if (maxn - minn > k) ans += n - r + 1;
l++;
}
cout << ans << endl;
}
return 0;
}