25暑期10

发表于 更新于 分类于 ， 阅读次数： 作者 Cool-breeze ， Pomelorin

Problem F

把数组 \(\{a_n\}\) 分为三段，使得在三段内同时出现的数字数量最大。输出最大值以及左右指针（即分割方法）。

\(3\le n\le150000,1\le a_i\le10^6\)。

点击查看题解

对于每个出现次数大于等于 \(3\) 的数字，都能保证存在将此数字分在三段上的左指针范围和右指针范围。问题转化为，有 \(m\) 组条件，每组条件为 \(l_{i1}\le a\le r_{i1}\)（左区间）且 \(l_{i2}\le b\le r_{i2}\)（右区间），求使得满足条件组数最多的 \(a\) 和 \(b\)。

从左到右枚举左指针位置，用线段树维护答案。当左指针进入一个左区间后，对应右区间 +1；退出一个左区间后，对应右区间 -1。每次移动后，查询区间最大值即可。

具体来说，先维护每一种数字出现的最右位置，以及每一个数字的后一个相同数字的位置（即每一个数字的后继）。

然后当左指针向右移动，一个新的数加入了第一个区间，就在线段树上将这个数的后继到最右位置全部 +1，因为这个数会使右端点在这个区间范围内贡献 +1。

如果一个数字不是第一个加入第一个区间，那就要在线段树上减去这个数到这个数的后继。

每次移动左指针，直接查询线段树 \([1,n]\) 最值即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 150005;
int a[N];
int mmax[4 * N]; 
int iindex[4 * N]; 
int lz[4 * N]; 

void push_up(int n) {
    mmax[n] = max(mmax[2 * n], mmax[2 * n + 1]);
    iindex[n] = (mmax[2 * n] >= mmax[2 * n + 1]) ? iindex[2 * n] : iindex[2 * n + 1];
}

void push_down(int n,int mid,int l,int r) {
    lz[2 * n] += lz[n]; 
    lz[2 * n + 1] += lz[n];
    mmax[2 * n] += lz[n];
    mmax[2 * n + 1] += lz[n];
    lz[n] = 0;
}

void build(int n,int l,int r) {
    if (l == r) {
        mmax[n] = 0;
        iindex[n] = l;
        return;
    }
    lz[n]=0;
    int mid = (l + r) >> 1;
    build(2 * n, l, mid);
    build(2 * n + 1, mid + 1, r);
    push_up(n);
    return;
}

void update(int n,int l,int r,int x,int y,int k) {
    if (x <= l && y >= r) {
        lz[n] += k;
        mmax[n] += k;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(n, mid, l, r);
    if (x <= mid) {
        update(2 * n, l, mid, x, y, k);
    }
    if (y > mid) {
        update(2 * n + 1, mid + 1, r, x, y, k);
    }
    push_up(n);
    return;
}

int rr[1000005], nex[N], pos[1000005];
int b[1000005];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= 1000000; i++) {
        rr[i] = -1, pos[i] = -1;
        b[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        rr[a[i]] = max(rr[a[i]], i);
        nex[i] = -1;
        if (pos[a[i]] != -1) {
            nex[pos[a[i]]] = i;
        }
        pos[a[i]] = i;
    }
    for (int i = 1; i <= 4 * n + 3; i++) {
        lz[i] = 0;
    }
    build(1ll, 1ll, n);
    int ans = 0, index1 = 2, index2 = 3;
    for (int i = 2; i < n; i++) {
        int x = a[i - 1];
        if (b[x] == 0) {
            b[x] = 1;
            //first time
            if (nex[i - 1] != -1 && rr[x] != nex[i - 1]) {
                update(1ll, 1ll, n, nex[i - 1] + 1, rr[x], 1);
            }
        } else {
            if (nex[i - 1] != -1) {
                update(1ll, 1ll, n, i, nex[i - 1], -1);
            }
        }
        if (mmax[1] > ans) {
            ans = mmax[1], index1 = i, index2 = iindex[1];
        }
    }
    cout << ans << endl << index1 << ' ' << index2 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}