最大最小题解
方法1：AC
启发式分治。对于区间，找到最大值所在位置，然后处理横跨最大值所在位置的点对，然后递归处理子区间。启发式分治的时间复杂度可证明为
。首先是如何找到一个区间的最大值及其位置，这个可以用
表来处理，当然线段树也是可以的。那么我们知道一个区间，知道这个区间的最大值及最大值的位置，假设现在是区间
,最大值位置是
,那么我们应该去看
与
谁小然后去枚举那一个子区间。假设我们枚举的是左边半个区间，也就是从
到
。假设我们现在枚举到了
处，我们需要知道
的最小值
是不是小于等于
处的值。如果是我们就可以算贡献
假设不是我们还需要去
找到一个最左边的位置
满足
处的值
小于等于
,贡献为
找
的位置可以用线段树来找。总的时间复杂度为
,空间复杂度为
。
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
typedef long long ll;
const int N=100010;
char s[N];
int a[N],n;
int mn[N<<2];//线段树维护区间最小值
int st[20][N];//st表维护区间最大值下标
int que(int l,int r){//返回区间最大值下标
int f=r-l+1;
f=log2(f);
if(a[st[f][l]]>a[st[f][r-(1<<f)+1]]) return st[f][l];
return st[f][r-(1<<f)+1];
}
inline void up(int rt) {mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);}
void build(int l,int r,int rt) {
if (l==r) {mn[rt]=a[l];return ;}
int m=(l+r)>>1;
build(lson),build(rson);
up(rt);
}
int fg,v;
void qry(int L,int R,int l,int r,int rt) {//求区间[l,r]中≤v的最左边的位置
if(fg) return;
if (l==r) {
if(mn[rt]<=v) fg=l;
return ;
}
int m=(l+r)>>1;
if (L<=m&&mn[rt<<1]<=v) qry(L,R,lson);
if (m<R&&mn[rt<<1|1]<=v) qry(L,R,rson);
}
int get(int l,int r,int val) {//返回区间[l,r]中≤v的最左边的位置，没有则返回0
fg=0,v=val;
qry(l,r,1,n,1);
return fg;
}
void qry2(int L,int R,int l,int r,int rt) {//求区间[l,r]中≤v的最右边的位置
if(fg) return;
if (l==r) {
if(mn[rt]<=v) fg=l;
return ;
}
int m=(l+r)>>1;
if (m<R&&mn[rt<<1|1]<=v) qry2(L,R,rson);
if (L<=m&&mn[rt<<1]<=v) qry2(L,R,lson);
}
int get2(int l,int r,int val) {//返回区间[l,r]中≤v的最右边的位置，没有则返回0
fg=0,v=val;
qry2(l,r,1,n,1);
return fg;
}
ll ans=0;
void solve(int l,int r) {//启发式分治
if(r<l) return;
int p=que(l,r);
int mx=a[p],mn=a[p];
if(p-l<r-p) {//左边小，遍历左边
int pos=get(p,r,mx>>1);
for(int i=p;i>=l;i--) {
mn=min(mn,a[i]);
if(mn*2<=mx) ans+=r-p+1;//[i,p]中存在mn*2<=a[p]
else if(pos) ans+=r-pos+1;//[p,r]中存在a[pos]*2<=a[p]
}
}else {//右边小，遍历右边
int pos=get2(l,p,mx>>1);
for(int i=p;i<=r;i++) {
mn=min(mn,a[i]);
if(mn*2<=mx) ans+=p-l+1;//[p,i]中存在mn*2<=a[p]
else if(pos) ans+=pos-l+1;//[l,p]中存在a[pos]*2<=a[p]
}
}
solve(l,p-1);//递归左子区间
solve(p+1,r);//递归右子区间
}
class Solution {
public:
/**
*
* @param array int整型一维数组 array
* @param arrayLen int array数组长度
* @return long长整型
*/
long long MaxMin(int* array, int arrayLen) {
// write code here
n=arrayLen;
for(int i=1;i<=n;i++) a[i]=array[i-1],st[0][i]=i;//预处理
for(int j=1;(1<<j)<=n;j++)//预处理ST表
for(int i=1;i<=n;i++){
if((i+(1<<(j-1)))>n||a[st[j-1][i]]>a[st[j-1][i+(1<<(j-1))]]) st[j][i]=st[j-1][i];
else st[j][i]=st[j-1][i+(1<<(j-1))];
}
build(1,n,1);
solve(1,n);
return ans;
}
};解法2：TLE
ST表预处理最大最小值，然后枚举左右端点，判断是否可行。时间复杂度O(n^2),空间复杂度为O(nlogn)。
typedef long long ll;
const int N=100010;
int mn[22][N],mx[22][N],a[N],n;
int lg[N];
void init(int n){
for(int i=1;i<=n;i++) mn[0][i]=a[i];
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
mn[j][i]=min(mn[j-1][i],mn[j-1][i+(1<<(j-1))]);
for(int i=1;i<=n;i++) mx[0][i]=a[i];
for(int j=1;j<=21;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);
}
int querymn(int l,int r){
int k=lg[r-l+1];
return min(mn[k][l],mn[k][r-(1<<k)+1]);
}
int querymx(int l,int r){
int k=lg[r-l+1];
return max(mx[k][l],mx[k][r-(1<<k)+1]);
}
class Solution {
public:
/**
*
* @param array int整型一维数组 array
* @param arrayLen int array数组长度
* @return long长整型
*/
long long MaxMin(int* array, int arrayLen) {
// write code here
n=arrayLen;
lg[0]=-1;
for(int i=1;i<N;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) a[i]=array[i-1];
init(n);
ll ans=0;
for(int st=1;st<=n;st++) {
for(int ed=st;ed<=n;ed++) {
ll mx=querymx(st,ed),mn=querymn(st,ed);
if(mn*2<=mx) ans++;
}
}
return ans;
}
};