洛谷 4755 Beautiful Pair

这题的分治特征比较明显，但是按照传统的二分实现分治大概不可做。
更可做的是对于每个区间的最大值 O(n) 统计答案。
但是这样子复杂度无法保证是 O(nlogn) 的。

可以考虑把单层的复杂度优化到可以接受的范围内，这样即便分治的过程是一条链也只是多了一个 O(n) 而已。

首先，我们把取最大值的过程，用 ST 表优化为 O(1)。
然后，设当前区间 [l,r] 最大值的位置为 mx，那么以 amx 为最大值的数对的答案相当于 mx∑i=lr∑j=mx+1[aj≤amxai]，两个 ∑ 的范围交换也一样。
其中 [X] 表示如果 X 成立即为 1 否则为 0。
发现后面这个 ∑ 可以用主席树来做，单次 O(logn)。
现在最大的问题是确定前面这个 ∑ 的取值范围。

非常显然地，我们可以启发式地取两边长度较小的一边来枚举。
这样的话，对于 a 单调的数据，开始提到的那种分治是 O(n2) 的，这个算法反而可以做到 O(nlogn)。
而能够使那种分治的复杂度为 O(nlogn) 的数据反而是这个算法的上界，即 O(nlog2n)。

壮哉我大主席树！

代码：

#include <cstdio>
const int N = 1e5;
const int A = 1e9;
const int LG = 20;
using namespace std;
int n,a[N + 5];
int st[N + 5][LG + 5],lg2[N + 5];
struct node
{
    int cnt;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot,++seg[p].cnt;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,seg[p].ls,tl,mid);
    else
        insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].cnt;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret += query(l,r,seg[p].rs,mid + 1,tr);
    return ret;
}
long long solve(int l,int r)
{
    if(l > r)
        return 0;
    if(l == r)
        return a[l] <= 1;
    int mx,lg = lg2[r - l + 1];
    if(a[st[l][lg]] >= a[st[r - (1 << lg) + 1][lg]])
        mx = st[l][lg];
    else
        mx = st[r - (1 << lg) + 1][lg];
    long long ret = solve(l,mx - 1) + solve(mx + 1,r);
    if(mx - l < r - mx)
        for(register int i = l;i <= mx;++i)
            ret += query(1,a[mx] / a[i],rt[r],1,A) - query(1,a[mx] / a[i],rt[mx - 1],1,A);
    else
        for(register int i = r;i >= mx;--i)
            ret += query(1,a[mx] / a[i],rt[mx],1,A) - query(1,a[mx] / a[i],rt[l - 1],1,A);
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),st[i][0] = i;
    for(register int i = 2;i <= n;++i)
        lg2[i] = lg2[i / 2] + 1;
    for(register int i = 1;i <= LG;++i)
        for(register int j = 1;j + (1 << i) - 1 <= n;++j)
            if(a[st[j][i - 1]] >= a[st[j + (1 << i - 1)][i - 1]])
                st[j][i] = st[j][i - 1];
            else
                st[j][i] = st[j + (1 << i - 1)][i - 1];
    for(register int i = 1;i <= n;++i)
        insert(a[i],1,rt[i] = rt[i - 1],1,A);
    printf("%lld\n",solve(1,n));
}