hdu5289 Assignment (区间查询最大值最小值，st算法...)

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

题意：给定长度为n的序列a和一个整数K,找出最大值和最小值的差值小于K的区间。输出满足条件的区间的个数。

分析：枚举a[i],以a[i]为起点,然后二分找终点(大区间满足条件的话小区间肯定也满足),依据起点和终点的位置能够算出以a[i]为起点可满足条件的区间的个数。怎么推断区间是否满足条件?能够用st算法用O（N*logN）方法进行预处理,然后O（1）查询区间最大值可最小值。先前用线段树查询超时了。。

。

后来还看到别人用树状数组+二分也过了。

。

还有的用队列写，或者直接线段树不二分。。。。

代码：

#include <iostream>
#include <cstdio>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 2e5;
int _max,_min,n,K;int MAX[100006][20],MIN[100006][20],a[100006];
void Init()
{
int i,j;
for(i=0;i<n;i++)
MAX[i][0]=MIN[i][0]=a[i];
for(j=1;(1<<j)<=n;j++)
{
for(i=0;i+(1<<j)-1<n;i++)
{
MAX[i][j]=MAX[i][j-1]>MAX[i+(1<<(j-1))][j-1]?MAX[i][j-1]:MAX[i+(1<<(j-1))][j-1];
MIN[i][j]=MIN[i][j-1]<MIN[i+(1<<(j-1))][j-1]?MIN[i][j-1]:MIN[i+(1<<(j-1))][j-1];
}
}
}
bool ok(int L,int R)
{
int k=0;
while((1<<(k+1))<=(R-L+1))
k++;
_min=MIN[L][k]<MIN[R-(1<<k)+1][k]?MIN[L][k]:MIN[R-(1<<k)+1][k];
_max=MAX[L][k]>MAX[R-(1<<k)+1][k]?MAX[L][k]:MAX[R-(1<<k)+1][k];
return _max-_min<K;
}
int Find(int s)
{
int down=s+1,up=n-1,mid,ret=s;
while(down<=up)
{
mid=(down+up)>>1;
if(!ok(s,mid))
up=mid-1;
else
{
down=mid+1;
if(ret<mid)
ret=mid;
}
}
return ret;
}
int main()
{
int ncase,i,j;
long long ans;
scanf("%d",&ncase);
while(ncase--)
{
scanf("%d%d",&n,&K);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
Init();
ans=n;
for(i=0;i<n;i++)
ans+=Find(i)-i;
printf("%I64d\n",ans);
}
return 0;
}