Assignment
题意
- 一段长度为n的区间，选取一段连续子区间满足要求子区间的max-min<=k,求这样的子区间数目
- n<=1e5
- 0<k<=1e9
题解
- 可以估计时间复杂度时o(nlogn)的算法
- ST表可以在O(1)时间内求得子区间的max-min,
- 而枚举子区间可以选定左端点，然后二分查找右端点(lower_bound(,,k)-1,lower_bound需自己实现)
- 最大的教训时自己原来并不是真的会二分查找和结果数目是超过了int,结果自己wa了
- 以后有关求问多少可能的一定要想想是否结果会溢出
代码
#include<bits/stdc++.h>
const int maxn=1e5+10;
int stmin[maxn][17];
int stmax[maxn][17];
int a[maxn];
int T,n,k;
void build(){
for(int i=1;i<=n;i++){
stmin[i][0]=a[i];
stmax[i][0]=a[i];
}
int maxl=floor(log2(n));
int mul=1;
for(int j=1;j<=maxl;j++){
for(int i=1;i<=n&&(i+mul)<=n;i++){
stmin[i][j]=std::min(stmin[i][j-1],stmin[i+mul][j-1]);
stmax[i][j]=std::max(stmax[i][j-1],stmax[i+mul][j-1]);
}
mul=mul*2;
}
}
int check(int x,int y){
int len=floor(log2(y-x+1));
int minv=std::min(stmin[x][len],stmin[y-(1<<len)+1][len]);
int maxv=std::max(stmax[x][len],stmax[y-(1<<len)+1][len]);
return maxv-minv;
}
int bsearch(int begin,int n){//ÕÒµ½
//lower_bound first >=k
if(check(begin,n)<k) return (n+1);
int m,l=begin,r=n;
while(l<r){
m=l+((r-l)>>1);
if(check(begin,m)<k) l=m+1;
else r=m;
}
return l;
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d %d",&n,&k);
for(int j=1;j<=n;j++){
scanf("%d",&a[j]);
}
build();
long long res=0;
for(int i=1;i<=n;i++){
//printf("debug %d
",bsearch(i,n)-i);
res=res+(bsearch(i,n)-i);
}
printf("%lld
",res);
}
fclose(stdin);
return 0;
}
关于二分的总结(完全摘自知乎）
- 注意观察b1()和lower_bound()关系
- 更有价值的内容可以看知乎
//10个二分9个错，自己还没有注意到二分里面的问题
//简单分类
/*
对于单调不降序列a[],关键字key
1. min(i) a[i]=key
2. max(i) a[i]=key
3. min(i) a[i]>key or >=key
4. max(i) a[i]<key or <=key
*/
//given a test case
//a[8]={1,2,2,4,4,5,5,5};key=4;
int b1(int a[],int n,int key){
int m,l=0,r=n-1;//闭区间[0,n-1]
while(l<r){
m=l+((r-l)>>1);
if(a[m]<key) l=m+1;
else r=m;//
// if a[m]>key r=m 没有问题
// if a[m]==key, 此时m可能在任意可能满足a[i]==key的位置
}
if(a[r]==key) return r;
return -1;
}
int b2(int a[],int n,int key){
int m,l=0,r=n-1;
while(l<r){
m=l+((r+1-l)>>1);//向上取整
if(a[m]<=key) l=m;
else r=m-1;
}
if(a[l]==key) return l;
return -1;
}
int b3(int a[],int n,int key){
int m,l=0,r=n-1;
while(l<r){
m=l=((r-l)>>1);
if(a[m]<=key) l=m+1;
else r=m;
}
if(a[r]>key) return r;
return -1;
}
int b4(int a[],int n,int key){
int m,l=0,r=n-1;
while(l<r){
m=l+((r-l+1)>>1);
if(a[m]<key) l=m;
else r=m-1;
}
if(a[l]<key) return l;
return -1;
}
int lower_bound(int A[], int n, int key) {
if (A[n - 1] < key) return n;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (A[mid] < key) lo = mid + 1; else hi = mid;
}
return lo;
}