hdu 5289 Assignment（给一个数组，求有多少个区间，满足区间内的最大值和最小值之差小于k）

**1.区间是一段的，不是断开的哟** **2.代码是看着标程写的** **3.枚举左端点，二分右端点流程：**  ~~~ #include<cstdio> #include<cstring> #include<cmath> #define LL long long #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N=200007; int minn[N][20];//2^18=262144 2^20=1048576 int maxx[N][20]; //----------------------查询O(1)------------- int queryMin(int l,int r) { int k=floor(log2((double)(r-l+1)));//2^k <= (r - l + 1),floor()向下取整函数 return Min(minn[l][k],minn[r-(1<<k)+1][k]); } int queryMax(int l,int r) { int k=floor(log2((double)(r-l+1))); return Max(maxx[l][k],maxx[r-(1<<k)+1][k]); } //------------------------------------------------- int calc(int l,int r) { int k=log2((double)(r-l+1)); int MAX=Max(maxx[l][k],maxx[r-(1<<k)+1][k]); int MIN=Min(minn[l][k],minn[r-(1<<k)+1][k]); return MAX-MIN; } int main() { int T; int n,k,i,j,p; LL ans; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(i=1; i<=n; ++i) { scanf("%d",&j); minn[i][0]=maxx[i][0]=j; } //------------------------------------------预处理O(nlogn)--------------- for(j=1; (1<<j)<=n; ++j)//1<<j==2^j,枚举区间长度1，2，4，8，16，，，，， for(i=1; i+(1<<j)-1<=n; ++i)//i+(1<<j)-1表示区间右边界，枚举区间左边界 { p=(1<<(j-1)); minn[i][j]=Min(minn[i][j-1],minn[i+p][j-1]); maxx[i][j]=Max(maxx[i][j-1],maxx[i+p][j-1]); } //----------------------------------------------------------------------- //---------------------------枚举左端点，二分右端点--------------------------- int l,r,mid; ans=0; //左端点固定为i，右端点用l,r,mid去确定，最后用l和r中的其中一个，此时l+1==r for(i=1; i<=n; ++i) { l=i,r=n; while(l+1<r) { mid=(l+r)>>1;//(l+r)/2==(l+r)>>1 if(calc(i,mid)<k) { l=mid; } else { r=mid-1;//自己去演示算法流程就知道r可以赋值mid-1 } } if(calc(i,r)<k) { ans=ans+(LL)(r-i+1); } else { ans=ans+(LL)(l-i+1); } } //--------------------------------------------------------------------------- printf("%lld\n",ans); } return 0; } ~~~