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;
}