CF1514D Cut and Stick
题目链接:https://codeforces.com/contest/1514/problem/D
题目大意
给定一个长度为 n 的序列 (n\le3\times10^5),可以对其进行三种操作:
要求:给定 q 个询问 (q\le3\times10^5) ,每次给出一个区间的左右端点,将这个区间分成若干个片段,使得每个片段内任意元素出现的次数不严格大于\lceil\frac{x}{2}⌉ (x 为该片段长度)。求可以分成的最少片段数目。
Solution
这其实是一个绝对众数问题,在一个合法段里,一个元素最多出现\lceil\frac{x}{2}⌉ 。
考虑一段里出现次数最多的数是 a ,那么这一段如果有 p 个不是 a 的元素,如果使得这一段合法,这一段最多能出现 p+1 个 a ( 显然可以出现 p 个,之所以多个 1 是因为题目说了向上取整。
考虑 [L,R] 中共有 n 个数字,出现次数最多的元素 x 出现了 k 次,就有 n-k 个不是 x 的元素。假如这 n-k 个元素可以形成 p 段(贡献了 p 段),按照上文所说的就可以抵消掉 n-k+p 个 x ,现在还剩下 k-(n-k+p)=2*k-n-p 个 x ,只能每个 x 单独放一段,所以总共先就是
2*k-n-p+p=2*k-n
至于怎样找到出现最多的这个次数,可以用主席树,官方题解给了随机化的方式也非常不错~
code:
#include<bits/stdc++.h>
const int N = 3e5 + 10 ;
std::unordered_map<int,int> mp;
int n,m,a[N],b[N];
int sum[N<<5],ls[N<<5],rs[N<<5];
int rk[N],cnt,rt[N];
int cmp(int x,int y){
return a[x]<a[y];
}
void copy(int old,int cur){
sum[cur]=sum[old],ls[cur]=ls[old],rs[cur]=rs[old];
}
void pushup(int cur){
sum[cur]=sum[ls[cur]]+sum[rs[cur]];
}
int build(int l,int r){
int cur = ++cnt;
if(l==r) return cur;
int mid = l+r>>1;
ls[cur]=build(l,mid);
rs[cur]=build(mid+1,r);
return cur;
}
int add(int pre,int cur,int l,int r,int x){
cur = ++cnt;
copy(pre,cur);
if(l==r){
sum[cur]=sum[pre]+1;
return cur;
}
int mid = l + r >> 1;
if(x<=mid) ls[cur] = add(ls[cur],cur,l,mid,x);
else rs[cur] = add(rs[cur],cur,mid+1,r,x);
pushup(cur);
return cur;
}
int ask(int pre,int cur,int l,int r,int len){
if(l==r){
if(sum[cur]-sum[pre]>len) return sum[cur]-sum[pre];
return 0;
}
int mid = l+r>>1;
if(sum[ls[cur]]-sum[ls[pre]]>len) return ask(ls[pre],ls[cur],l,mid,len);
if(sum[rs[cur]]-sum[rs[pre]]>len) return ask(rs[pre],rs[cur],mid+1,r,len);
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
rt[0]=build(1,n);
for(int i=1;i<=n;++i)
rt[i]=add(rt[i-1],rt[i],1,n,a[i]);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
int p = (r-l+1)/2+((r-l+1)&1);
int k = ask(rt[l-1],rt[r],1,n,p);
if(k!=0) printf("%d\n",2*k-(r-l+1));
else printf("%d\n",1);
}
return 0;
}
0 条评论