【Codeforces 643G】Choosing Ads

Author Avatar
mrsrz 1月 15, 2020

分块。

题目大意：

给定一个长度为 $n$ 的数列以及 $p$（$20\leq p\leq 100$）。

有两个操作：

  1. 区间修改为 $x$。
  2. 查询区间内出现了不少于 $p\%$ 的数，允许输出一定数量的不符合条件的数，但必须包含所有符合条件的数。

题解：

以下是一种分块做法。

对原数列进行分块，并对值域进行分块。我们记录 $tot[i][k]$ 表示前 $i$ 个块中，$k$ 的出现次数（分块前缀和思想）。并用一个数组记录每个块中出现过的元素。

用 set 维护所有总出现次数达到 $20\%S$（$S$ 为块大小，下同）的数。

对修改操作，边角直接暴力修改，整块的直接打修改标记。然后我们提取出所有出现次数产生变化的数值，对这些数值的前缀和数组暴力进行修改。单次求前缀和的复杂度是 $O(\frac n S)$ 的，但由于修改操作是区间赋值，所以重新求前缀和的总次数是 $O(n+m)$，复杂度均摊正确。

对查询操作，如果区间比较小，可以直接暴力求以减小常数。区间比较大时采用另外方法。

由于我们已经用 set 记录了总出现次数达到 $20\%S$（$S$ 为块大小，下同）的数，这样的数最多 $\frac {5n} S$ 个，我们需要对每个数，$O(1)$ 求其在区间内的出现次数。这些数在边角的出现次数，我们可以用一遍 $O(S)$ 的扫描求出对于全部数的出现次数。而在块间的出现次数，我们可以通过分块前缀和数组相减 $O(1)$ 求得。

不考虑 $20\%$ 带来的常数影响，容易得到当 $S=\sqrt n$ 时复杂度最优，为 $O((n+m)\sqrt n)$。

Code：

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<set>
#include<ctime>
const int N=1.6e5,siz=600,M=N/siz+2,K=siz*2/5;
std::set<int>st;
char buf[(int)1e8],*ss=buf;
inline void init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n',fclose(stdin);}
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
#define bel(x)((x-1)/siz+1)
int n,m,p,a[N];
int L[M],R[M],blocks,sta[N],top,vis[N],tag[M];
int STA[M][siz+2],TP[N],cnt[N];
int sum[N][M];
int pre[N][M];
inline void prefix(int id){
    st.erase(id);
    int*sum=::sum[id];int*pre=::pre[id];
    for(int i=1;i<=blocks;++i)
    pre[i]=pre[i-1]+sum[i];
    if(pre[blocks]>=K)st.insert(id);
}
inline void pushdown(int id){
    const int v=tag[id];
    tag[id]=0;
    TP[id]=1;
    STA[id][1]=v;
    for(int i=L[id];i<=R[id];++i)a[i]=v;
}
inline void rebuild(int id){
    int*s=STA[id],&top=TP[id];
    top=0;
    for(int i=L[id];i<=R[id];++i)if(!vis[a[i]])vis[a[i]]=1,s[++top]=a[i];
    for(int i=1;i<=top;++i)vis[s[i]]=0;
}
struct ostream{
    char buf[15000005],*s;
    inline ostream(){s=buf;}
    inline ostream&operator<<(int d){
        if(!d){
            *s++='0';
        }else{
            static int w;
            for(w=1;w<=d;w*=10);
            for(;w/=10;d%=w)*s++=d/w^'0';
        }
        return*this;
    }
    inline ostream&operator<<(const char&c){*s++=c;return*this;}
    inline void flush(){
        fwrite(buf,1,s-buf,stdout);
        s=buf;
    }
    inline~ostream(){flush();}
}cout;
int main(){
    init();
    n=readint(),m=readint(),p=readint();
    blocks=bel(n);
    for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;R[blocks]=n;
    for(int i=1;i<=n;++i){
        a[i]=readint();
        ++sum[a[i]][bel(i)];
    }
    for(int i=1;i<=n;++i)prefix(i);
    for(int x=1;x<=blocks;++x)rebuild(x);
    while(m--){
        if(readint()==1){
            int l=readint(),r=readint(),x=readint();
            const int bL=bel(l),bR=bel(r);
            if(bL==bR){
                if(tag[bL])pushdown(bL);
                top=0;
                for(int i=l;i<=r;++i){
                    --sum[a[i]][bL];
                    if(!vis[a[i]])vis[a[i]]=1,sta[++top]=a[i];
                    ++sum[a[i]=x][bL];
                }
                if(!vis[x])sta[++top]=x;
                for(int i=1;i<=top;++i)vis[sta[i]]=0,prefix(sta[i]);
                rebuild(bL);
            }else{
                if(tag[bL])pushdown(bL);
                top=0;
                for(int i=R[bL];i>=l;--i){
                    --sum[a[i]][bL];
                    if(!vis[a[i]])vis[a[i]]=1,sta[++top]=a[i];
                    ++sum[a[i]=x][bL];
                }
                if(tag[bR])pushdown(bR);
                for(int i=L[bR];i<=r;++i){
                    --sum[a[i]][bR];
                    if(!vis[a[i]])vis[a[i]]=1,sta[++top]=a[i];
                    ++sum[a[i]=x][bR];
                }
                for(int i=bL+1;i<bR;++i){
                    if(tag[i]){
                        sum[tag[i]][i]=0;
                        if(!vis[tag[i]])vis[tag[i]]=1,sta[++top]=tag[i];
                    }else{
                        const int*s=STA[i],&tp=TP[i];
                        for(int j=1;j<=tp;++j){
                            sum[s[j]][i]=0;
                            if(!vis[s[j]])vis[s[j]]=1,sta[++top]=s[j];
                        }
                    }
                    sum[x][i]=R[i]-L[i]+1;
                    tag[i]=x;
                }
                if(!vis[x])sta[++top]=x;
                for(int i=1;i<=top;++i)vis[sta[i]]=0,prefix(sta[i]);
                rebuild(bL),rebuild(bR);
            }
        }else{
            int l=readint(),r=readint();
            if(l>r)continue;
            const int LEN=r-l+1,C=LEN*p/100+!!(LEN*p%100),bL=bel(l),bR=bel(r);
            int ans[15],tans=0;
            if(r-l+1<=3*siz){
                top=0;
                for(int i=l;i<=r;++i){
                    const int x=tag[bel(i)]?tag[bel(i)]:a[i];
                    if(!vis[x])sta[++top]=x;
                    ++vis[x];
                }
                for(int i=1;i<=top;++i)
                if(vis[sta[i]]>=C)ans[++tans]=sta[i];
                if(tans)
                std::sort(ans+1,ans+tans+1);
                cout<<tans<<' ';
                for(int i=1;i<=tans;++i)
                cout<<ans[i]<<' ';
                cout<<'\n';
                for(int i=1;i<=top;++i)vis[sta[i]]=0;
            }else{
                top=0;
                if(tag[bL])pushdown(bL);
                if(tag[bR])pushdown(bR);
                for(int i:st)
                if(!vis[i])vis[i]=1,sta[++top]=i;
                for(int i=R[bL];i>=l;--i){
                    if(!vis[a[i]])vis[a[i]]=1,sta[++top]=a[i];
                    ++cnt[a[i]];
                }
                for(int i=L[bR];i<=r;++i){
                    if(!vis[a[i]])vis[a[i]]=1,sta[++top]=a[i];
                    ++cnt[a[i]];
                }
                for(int i=1;i<=top;++i){
                    cnt[sta[i]]+=pre[sta[i]][bR-1]-pre[sta[i]][bL];
                    if(cnt[sta[i]]>=C)ans[++tans]=sta[i];
                }
                if(tans)
                std::sort(ans+1,ans+tans+1);
                cout<<tans<<' ';
                for(int i=1;i<=tans;++i)
                cout<<ans[i]<<' ';
                cout<<'\n';
                for(int i=1;i<=top;++i)
                cnt[sta[i]]=vis[sta[i]]=0;
            }
        }
    }
//    fprintf(stderr,"%.3f\n",1.*clock()/CLOCKS_PER_SEC);
    return 0;
}
Powered by Hexo
Theme - Material