分治&线段树练习——洛谷P4755 Beautiful Pair

蒟蒻的垂死挣扎

给定一个数列，求区间左端点乘右端点小于区间最大值的区间个数。

这一题很妙啊。先膜一波zsy。

看到这个题目，顺序做总觉得有问题，那么我们考虑分治做。既然是要求找到如上所说的区间个数，那么我们发现每次将最大值作为分治中心是比较优秀的，每次计算跨越这个点的区间个数，这样我们就能很方便的计算出方案数，现在的问题是怎么保证复杂度。

保证复杂度之前我们先看看我们如何统计这个方案，一个显而易见的做法是，既然已经确定了最大值，那么我们枚举跨越所有这个最大值的区间，依次检查是否合法就行了。这样无疑是非常暴力的，既然是考虑计数，我们肯定要对这个策略进行优化，我们发现如果已经得到最大值与一个端点，那么我们可以确定另一个端点的取值范围，如此就可以得到一个用线段树维护的优化方法，即只枚举一个端点，计算另一个端点的取值范围，在线段树上查询即可。最后考虑枚举哪边，查询哪边，我们发现，如果每一次都枚举比较小的区间的话，那么每次枚举的区间都会至少减小一半，那么说明每个数被枚举的次数最多为log次，再乘上每次查询线段树的log，这样我们就得到了一个时间复杂度两只log的算法。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#define ll long long
#define MOD 1000000007
#define MAXN 1000000000
#define N 110000 
#define RG register

using namespace std;

inline int read(){
    RG int x=0,o=1; RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=((x<<3)+(x<<1))+ch-'0',ch=getchar();
    return x*o;
}

int n,a[N],root[N],Log[N]; ll ans;
struct HJTree{
    int ls[N*80],rs[N*80],num[N*80],tot;
    inline void Modify(int l,int r,int &x,int y,int pos,int val){
        x=++tot; ls[x]=ls[y],rs[x]=rs[y],num[x]=num[y]+val;
        if(l==r) return ; int mid=(l+r)>>1;
        if(pos<=mid) Modify(l,mid,ls[x],ls[y],pos,val);
        else Modify(mid+1,r,rs[x],rs[y],pos,val);
    }
    inline ll Query(int l,int r,int now,int L,int R){
        if(!now) return 0; if(l>=L&&r<=R) return num[now];
        int mid=(l+r)>>1,ans=0;
        if(L<=mid) ans+=Query(l,mid,ls[now],L,R);
        if(R>mid) ans+=Query(mid+1,r,rs[now],L,R);
        return ans;
    }
} T;
struct ST{
    int Max[21][N];
    inline void Modify(int i,int j){
        int nxt=j+(1<<i-1); if(nxt>n) return ;
        Max[i][j]=a[Max[i-1][j]]>a[Max[i-1][nxt]]?Max[i-1][j]:Max[i-1][nxt];
    }
    inline int Query(int i,int j){
        int len=j-i+1,x=Log[len],y=(1<<x);
        return a[Max[x][i]]>a[Max[x][j-y+1]]?Max[x][i]:Max[x][j-y+1];
    }
} S;

inline void Divide(int l,int r){
    if(l>r) return ;
    int mid=S.Query(l,r),SL,SR,TL,TR;
    if(mid-l>r-mid) SL=l,SR=mid,TL=mid,TR=r;
    else SL=mid,SR=r,TL=l,TR=mid;
    for(RG int i=TL;i<=TR;++i){
        int Max=a[mid]/a[i]; ll sum=T.Query(1,MAXN,root[SL-1],1,Max);
        ans+=T.Query(1,MAXN,root[SR],1,Max)-sum;
    }
    Divide(l,mid-1),Divide(mid+1,r);
}

int main(){
    n=read(); for(RG int i=1;i<=n;++i) a[i]=read(),Log[i]=log2(i);
    for(RG int i=1;i<=n;++i){
        T.Modify(1,MAXN,root[i],root[i-1],a[i],1);
        S.Max[0][i]=i;
    }
    for(RG int i=1;i<=20;++i)
        for(RG int j=1;j<=n;++j)
            S.Modify(i,j);
    Divide(1,n); cout<<ans<<endl;
    
}