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

P4755 Beautiful Pair

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

题目

洛谷

做法

\(i≤x≤j,a[i]<\frac{a[x]}{a[j]}\)

考虑\(a[x]\)的贡献,单调栈预处理\(L,R\)能作为最大值的区间

枚举一端点,仅需另一端点满足条件即可,启发式枚举端点

另一端点丢到树状数组里随便乱搞,由于是一个区间的要差分一下

My complete code

#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long LL;
const LL maxn=1e5+9;
struct node{
    LL val,x;
}que[maxn]; vector<LL> Q[maxn];
LL n,cnt;
LL L[maxn],R[maxn],a[maxn],b[maxn];
inline void Fir_LR(){
    LL tail(0);
    for(LL i=1;i<=n;++i){
        while(tail && que[tail].val<a[i]) --tail;
        L[i]=(tail?que[tail].x+1:1);
        que[++tail]=(node){a[i],i};
    }
    tail=0;
    for(LL i=n;i>=1;--i){
        while(tail && que[tail].val<=a[i]) --tail;
        R[i]=(tail?que[tail].x-1:n);
        que[++tail]=(node){a[i],i};
    }
}
inline void Fir_Q(){
    for(LL i=1;i<=n;++i)
        if(i-L[i]<=R[i]-i){
            for(LL j=L[i];j<=i;++j)
                Q[R[i]].push_back(a[i]/a[j]),
                Q[i-1].push_back(-a[i]/a[j]);
        }else{
            for(LL j=i;j<=R[i];++j)
                Q[i].push_back(a[i]/a[j]),
                Q[L[i]-1].push_back(-a[i]/a[j]);
        }
}
struct Tree_k{
    LL tree[maxn];
    inline LL Lowbit(LL x){ return x&-x; }
    inline void Add(LL x,LL val){
        for(;x<=cnt;x+=Lowbit(x)) tree[x]+=val;
    }
    inline LL Query(LL x){
        LL ret(0);
        for(;x;x-=Lowbit(x)) ret+=tree[x]; return ret;
    }
}Tk;
inline void Fir_S(){
    LL ret(0);
    for(LL i=1;i<=n;++i){
        Tk.Add(a[i],1);
        for(LL j=0;j<Q[i].size();++j){
            LL val(Q[i][j]);
            LL x(abs(val)>=b[cnt]?cnt:upper_bound(b+1,b+1+cnt,abs(val))-b-1);
            ret+=(val>0?1:-1)*Tk.Query(x);
        }
    }
    cout<<ret;
}
int main(){
    cin>>n;
    for(LL i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
    Fir_LR();
    Fir_Q();
    sort(b+1,b+1+n), cnt=unique(b+1,b+1+n)-b-1;
    for(LL i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;//,cout<<a[i]<<' ';cout<<endl;
    Fir_S();
}