线段树二分）"/>
CF786C Till I Collapse 题解 （主席树 + 线段树二分）
题目描述
对于 k = 1 , 2 , 3 , . . . , n k = 1,2,3,...,n k=1,2,3,...,n，分别求出最小的 m m m，使得存在一种将 n n n 个数划分成 m m m 段的方案，每段中不同数字的个数不超过 k k k 个。
1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 1 ≤ a i ≤ n 1 \leq a_i \leq n 1≤ai≤n。
输入样例：
5
1 3 4 3 3
输出样例：
4 2 1 1 1
分析：
首先很容易能够想到一个 n 2 n^2 n2 的暴力：那就是对于每一个询问 k k k，我们从起点往后拓展，如果当前段内的数字个数超过了 k k k，那么新开一段，否则就仍然使用当前段。最后输出段的数量就好了。可以证明这样的贪心是对的。
我们考虑怎样优化这一过程。现在的问题在于对于一个起点 x x x 而言，怎样快速找到一个长度 l e n len len，使得 [ x , x + l e n − 1 ] [x, x + len - 1] [x,x+len−1] 里面出现了 k k k 种数字。
注意到如果起点确定，那么影响 l e n len len 的长度的应该是 在起点右边，每种数字最靠左的位置。因为这些位置能够最先影响到区间内的数字种类数。
但是我们不能开一个二维数组去记录一每一个位置为起点，每种数字最靠左的位置。这样空间复杂度是不允许的并且也不好查询。 我们考虑 主席树。
我们维护一棵 可持久化线段树，对于每一个位置 i i i 而言，线段树的根为 r o o t i root_i rooti。具体来讲，我们倒序插入每个 a i a_i ai，如果 a i a_i ai 到当前为止是第一次出现的，我们就让 r o o t i root_i rooti 的 i i i 位置上加 1 1 1。否则，就让 r o o t i root_i rooti 的 l s t a i lst_{a_i} lstai 位置减 1 1 1，让 i i i 位置加 1 1 1。其中 l s t x lst_x lstx 表示 x x x 上一次出现的位置。
这样做的好处在于我们每次只用对线段树进行 单点修改，其它的直接继承就好。并且十分方便查询。
这样做，我们就可以在起点 x x x 的线段树上二分，找到第一个位置 y y y 使得 [ x , y ] [x, y] [x,y] 的种类数为 k k k。并且线段树中只需要维护 区间和 即可。
我们来计算一下时间复杂度：每一次二分的时间复杂度显然是 O ( l o g 2 n ) O(log_2n) O(log2n)。因为对于一个询问 k k k 而言，答案不会超过 n k \frac{n}{k} kn（每 k k k 个一段显然合法），那么所有询问的二分次数加起来是 ∑ i = 1 n n i ≈ n l o g 2 n \sum_{i = 1}^{n} \frac{n}{i} \approx nlog_2n ∑i=1nin≈nlog2n。所以总复杂度是 O ( n l o g 2 2 n ) O(nlog^2_2n) O(nlog22n)。
CODE：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
inline int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int n, a[N], lst[N];
namespace Seg{int tot, root[N];struct SegmentTree{int ls, rs, num;#define ls(x) t[x].ls#define rs(x) t[x].rs#define num(x) t[x].num}t[N * 25 * 2];int build(){tot++;ls(tot) = rs(tot) = num(tot) = 0;return tot;}void update(int p){num(p) = num(ls(p)) + num(rs(p));}int ins(int p, int lp, int rp, int pos, int c){// 可持久化线段树 int tp = build(); t[tp] = t[p];if(lp == rp){num(tp) += c;return tp;}int mid = (lp + rp >> 1);if(pos <= mid) ls(tp) = ins(ls(tp), lp, mid, pos, c);else rs(tp) = ins(rs(tp), mid + 1, rp, pos, c);update(tp);return tp;}int query(int p, int lp, int rp, int k){if(lp == rp) return lp;int mid = (lp + rp >> 1);if(k <= num(ls(p))) return query(ls(p), lp, mid, k);else return query(rs(p), mid + 1, rp, k - num(ls(p)));}
}
int main(){n = read();for(int i = 1; i <= n; i++) a[i] = read();for(int i = n; i >= 1; i--){if(!lst[a[i]]){Seg::root[i] = Seg::ins(Seg::root[i + 1], 1, n, i, 1);lst[a[i]] = i;}else{int k = Seg::ins(Seg::root[i + 1], 1, n, lst[a[i]], -1);Seg::root[i] = Seg::ins(k, 1, n, i, 1);lst[a[i]] = i;}}for(int i = 1; i <= n; i++){int now = 1, res = 0;while(now <= n){if(i >= Seg::num(Seg::root[now])) now = n + 1;else now = Seg::query(Seg::root[now], 1, n, i + 1);//找到第 i + 1 个 res++;}printf("%d ", res);}return 0;
}
更多推荐
CF786C Till I Collapse 题解 （主席树 + 线段树二分）
发布评论