ZROI NOIP十连测 D9T1

发表于 更新于 本文字数： 635 阅读时长 ≈ 2 分钟

题意：给定长度为 nn 的序列 aa，令 f(l,r,x)f(l,r,x) 为 a[l,r]a[l,r] 内 xx 的出现次数，mm 次询问，找到一个 pp 使得 f(1,p,x)×f(p+1,n,y)f(1,p,x)\times f(p+1,n,y) 最大，输出最大值。

1≤n,m≤105,1≤ai≤1091\leq n,m\leq 10^5,1\leq a_i\leq 10^9

考虑根号分治（实际上我赛时完全没想到这个）。不会的话可以看看这篇日报

由于序列 aa 中出现次数大于等于 n\sqrt n 的数最多只有 n\sqrt n 个，所以对于这类数，我们可以直接 O(nn)O(n\sqrt n) 预处理出它与其它所有数的答案，在询问的时候只要 xx 和 yy 中有至少一个的出现次数大于等于 n\sqrt n，就可以进行 O(1)O(1) 查询。

对于出现次数小于 n\sqrt n 的数，我们可以提前记录下它们在序列中出现的位置，然后在询问的时候就能直接枚举它出现的位置进行计算，由于位置数量小于 n\sqrt n，因此可以在 O(n)O(\sqrt n) 的复杂度下算出。

综合起来本题的复杂度就是 O(n)O(\sqrt 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
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn = 1e5 + 5;
const int B = 320;
int n, m;
int a[maxn], b[maxn], tot;
int tong[maxn];
int cnt[maxn];
int large[maxn], num, rnk[maxn];
ll s[maxn][B + 5], t[B + 5][maxn];
vector<int> g[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        b[i] = a[i];
    sort(b + 1, b + 1 + n);
    tot = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
    for (int i = 1; i <= n; i++)
        g[a[i]].push_back(i);
    for (int i = 1; i <= n; i++)
        tong[a[i]]++;
    for (int i = 1; i <= tot; i++)
        if (tong[i] >= B)
            large[++num] = i, rnk[i] = num;
    for (int i = 1; i <= n; i++)
    {
        ++cnt[a[i]];
        for (int j = 1; j <= num; j++)
            s[a[i]][j] = max(s[a[i]][j], 1ll * cnt[a[i]] * (tong[large[j]] - cnt[large[j]]));
    }
    for (int i = 1; i <= tot; i++)
        cnt[i] = 0;
    for (int i = n; i >= 1; i--)
    {
        ++cnt[a[i]];
        for (int j = 1; j <= num; j++)
            t[j][a[i]] = max(t[j][a[i]], 1ll * cnt[a[i]] * (tong[large[j]] - cnt[large[j]]));
    }
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        x = lower_bound(b + 1, b + 1 + tot, x) - b;
        y = lower_bound(b + 1, b + 1 + tot, y) - b;
        if (x == y)
            cout << 1ll * (tong[x] / 2) * (tong[x] - tong[x] / 2) << endl;
        else if (tong[x] >= B)
            cout << t[rnk[x]][y] << endl;
        else if (tong[y] >= B)
            cout << s[x][rnk[y]] << endl;
        else
        {
            int yp = 0, num = 0;
            ll ans = 0;
            for (int i : g[x])
            {
                ++num;
                while (yp < g[y].size() && g[y][yp] < i)
                    ++yp;
                ans = max(ans, 1ll * num * (tong[y] - yp));
            }
            cout << ans << endl;
        }
    }
    return 0;
}