【题解】蒜头君的项链

发表于 分类于 阅读次数： Valine： 本文字数： 759 阅读时长 ≈ 3 分钟

题目链接（计蒜客）

题目大意

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

$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)$