https://www.luogu.org/problemnew/show/P4755

考虑分治，在 [l, r] 区间中用线段树找到最大的一个点，处理经过它的可行数对的个数，统计个数可以离线树状数组处理

因为最多被分成 2n 个区间（像线段树一样），对于每个区间使用类似于启发式合并的思想将要处理的区间放到 vector 里面，最多有 n log n 个查询，复杂度 n log^2 n

#include <bits/stdc++.h>

#define For(i, a, b) for(int i = a; i <= b; i++)

using namespace std;

typedef unsigned long long ull;

typedef long long ll;

template <typename _T>

inline void read(_T &f) {

    f = 0; _T fu = 1; char c = getchar();

    while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}

    while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

    f *= fu;

}

const int N = 1e5 + 5;

int Max[N << 2], wz[N << 2], a[N], pre[N], f[N];

long long ans;

int n, len;

void build(int u, int l, int r) {

    if(l == r) {

        Max[u] = a[l];

        wz[u] = l;

        return;

    }

    int mid = (l + r) >> 1;

    build(u << 1, l, mid);

    build(u << 1 | 1, mid + 1, r);

    if(Max[u << 1] > Max[u << 1 | 1]) Max[u] = Max[u << 1], wz[u] = wz[u << 1];

    else Max[u] = Max[u << 1 | 1], wz[u] = wz[u << 1 | 1];

}

int Q1, Q2;

void query(int u, int l, int r, int L, int R) {

    if(l <= L && R <= r) {

        if(Max[u] > Q1) {

            Q1 = Max[u];

            Q2 = wz[u];

        }

        return;

    }

    int mid = (L + R) >> 1;

    if(mid >= l) query(u << 1, l, r, L, mid);

    if(mid + 1 <= r) query(u << 1 | 1, l, r, mid + 1, R);

}

int lowbit(int x) {return x & -x;}

void add(int x) {for(int i = x; i <= n; i += lowbit(i)) f[i]++;}

int query(int x) {int ans = 0; for(int i = x; i; i -= lowbit(i)) ans += f[i]; return ans;}

struct ele {

    int l, r, v;

    bool operator < (const ele A) const {return v < A.v;}

    ele (int a, int b, int c) : l(a), r(b), v(c) {}

    ele () {}

};

vector <ele> Q;

vector <int> t[N];

void solve(int l, int r) {

    if(l > r) return;

    Q1 = 0; query(1, l, r, 1, n);

    int L = Q2 - l, R = r - Q2; int tmp = Q2;

    if(L < R) for(int i = l; i <= Q2; i++) { Q.push_back(ele(Q2, r, pre[Q1] / pre[a[i]])); }

    else for(int i = Q2; i <= r; i++) Q.push_back(ele(l, Q2, pre[Q1] / pre[a[i]]));

    solve(l, tmp - 1); solve(tmp + 1, r);

}

int main() {

    cin >> n;

    for(int i = 1; i <= n; i++) { read(a[i]), pre[i] = a[i]; };

    sort(pre + 1, pre + n + 1); len = unique(pre + 1, pre + n + 1) - pre - 1;

    for(int i = 1; i <= n; i++) a[i] = lower_bound(pre + 1, pre + len + 1, a[i]) - pre;

    build(1, 1, n); solve(1, n);

    for(vector <ele> :: iterator it = Q.begin(); it != Q.end(); it++) it -> v = upper_bound(pre + 1, pre + len + 1, it -> v) - pre - 1;

    for(int i = 1; i <= n; i++) t[a[i]].push_back(i);

    sort(Q.begin(), Q.end()); int LEN = Q.size(), now = 0;

    for(int i = 0; i <= len; i++) {

        for(vector <int> :: iterator it = t[i].begin(); it != t[i].end(); it++) add(*it);

        while(Q[now].v == i && now < LEN) {

            ans += (long long)(query(Q[now].r) - query(Q[now].l - 1));

            now++;

        }

    }

    cout << ans << endl;

    return 0;

}