Codeforces 786C. Till I Collapse 主席树
2024-08-27 21:47:14
题目大意:
给定一个长度为\(n\)的序列,要求将其划分为最少的若干段使得每段中不同的数字的种数不超过\(k\).
对于 \(k = 1 .. n\)输出所有的答案.
\(n \leq 10^5\)
题解:
考虑最坏情况下会分成多少段.
最坏分成\(\frac{n}{k}\)段。
所以对于每种\(k\)将其段数加起来。
有\(O(\sum_{k=1}^n\frac{n}{k})= O(n\log n)\)
所以我们可以考虑每次找出下一个端点进行转移。
复杂度为\(O(\text{转移}nlogn)\)
对于每次转移我们要找到最大的一个元素使得从当前点向右经过的不同的数字种数\(\leq k\)
假设说我们有一个数组\(f_{p,i}\)表示从\(p\)开始往后\(i\)是否是第一次出现。
那么我们就可以通过在线段树上二分的方式在\(\log n\)的时间确定这个坐标。
考虑对每一个\(p\)建立\(f_{p,i}\)的线段树。
然后发现\(f_p\)与\(f_{p+1}\)只有两个元素不同的区别。
所以可以建立可持久化线段树完成这个东西的维护。
复杂度\(O(n\log^2n)\)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 100010;
struct Node{
Node *ch[2];
int num;
void update(){
num = ch[0]->num + ch[1]->num;
}
}mem[maxn*40],*null,*it,*root[maxn];
inline void init(){
it = mem;null = it++;
null->ch[0] = null->ch[1] = null;
null->num = 0;root[0] = null;
}
Node* modify(Node *rt,int l,int r,int pos,int val){
Node *p = it++;*p = *rt;
if(l == r){
p->num = val;
return p;
}
int mid = l+r >> 1;
if(pos <= mid) p->ch[0] = modify(p->ch[0],l,mid,pos,val);
else p->ch[1] = modify(p->ch[1],mid+1,r,pos,val);
p->update();return p;
}
inline int find(Node *p,int l,int r){
if(l == r && p->num != 0) return -1;
if(l == r) return l;
int mid = l+r >> 1;
if(p->ch[0]->num == 0) return max(mid,find(p->ch[1],mid+1,r));
else return find(p->ch[0],l,mid);
}
int query(Node *p,int l,int r,int k){
if(l == r) return l;
int mid = l+r >> 1;
if(k > p->ch[0]->num){
k -= p->ch[0]->num;
return query(p->ch[1],mid+1,r,k);
}else if(k < p->ch[0]->num) return query(p->ch[0],l,mid,k);
else return max(mid,find(p->ch[1],mid+1,r));
}
int nx[maxn],la[maxn],ws[maxn];
int a[maxn],n;
inline int solve(int k){
int pos = 1,x,ans = 0;
while(pos <= n){
x = query(root[pos],1,n,min(k,n-pos+1));
pos = x+1;++ ans;
}return ans;
}
int main(){
read(n);
rep(i,1,n) read(a[i]);
memset(ws,-1,sizeof ws);
rep(i,1,n){
la[i] = ws[a[i]];
ws[a[i]] = i;
}
memset(ws,-1,sizeof ws);
per(i,n,1){
nx[i] = ws[a[i]];
ws[a[i]] = i;
}
init();
root[1] = root[0];
rep(i,1,n){
if(la[i] == -1) root[1] = modify(root[1],1,n,i,1);
}
rep(i,2,n){
root[i] = modify(root[i-1],1,n,i-1,0);
if(nx[i-1] != -1) root[i] = modify(root[i],1,n,nx[i-1],1);
}
rep(k,1,n){
printf("%d",solve(k));
if(k != n) putchar(' ');
else putchar('\n');
}
return 0;
}
最新文章
- 掌握javascript中的最基础数据结构-----数组
- php函数获取真实客户端IP地址
- Java replace() 方法
- [Hive - LanguageManual] Statistics in Hive
- ASP.NET html转图片
- SpringBoot笔记一
- Zookeeper实践方案:(4)命名服务
- AOP:代理思想 (没有考虑到Spring)
- 利用NSURLSession下载视频,图片,能实现断点续传
- vim编辑器的使用技巧
- Net 面试随想
- Kotlin封装RxJava与Retrofit
- UML类图的简单梳理
- jmeter和jdk的安装教程
- spring boot集成redis实现session共享
- Sql 无法解决 equal to 运算中 ";Chinese_PRC_CI_AS"; 和 ";Chinese_PRC_90_CI_AI"; 之间的排序规则冲突
- python 之 模块
- 15. 3Sum C++
- python catch socket timeout
- python selenium-9 grid模式