[HackerRank] Array Pairs[101 Hack 42]

Problem

Consider an array of $$n$$ integers, $$A = [a1, a_2, \ldots, a{n}]$$. Find and print the total number of $$(i,j) $$ pairs such that $$ai \times a_j \le max(a_i, a{i+1}, \ldots, a_j) $$ where $$i \lt j$$.

Input Format

The first line contains an integer,$$ n $$, denoting the number of elements in the array.
The second line consists of $$ n $$space-separated integers describing the respective values of$$ a_1 , a_2,a_3, \cdots a_n$$.

Constraints

$$ 1 \leq n \leq 5 \times 10^5 $$

$$ 1 \leq a_i \leq 10^9 $$

Scoring

$$ 1 \leq n \leq 1000 $$ for 25% of the test cases.

$$ 1 \leq n \leq 10^5 $$ for 50% of the test cases.

$$ 1 \leq n \leq 5 \times 10^5 $$ for 100% of the test cases.

Output Format

Print a long integer denoting the total number $$(i,j)$$ pairs satisfying $$ ai \times a_j \leq max(a_i,a{i+1},a{i+2}, \cdots ,a_j )$$where $$(i<j)$$

Sample Input

5
1 1 2 4 2

Sample Output

Explanation

There are eight pairs satisfying the given criteria:(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5) and (3,5). Thus, we printas 8 our answer.

思路

笛卡尔树

方案1：参考： http://blog.csdn.net/samjia2000/article/details/52997874

假如我们已经知道了$$max(ai,a{i+1},...,aj)$$是$$v$$，那么对于一个i我们就可以知道$$a_j$$的取值范围应该为$$[1,\frac{a_i}{v}]$$于是我们可以建出笛卡尔树，对于笛卡尔树上的一个点，我们有两种方法来求出$$max(a_i,a{i+1},...,a_j)$$是$$v$$的合法的$$(i,j)$$的个数，一是枚举$$i$$，利用数据结构统计$$j$$的个数，二是枚举$$j$$，统计i的个数，显然如果我们非要从这两种里面选一种的话，我们会选择枚举次数少的。

那么这样做为什么不会使得询问的次数特别多呢？显然，一个最坏的情况下，我们建出的笛卡尔树应该是颗满二叉树，而当前情况下共有$$log_2n$$层，每层$$n$$个，由于要用到数据结构，所以这样做是$$O(nlog_2 ^2n)$$的。

这题的难点主要在于要想到用笛卡尔树，还要想到挑选个数小的那边进行枚举。

方案2：

为了方便求出区间最大值，我们先建出笛卡尔树。

考虑枚举笛卡尔树上每一个点，显然可以得到它作为最大值的区间。

如果我们枚举这个区间的左半部分的一个数，结合当前最大值，我们就知道右半区间的合法的数的取值范围。也就是我们只需要查询右半区间有多少个数小于等于某数即可。

但是这样显然是$$O(n^2)$$的，但是不虚，使用类似启发式合并的想法，如果右边比左边长度小，我们就枚举右边！这样每次枚举长度不会超过整个区间的一半！也就是说枚举的复杂度是$$O(nlog_2n)$$的！

至于查询，你可以选择打一个主席树在线查。当然也可以先把所有区间询问变为两个前缀询问相减，然后先存下来，遍历完笛卡尔树之后再统一使用树状数组计算。

时间复杂度$$O(nlog_2 ^2n)$$。

注意特判当前最大值和别的数组合造成的贡献。

代码

方案1：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

const int N = 5e5+10;

typedef long long LL;

int tree[N];
struct sj{
    int ty,l,r,x;
    friend bool operator <(sj a,sj b){
        if (a.x!=b.x)return a.x<b.x;
        return a.ty<b.ty;
    }
}q[N*20];
int sta[N],k,m;
int n;
LL ans;
int L[N],R[N],a[N],fa[N],rt,s[N],f[N];

void add(int ty,int l,int r,int x){
    q[++m].ty=ty;q[m].l=l;q[m].r=r;q[m].x=x;
}

void bfs(){
    int he=0,ta=1;
    f[1]=rt;
    while(he<ta){
        int x=f[++he];
        if (L[x])f[++ta]=L[x];
        if (R[x])f[++ta]=R[x];
    }
    fd(d,n,1){
        int x=f[d];
        s[x]=s[L[x]]+s[R[x]]+1;
        if(L[x]&&R[x]){
            if (s[L[x]]<s[R[x]]){
                fo(i,x-s[L[x]],x-1)
                add(1,x,x+s[R[x]],a[x]/a[i]);
                add(1,x+1,x+s[R[x]],1);
            }
            else{
                fo(i,x+1,x+s[R[x]])
                add(1,x-s[L[x]],x,a[x]/a[i]);
                add(1,x-s[L[x]],x-1,1);
            }
        }
        else
            if (L[x]+R[x]){
                if (L[x])add(1,x-s[L[x]],x-1,1);
                else add(1,x+1,x+s[R[x]],1);
            }
    }
}

int getans(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        x-=x&-x;
    }
    return ans;
}

void change(int x){
    while(x<=n){
        tree[x]++;
        x+=x&-x;
    }
}

int main(){
    scanf("%d",&n);
    fo(i,1,n)scanf("%d",&a[i]);
    sta[k=1]=1;
    fo(i,2,n){
        if (a[i]<=a[sta[k]]){
            fa[i]=sta[k];
            sta[++k]=i;
            continue;
        }
        while(k&&a[sta[k]]<a[i])k--;
        fa[sta[k+1]]=i;
        fa[i]=sta[k];
        sta[++k]=i;
    }
    fo(i,1,n)
    if (!fa[i])rt=i;
    else{
        if (i<fa[i])L[fa[i]]=i;
        else R[fa[i]]=i;
    }
    bfs();
    fo(i,1,n)add(0,i,0,a[i]);
    sort(q+1,q+1+m);
    fo(i,1,m)
    if (q[i].ty)ans=ans+getans(q[i].r)-getans(q[i].l-1);
    else change(q[i].l);
    printf("%lld\n",ans);
    return 0;
}