【题解】Beautiful Pair 毒瘤变 log 思想+BIT+单调栈 luogu4755 ——quhengyi11

不用说你也知道我是什么了吧 啊呜

题解

首先考虑暴力搞，分治，每次把当前区间最大的数拎出来，然后统计左右两边的贡献

这种方法显然会被一个严格升序列给卡成 $n^2$

考虑优化上面的暴力，我们发现我们统计的实际上是分别以这 $n$个数为中心 (也就是最大的那个数 $max$) 并且求两边数对它的贡献的，分治只是确定了它们各自可以被贡献到的区间，但这样的代价是让贡献的顺序固定了，我们考虑记录一下每个数如果作为 $max$可以延伸到的最左边和最右边的数，分别记为 $L[i],R[i]$，这里用单调栈可以搞定。

整理一下思路，现在你相当于有一个长度为 $n$的序列 $a[i]$，有 $n$个询问，每个询问有三个数 $L[i],i,R[i]$，要让你求出有多少个数对满足
$$x\in [L[i],i), y\in (i,R[i]],a[x]\times a[y] \leq a[i]$$

并把这些结果加起来。

我们可以考虑乱统计一波，你可以先枚举 $y$，然后再用树状数组搞 $x$对 $y$的贡献，我们可以离线处理就可以按顺序一次树状数组扫完贡献。

然而这个复杂度完全取决于你枚举 $y$的复杂度。

很容易想到我们可以枚举更小的那个区间而去用树状数组统计更大的那个区间？

可是这又有什么用呢？

你会惊奇地发现你的枚举复杂度降到了 $nlogn$

因为你一个数被枚举到的时候，设当前枚举区间 $(i, R[i]]$的大小为 $len$，你会发现当前的 $[L[i],R[i]]$的大小是一定大于等于 $2\times len$的，那么 $[L[i],i]$这一段区间显然不会对当前这个数有贡献，也就是说对当前这个数被枚举的次数是 $logn$级别的（这里得意会一下我讲不清了 QAQ）。

这个证明太妙了 QvQ 我感觉我似乎还是不能触类旁通（

顺便提一下细节，当同样的数出现了两次的时候，显然会有一部分 $x,y$会被重复统计，因此对于重复的数我们可以控制 $L[i]$的延伸来避免容斥。

总复杂度加上树状数组是 $O(nlog^2n)$

代码

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 100005
#define M 4000005
int n, a[N], b[N], L[N], R[N], sta[N], top, tot;
ll ans;
std::vector<int> q[N];
inline int id (int x) {return x < b[1] ? 0 : std::lower_bound(b + 1, b + tot + 1, x) - b;}
int c[N];
inline int query (int x) {int ret = 0; for (; x; x -= lowbit(x)) ret += c[x]; return ret;}
inline void add (int x) {for (; x <= tot; x += lowbit(x)) c[x] += 1;}
int main ()
{
    scanf("%d", &n);
    fo (i, 1, n)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sta[top = 0] = 0;
    fo (i, 1, n)
    {
        while (top && a[sta[top]] < a[i]) --top;
        L[i] = sta[top] + 1;
        sta[++top] = i;
    }
    sta[top = 0] = n + 1;
    fd (i, n, 1)
    {
        while (top && a[sta[top]] <= a[i]) --top;
        R[i] = sta[top] - 1;
        sta[++top] = i;
    }
    fo (i, 1, n)
        if (i - L[i] <= R[i] - i)
        {
            fo (j, L[i], i)
            {
                q[R[i]].pb(a[i] / a[j]);
                q[i - 1].pb(-a[i] / a[j]);
            }
        }
        else
        {
            fo (j, i, R[i])
            {
                q[i].pb(a[i] / a[j]);
                q[L[i] - 1].pb(-a[i] / a[j]);
            }
        }
    std::sort(b + 1, b + n + 1);
    fo (i, 1, n) if (b[i] != b[tot]) b[++tot] = b[i];
    fo (i, 1, n)
    {
        add(id(a[i]));
        int sz = q[i].size() - 1;
        fo (j, 0, sz)
        {
            int pos = std::upper_bound(b + 1, b + tot + 1, q[i][j] < 0 ? -q[i][j] : q[i][j]) - b - 1;
            ans += q[i][j] < 0 ? -query(pos) : query(pos);
        }
    }
    printf("%lld\n", ans);
    return 0;
}