Codeforces Round #401 (Div. 1) C(set+树状数组)

题意： 给出一个序列，给出一个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]);
}