【题解】蒜头君的项链

发表于 分类于 阅读次数： Valine：

题目链接（计蒜客）

题目大意

给出有\(n\)个元素的序列\(a\)，现在将序列分成若干连续的段，每个段的不同元素种类数不能超过\(k\)。对于\(1\le k \le n\)的每一个正整数\(k\)，计算最少划分成多少段。

\(1\le n \le 10^5,~1 \le a_i \le n\)

40pts

类似于HH的项链

对于\(r\)有序的询问，用树状数组快速求区间不同元素的个数

枚举每个\(k\)，之后用两个指针\(l,r\)，找到最大的\(r\)使得不同元素的个数\(\le k\)，之后令\(l=r+1\)

复杂度\(O(n^2)\)

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
int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    int l = 1, r = 1, kmax = 0;
    for (int i = 1; i <= n; i++) {
        if (!book[a[i]]) {
            kmax++;
            book[a[i]] = 1;
        }
    }
    memset(book, 0, sizeof(book));
    for (int k = 1; k < kmax; k++) {
        cnt = 1, l = 1;
        memset(c, 0, sizeof(c)); memset(book, 0, sizeof(book));
        for (int i = 1; i <= n;) {
            if (book[a[i]]) update(book[a[i]], -1);
            update(i, 1);
            book[a[i]] = i;
            if (getsum(i) - getsum(l - 1) > k) l = i,cnt++; //记录分成了几条项链
            else i++;
        }
        printf("%d ", cnt);
    }
    for (int i = kmax; i <= n; i++) printf("1 ");
    return 0;
}

100pts

考虑转换枚举顺序。

枚举左端点\(l\)，快速求出一个最大的\(maxr\)使得\([l,r]\)内元素的种类数\(\le k\)。

开\(\text{vector}~ q_l\)记录对于\(l\)需要计算的\(k\)。

枚举到\(l\)时遍历\(q_l\)，取出\(k\)，对于\(l\)求出\(maxr\)

将\(k\)放进\(q_{maxr+1}\)中，\(ans_k++\)

如何求\(maxr\)?

对于每个出现在位置\(i\)的元素\(a_i\)，预处出理数组\(nxt(i)\)，表示元素\(a_i\)在位置\(i\)出现后，下一次出现的位置。

仍然使用树状数组统计，开始时将所有的元素第一次出现的位置赋为\(1\)。

\(l\)向右移动时，清除树状数组中\(l\)的值并将\(nxt(a_l)\)赋为\(1\)。

\([1,r]\)的和即为当前\([l,r]\)中不同元素的数量。

因为树状数组求和每次减\(lowbit\)，即\(2^p\)，我们用类似倍增的思想，对于\(r\)直接枚举二进制位\(p\)，求出\(maxr\)。

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
vector<ll> q[N];

int query(int x) {
    int p = 0, s = 0;
    for (int i = 20; i != -1; i--) {
        if (p + (1 << i) > n) continue;
        if (s + tree[p + (1 << i)] <= x) s += tree[p += 1 << i];
    }
    return p + 1;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) {
        if (!last[a[i]]) update(i, 1);
        else nxt[last[a[i]]] = i;
        last[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) q[1].push_back(i);
    //vector[i]里存的是要以i为左端点进行计算的k
    for (int i = 1; i <= n; i++) {//枚举所有左端点
        int len = q[i].size();
        for (int j = 0; j < len; j++) { //枚举所有要计算的k
            int x = q[i][j];
            ans[x]++;
            //query(x)为能找到的最大的右端点 + 1
            q[query(x)].push_back(x);
        }
        update(i, -1);
        if (nxt[i]) update(nxt[i], 1);
    }

    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

复杂度

计算\(k\)的数量最多是\(O(n+\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+...)=O(n\ln n)\)

计算\(maxr\)是\(O(\log_2 n)\)

总复杂度是\(O(n\log n^2)\)