P4755 Beautiful Pair

Find_NICK · 2025-06-17 17:16:19 · 题解

使用笛卡尔树+树上启发式合并解决。
首先建笛卡尔树，然后按照树上启发式合并的一般套路，先枚举轻子树中的每个点，我们设此时根的值为 x，对于轻子树中每个点 v ，我们需要查询重子树中权值 \leq \frac{x}{w_v} 的数有几个，用线段树就能做。
最后不要忘记把轻子树和本身的贡献加入进去。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5, M = 1e9;
using ll = long long;
int n, l[N], r[N], s[N], sz[N], dfn[N], t[N], idx, son[N], top;
ll a[N], ans;
int rt;
vector<ll> p, w;
struct SegT {
  int t[N << 5], ls[N << 5], rs[N << 5], idx;
  void mod(int &u, int L, int R, int p, int x) {
    if (!u)
      u = ++idx;
    if (L == R)
      return t[u] += x, void();
    int mid = (L + R) / 2;
    if (p <= mid)
      mod(ls[u], L, mid, p, x);
    else
      mod(rs[u], mid + 1, R, p, x);
    t[u] = t[ls[u]] + t[rs[u]];
  }
  int query(int u, int L, int R, int l, int r) {
    if (!u)
      return 0;
    if (l <= L && R <= r)
      return t[u];
    int mid = (L + R) / 2, ret = 0;
    if (l <= mid)
      ret += query(ls[u], L, mid, l, r);
    if (r > mid)
      ret += query(rs[u], mid + 1, R, l, r);
    return ret;
  }
} T;
void dfs1(int u) {
  if (!u)
    return;
  dfn[u] = ++idx;
  t[idx] = u;
  sz[u] = 1;
  dfs1(l[u]), dfs1(r[u]);
  sz[u] += sz[l[u]] + sz[r[u]];
  son[u] = (sz[l[u]] > sz[r[u]] ? l[u] : r[u]);
}
void clear(int u) {
  for (int i = dfn[u]; i < dfn[u] + sz[u]; i++)
    T.mod(rt, 1, M, a[t[i]], -1);
}
void dfs2(int u) {
  if (!u)
    return;
  int hs = son[u], ls = l[u] ^ r[u] ^ son[u];
  dfs2(ls), clear(ls);
  dfs2(hs);
  for (int i = dfn[ls]; i < dfn[ls] + sz[ls]; i++) {
    int v = a[t[i]];
    ans += T.query(rt, 1, M, 1, a[u] / v);
  }
  for (int i = dfn[ls]; i < dfn[ls] + sz[ls]; i++)
    T.mod(rt, 1, M, a[t[i]], 1);
  T.mod(rt, 1, M, a[u], 1);
  ans += T.query(rt, 1, M, 1, 1);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cin >> n;
  a[0] = 2e9;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    while (a[s[top]] < a[i])
      l[i] = s[top--];
    r[s[top]] = i, s[++top] = i;
  }
  dfs1(r[0]);
  dfs2(r[0]);
  cout << ans;
}