Codeforces 786 C. Till I Collapse

题目链接：http://codeforces.com/contest/786/problem/C

大力膜了一发杜教的代码感觉十分的兹瓷啊！

　　我们知道如果$k$是给定的我们显然是可以直接一遍$O(n)$的贪心扫过去的，那么问题很显然的变成了支持一个数据结构，维护一段区间内不同数字的个数(事实上是固定左端点求最远的右端点使得这段区间内不同数字的个数小于等于$k$)。嗯，很可以，如果写过HH的项链的话你就有可能.....

HH的项链是有莫队做法和离线询问预处理$next$数组并用树状数组维护两种做法的，考虑如何转换第二种做法。(${next}$数组表示与第$i$个点颜色相同的在$i$之后的第一个点的位置)

　　这里离线询问显然是不现实的(不知道要询问哪一些区间)，考虑我们不是要做$n$次么，每一次的询问都是不停的往右边跳，所以拿一根扫描线从左到右扫过去，对于每一个位置做以这个位置为左端点的询问，然后把这个询问丢到查询出来的右端点的右边那一个点上去，用一个树状数组维护每个颜色出现的位置，扫描线扫过一个点之后消除这个点所在位置的影响，增加这个点的$next$的点所在位置的影响。树状数组查询的时候利用它的性质倍增的查询，就不需要二分了。

　　一共有$n$次从左往右的跳跃，所以总跳跃的次数是${O(nlogn)}$的，树状数组利用倍增查询的复杂度是${O(logn)}$的，最后复杂度${O(nlog^{2}n)}$。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<map>
 8 #include<cstring>
 9 using namespace std;
10 #define maxn 1001000
11 #define TIMES 17
12 #define llg int
13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
14 llg n,m,a[maxn],k,sum[maxn],c[maxn],xian[maxn],nextt[maxn],ans[maxn];
15 vector<llg>f[maxn];
16 
17 inline int getint()
18 {
19        int w=0,q=0; char c=getchar();
20        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
21        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
22 }
23 
24 llg lowbit(llg x) {return x&-x;}
25 
26 void add(llg x,llg val) {for (;x<=n+1;x+=x&-x) c[x]+=val;}
27 
28 llg find (llg x)
29 {
30     llg pos=0;
31     for (llg i=TIMES;i>=0;i--)
32     {
33         if (pos+(1<<i)<=n+1 && c[pos+(1<<i)]<x) 
34             x-=c[pos+(1<<i)],pos+=(1<<i);
35     }
36     return pos+1;
37 }
38 
39 int main()
40 {
41     yyj("E");
42     cin>>n;
43     for (llg i=1;i<=n;i++) a[i]=getint();
44     for (llg i=1;i<=n+1;i++) xian[i]=n+1;
45     for (llg i=n+1;i>=1;i--) 
46     {
47         nextt[i]=xian[a[i]];
48         xian[a[i]]=i;
49     }
50     
51     for (llg i=1;i<=n+1;i++) add(xian[i],1),f[1].push_back(i);;
52     for (llg i=1;i<=n;i++)
53     {
54         llg w=f[i].size();
55         for (llg j=0;j<w;j++)
56         {
57             llg d=f[i][j];
58             llg wz=find(d+1);
59             ans[d]++;
60             f[wz].push_back(d);
61         }
62         add(i,-1),add(nextt[i],1);
63     }
64     for (llg i=1;i<=n;i++) printf("%d ",ans[i]);
65     return 0;
66 }