luogu4755Beautiful_Pair题解

发表于 更新于

luogu4755Beautiful_Pair

标签 ：分治 + RMQ + 树状数组 + 启发式

这题看起来很分治，所以考虑分治。

一般的分治是在中间分开，可以发现这道题在中间分开并没有很好的性质。

于是 果断放弃 我们发现如果在最大值处分开会有很好的性质。因为在最大值处分开，所以左边的点和右边的点之间的最大值确定。(最大值可以用 ST表ST表 求)

考虑枚举左端点，那么右端点要满足的条件是 ar×al≤amida_r \times a_l \leq a_{mid}, 即 ar≤amidala_r \leq \frac{a_{mid}}{a_l} 。所有满足条件的右端点的个数就是区间 [mid,r][mid,r] 中值比 amidal\frac{a_{mid}}{a_l} 小的点的数量，这个可以直接用主席树求，也可以离线下来用树状数组求。

发现从最大值处分开的话复杂度并不正确，是 O(n2lg⁡n)O(n^2\lg n) .

可以运用启发式思想，在枚举端点时，不一定必须枚举左端点，可以在 midmid 两边长度更小的那个区间中枚举端点，这样复杂度就是O(nlg⁡2n)O(n \lg^2n) 的啦，证明如下。

对于每个点，每当它被枚举到一次，它所在的分治区间会缩小至少一半，所有对于每个点，他最多被枚举 O(lg⁡n)O(\lg n) 次，所以树状数组最多会接受到 O(nlg⁡n)O(n \lg n) 次询问，复杂度自然就是 O(nlg⁡2n)O(n \lg^2 n)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 1e5 + 10;
int n;

struct QUE
{
  int x, v, op;
  bool operator < (const QUE b) const
  {
    return x < b.x;
  }
}q[3 * N * 20];
int tot;

int a[N], b[4 * N * 20], cnt;
int st[N][30], d[N][30], lg[N];
ll ans;
int val[N * 6 * 20];

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

void add(int x, int v)
{
  for (int i = x; i <= 20 * n; i += lowbit(i))
  {
    val[i] += v;
  }
}

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

int find(int l, int r)
{
  int k = lg[r - l + 1];
  if (st[l][k] > st[r - (1 << k) + 1][k])
  {
    return d[l][k];
  }
  else return d[r - (1 << k) + 1][k];
}

void dfs(int l, int r)
{
  if (l == r) return ans += (a[l] == 1), void();
  if (l > r) return ;
  int mx = find(l, r);
  if (r - mx < mx - l)
  {
    for (int i = mx; i <= r; ++i)
    {
      q[++tot] = (QUE){mx, a[mx] / a[i], 1};
      q[++tot] = (QUE){l - 1, a[mx] / a[i], -1};
    }
  }
  else
  {
    for (int i = l; i <= mx; ++i)
    {
      q[++tot] = (QUE){r, a[mx] / a[i], 1};
      q[++tot] = (QUE){mx - 1, a[mx] / a[i], -1};
    }
  }
  dfs(l, mx - 1);
  dfs(mx + 1, r);
}

int main()
{
  scanf("%d", &n);
  lg[1] = 0;
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", &a[i]);
    st[i][0] = a[i], d[i][0] = i;
  }
  for (int i = 2; i <= n; ++i)
  {
    lg[i] = lg[i / 2] + 1;
  }
  for (int k = 1; k <= lg[n]; ++k)
  {
    for (int i = 1; i <= n - (1 << k) + 1; ++i)
    {
      if (st[i][k - 1] > st[i + (1 << (k - 1))][k - 1])
      {
        st[i][k] = st[i][k - 1];
        d[i][k] = d[i][k - 1];
      }
      else 
      {
        st[i][k] = st[i + (1 << (k - 1))][k - 1];
        d[i][k] = d[i + (1 << (k - 1))][k - 1];
      }
    }
  }
  dfs(1, n);
  for (int i = 1; i <= n; ++i)
  {
    b[++cnt] = a[i];
  }
  for (int i = 1; i <= tot; ++i)
  {
    b[++cnt] = q[i].v;
  }
  sort(b + 1, b + cnt + 1);
  for (int i = 1; i <= n; ++i)
  {
    a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
  }
  for (int i = 1; i <= tot; ++i)
  {
    q[i].v = lower_bound(b + 1, b + cnt + 1, q[i].v) - b;
  }
  sort(q + 1, q + tot + 1);
  int u = 0;
  for (int i = 1; i <= tot; ++i)
  {
    while (u < q[i].x)
    {
      ++u;
      add(a[u], 1);
    }
    ans += 1ll * q[i].op * query(q[i].v);
  }
  cout << ans << endl;
  return 0;
}

注意数组的大小, 有些数组大小级别是 O(nlg⁡n)O(n\lg n)