最大最小题解

方法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;
    }
};