欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-08 17:42:41
...

蒟蒻的垂死挣扎

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

这一题很妙啊。先膜一波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;
    
}

 

相关标签: 线段树