題意： 給出一個序列，給出一個k，要求給出一個劃分方案，使得連續區間內不同的數不超過k個，問劃分的最少區間個數，輸出時將k=1~n的答案都輸出

?

比賽的時候想的有點偏，然后寫了個nlog^2n的做法，T了

賽后發現有更加巧妙的做法

?

題解：

首先，可以貪心地想

也就是說從第一個數開始，每個區間都盡量往后選，直到不能選為止，可以證明這樣是最優的

那么如果按照這個方案，實際上區間的選取都是固定的。

所以位置為i的數有可能是k=1，k=2....k=t的起點

如果當前位置是i，我們考慮如何更新答案

首先對答案有影響的只有在i右邊的不同類別的第一個數，比如i右邊有1 2 3 1 2，那么有影響的只有前3個數

所以考慮動態插入一個樹狀數組

也就是說當前位置是i，k=t，那么k=t的下一個區間的位置就是去找樹狀數組內的一個區間，內部有t個不同的數（樹狀數組也可以查詢這個問題）

然后從1到n枚舉區間的起點，過程中更新k=t的下一個位置，并在每個位置用vector存包含了k為若干值的情況

（可以證明vector最多存nlogn個點，n+n/2+n/3+....+n/n約等于nlogn）

可以使用一個數組next存下一個位置的情況，也可以使用set來維護這個位置信息。

代碼如下

#include <iostream> #include <cstdio> #include <vector> #include <set> #define pb push_back using namespace std; const int maxn = 1e5 + 5; int c[maxn], ans[maxn], a[maxn]; set<int> S[maxn]; vector<int> L[maxn]; int n; void Modify(int x, int s){for(; x <= n; x += x&(-x)) c[x] += s; } int Find(int x){ //實際上只找x-1個數字int p = 0;for(int i = 20; i >= 0; i--){if(p + (1<<i) <= n && c[p + (1<<i)] < x) {x -= c[p + (1<<i)];p += (1<<i);}}return p+1; }void gao(int i){if(!S[i].empty()){Modify(*S[i].begin(), 1);S[i].erase(*S[i].begin());} }int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", a+i), S[a[i]].insert(i);for(int i = 1; i <= n; i++){L[1].pb(i);gao(i);}for(int i = 1; i <= n; i++){for(auto x : L[i]){int y = Find(x+1);L[y].pb(x);ans[x]++;}Modify(i, -1);gao(a[i]);}for(int i = 1; i <= n; i++) printf("%d ", ans[i]); }

?

轉載于:https://www.cnblogs.com/Saurus/p/6610316.html

總結

以上是生活随笔為你收集整理的Codeforces Round #401 (Div. 1) C(set+树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。