HDU - 5289：Assignment（单调队列||二分+RMQ||二分+线段树） - Java

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

InputIn the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means the maximum difference between abilities of staff in a group is less than k. The second line contains n integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate the i-th staff’s ability.OutputFor each test，output the number of groups.Sample Input

2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9

Sample Output

5
28

题意：求有多少个区间，其最大值和最小值的差小于K。

思路：从左到右，一次求以i为右边界的区间个数，这样的话，左边界一定是不移动，或者右移的。所以我们可以用单调队列，用两个队列表示单增和单减即可维护。或者用二分得到，每次RMQ验证区间差行否。

（虽然做过，但是我一眼还是想到的是分治，而不是简单方法。。。罪过。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],h1,t1,q1[maxn],h2,t2,q2[maxn],pos; long long ans;
int main()
{
int T,N,K;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&K);
rep(i,,N) scanf("%d",&a[i]);
h1=h2=; t1=t2=; ans=; pos=;
rep(i,,N){
while(h1>=t1&&a[q1[h1]]<a[i]) h1--;
while(h2>=t2&&a[q2[h2]]>a[i]) h2--;
q1[++h1]=i; q2[++h2]=i;
while(t1<=h1&&t2<=h2&&a[q1[t1]]-a[q2[t2]]>=K){
pos++;
while(q1[t1]<=pos) t1++;
while(q2[t2]<=pos) t2++;
}
ans+=i-pos;
}
printf("%lld\n",ans);
}
return ;
}