Description
Input
Output
Sample Input
Sample Output
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]
题意：给出数列长度 n 以及数字 k 以及数列，求出数列中所以满足其中最大值和最小值之差小于 k 的小数列的个数。注：单个数也算一个小数列且必然符合条件。
思路：
首先是查询区间最大值与最小值的方式——可以用树状数组，也可以用线段树，sparse-table由于空间限制不会用。
关于三者的特性——
st算法的复杂度 O(nlog(n)) / O(1) ， 线段树为 O(nlog(n)) / (log(n))，树状数组 O(<nlog(n)) / O(log(n))
空间复杂度 st 为 O(nlog(n))， 线段树 O(n)，常数较大 ， 树状数组是 O(n)
编程上 st 和 树状数组 都比较容易实现，线段树代码较长
另外线段树灵活性较大
（引用自http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html）
而后是遍历方式——从数列第一个数开始，并设指针 p 为1。如满足max-min<k，则++p，直到条件不满足。则此时有ans+=p-1（包含第一个数的所有组合）。之后第二个数同理，沿用指针 p ，因若第一个数满足条件，则第二个数也必然满足条件，以此类推。
遍历有小小的优化是，在判断++p后满足条件与否时，没必要调用query函数，直接以a[p]更新tmax和tmin即可。
优化后快 600ms。
代码如下：
（注意ans要用long long不然会wa。。）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100005; int n,k,t,a[maxn],maxval[maxn],minval[maxn],tmax,tmin; int lowbit(int x){ return x&(-x); } void ini(){ for(int i=1;i<=n;i++){ maxval[i]=minval[i]=a[i]; for(int j=1;j<lowbit(i);j<<=1){ maxval[i]=max(maxval[i],maxval[i-j]); minval[i]=min(minval[i],minval[i-j]); } } } void query(int l,int r){ tmax=tmin=a[r]; while(true){ tmax=max(tmax,a[r]); tmin=min(tmin,a[r]); if(r==l) break; for(r-=1;r-l>=lowbit(r);r-=lowbit(r)){ tmax=max(tmax,maxval[r]); tmin=min(tmin,minval[r]); } } } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&t); while(t--){ memset(maxval,0,sizeof(maxval)); memset(minval,0x3f,sizeof(minval)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ini(); int p=1; long long ans=0; for(int i=1;i<=n;i++){ if(p>n) p=n; query(i,p); while(tmax-tmin<k&&p<=n){ p++; tmax=max(tmax,a[p]); tmin=min(tmin,a[p]); } ans+=p-i; } printf("%I64d\n",ans); } return 0; }
原文：http://www.cnblogs.com/names-yc/p/4665651.html
