题意：

给你 $n$ 个数，请求出这 $n$ 个数有多少个连续的区间，使得每个区间都满足：

区间内数字的最大值大于等于区间内数字的最小值的两倍

解法一（暴力求解，不可AC）

直接枚举所有区间，并判断是否满足条件

具体的：

第一层循环枚举左端点 $l$ ，并且在第一层循环内维护最大值 $mx$ 和最小值 $mi$

第二层循环枚举右端点 $r$ ， $r$ 从左到右枚举的过程中顺便维护 $mx$ 和 $mi$

代码：

class Solution {
public:
    long long MaxMin(vector<int>& array) {
        int n=array.size();//数组长度
        long long ans=0;
        for(int l=0;l<n;l++){
            //最大值和最小值
            int mx=array[l],mi=array[l];
            for(int r=l+1;r<n;r++){
                //维护最大/最小值
                mx=max(mx,array[r]);
                mi=min(mi,array[r]);
                if(mx>=mi*2)ans++;
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^2)$ ，枚举所有区间的代价是 $O(n^2)$ 的，维护最大/最小值，更新答案都是 $O(1)$ 的，故总的时间复杂度为 $O(n^2)$

空间复杂度： $O(1)$ ，程序中并没有而外开辟新的内存，故空间复杂度为 $O(1)$

解法二（线段树+二分答案）

我们考虑枚举区间右端点 $r$ ，想办法用较为快速的方法获得对应区间左端点的合法值

分析：

若区间 $[l,r]$ 是合法的，那么区间 $[l-1,r]$ 一定是合法的

证明： $\left\{ \begin{aligned} max([l-1,r])>=max([l,r])\\ min([l-1,r])<=min([l,r])\\ max([l,r])>=2*min([l,r]) \end{aligned} \right. \Rightarrow max([l-1,r])>=min([l-1,r])*2$

则对于每一个右端点 $r$ ，我们可以二分找到满足条件的最大的左端点 $l$ ，则对于当前右端点 $r$ 来说，对答案的贡献是 $l-0+1=l+1$ （数组下标从0开始）

对于区间查询最大值/最小值，我们可以用线段树来实现

于是我们就做完了

代码：

class Solution {
public:
    struct segtree{
        int mxval[100001<<2],mival[100001<<2];
        inline int lson(int x){//左儿子
            return x<<1;
        }
        inline int rson(int x){//右儿子
            return x<<1|1;
        }
        inline void pushup(int x){//维护最大/最小值
            mxval[x]=max(mxval[lson(x)],mxval[rson(x)]);
            mival[x]=min(mival[lson(x)],mival[rson(x)]);
        }
        void update(int x,int l,int r,int p,int v){//单点修改
            if(l==r){
                mxval[x]=v;
                mival[x]=v;
                return;
            }
            int mid=(l+r)>>1;
            if(p<=mid)update(lson(x),l,mid,p,v);
            else update(rson(x),mid+1,r,p,v);
            pushup(x);
        }
        int querymax(int x,int l,int r,int sl,int sr){
            //查询区间最大值
            if(sl<=l&&sr>=r)return mxval[x];
            int mid=(l+r)>>1;
            if(sl<=mid&&mid+1<=sr)return max(querymax(lson(x),l,mid,sl,sr),querymax(rson(x),mid+1,r,sl,sr));
            if(sl<=mid)return querymax(lson(x),l,mid,sl,sr);
            return querymax(rson(x),mid+1,r,sl,sr);
        }
        int querymin(int x,int l,int r,int sl,int sr){
            //查询区间最小值
            if(sl<=l&&sr>=r)return mival[x];
            int mid=(l+r)>>1;
            if(sl<=mid&&mid+1<=sr)return min(querymin(lson(x),l,mid,sl,sr),querymin(rson(x),mid+1,r,sl,sr));
            if(sl<=mid)return querymin(lson(x),l,mid,sl,sr);
            return querymin(rson(x),mid+1,r,sl,sr);
        }
    }seg;
    long long MaxMin(vector<int>& array) {
        int n=array.size();
        for(int i=0;i<n;i++){
            //单点修改
            seg.update(1,0,n-1,i,array[i]);
        }
        long long ans=0;//ans表示答案
        for(int i=0;i<n;i++){//i为枚举的右端点
            int l=0,r=i-1;//l为二分下界，r为二分上界
            int p=-1;//满足条件的最大的左端点
            while(l<=r){
                int mid=(l+r)>>1;
                if(seg.querymax(1,0,n-1,mid,i)>=seg.querymin(1,0,n-1,mid,i)*2){
                    //如果满足条件，则记录，并且贪心地往右边找更优的左端点
                    p=mid;
                    l=mid+1;
                }else{
                    //不满足条件，只能往左边找
                    r=mid-1;
                }
            }
            //计算答案的贡献（p-0+1）
            ans+=p+1;
        }
        return ans;
    }
};

时间复杂度： $O(nlog^2n)$ ，枚举区间右端点的代价是 $O(n)$ 的，二分是 $O(logn)$ 的，二分内部查询最大/最小值是 $O(logn)$ 的，故总的时间复杂度为 $O(nlog^2n)$

空间复杂度： $O(n)$ ，线段树四倍内存消耗 $O(n)$ 的空间，加上本身数组 $O(n)$ 的空间，总的空间复杂度为 $O(n)$

题解 | #最大最小#

题意：

解法一（暴力求解，不可AC）

解法二（线段树+二分答案）