题解 CF643G 【Choosing Ads】

· · 题解

\Huge\color{#ffa030}{\tt My~Cnblogs}

CF643G Choosing Ads

1. ``1 l r id`` 令 $i\in[l,r]:a_i=id$。 2. ``2 l r`` 输出至多 $\lfloor\frac{100}{p}\rfloor$ 个数，其中包括所有 $[l,r]$ 区间内出现 $\ge\lceil\frac{p(r-l+1)}{100}\rceil$ 次的 $a_i$。 数据范围：$1\le n,m,id,a_i\le 150000$，$20\le p\le 100$，$1\le l\le r\le n

一眼想法：搞个线段树，节点存该区间出现频率 \ge\frac{p}{100} 的 a_i 值和出现次数存下来，合并。

这个做法的依据： 如果区间 [l,r] 中 a_i 出现频率 \ge\frac{p}{100}，[l,mid] 或 [mid+1,r] 必中有一个也满足。

这个做法的 \tt bug： 若 a_i 存在于 [l,mid] 的节点中而不存在于 [mid+1,r] 的节点中（或反过来），节点的信息难以合并。

于是，我这个思维愚钝的大蒟蒻就没在考场上做出来。

这题的正解类似以前的一道经典题：一个序列求众数（出现频率 \ge \frac 12），空间复杂度 只能 \Theta(1)。

做法是记录 now 和 cnt。新加入数 a 的时候，如果 [now=a]，cnt++；如果 [now\not=a]，cnt--，如果 [cnt<0]，cnt=1 并且 now=a。

这题也类似。出现频率 \ge\frac{p}{100} 的数至多 \lfloor\frac{100}{p}\rfloor 个，所以可以记录 \lfloor\frac{100}{p}\rfloor 个 now_i 和 cnt_i。

每次加入 a，如果 [now_i=a]，cnt_i++；如果 [now_i\not=a]，cnt_i--，如果 [cnt_i<0]，cnt_i=1 并且 now_i=a。

这样的话虽然只存了 \lfloor\frac{100}{p}\rfloor 种数，但已经完全反映了区间内数的数量对比，所以节点信息可以直接合并。

最后每个节点或许会存下不满足出现频率 \ge\frac{p}{100} 的值，但是输出只要包含答案就行了（题中说的）。

稍微长了点，但是没有坑人的细节，直接写就好了。

#include <bits/stdc++.h>
using namespace std;

//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

//Data
const int N=150000;
int n,m,p,pl,a[N+7];

//Segmenttree
typedef vector<pair<int,int>> vpii;
#define mid ((l+r)>>1)
#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
int mk[N<<2]; vpii ca[N<<2]; //pair.x 表示 now_i，pair.y 表示 cnt_i
void fill(vpii&v,int id,int c){v.clear(),v.pb(mp(id,c));}
vpii operator+(vpii p,vpii q){ //将 p 中的数一一加入 q
    vpii r;
    for(auto&u:p){
        int ok=0; for(auto&v:q)if(u.x==v.x){v.y+=u.y,ok=1;break;}
        if(ok) continue; q.pb(u); if(sz(q)<=pl) continue;
        int mn=n; for(auto&v:q) mn=min(mn,v.y);
        r.clear(); for(auto&v:q)if(v.y-mn) r.pb(mp(v.x,v.y-mn)); q=r; 
    }
    return q;
}
void down(int k,int l,int r){
    if(!mk[k]) return;
    fill(ca[k<<1],mk[k],mid-l+1),fill(ca[k<<1|1],mk[k],r-mid);
    mk[k<<1]=mk[k<<1|1]=mk[k],mk[k]=0;
}
void build(int k=1,int l=1,int r=n){
    if(l==r) return void(fill(ca[k],a[l],1));
    build(ls),build(rs),ca[k]=ca[k<<1]+ca[k<<1|1];
}
void fix(int x,int y,int z,int k=1,int l=1,int r=n){
    if(x<=l&&r<=y) return void((fill(ca[k],z,r-l+1),mk[k]=z)); down(k,l,r);
    if(mid>=x) fix(x,y,z,ls); if(mid<y) fix(x,y,z,rs);
    ca[k]=ca[k<<1]+ca[k<<1|1];
}
vpii query(int x,int y,int k=1,int l=1,int r=n){
    if(x<=l&&r<=y) return ca[k]; down(k,l,r);
    vpii res; if(mid>=x) res=res+query(x,y,ls); if(mid<y) res=res+query(x,y,rs);
    return res;
}
void Print(int k=1,int l=1,int r=n){ //调试用的，我这个蒟蒻，总是代码写挂
    printf("[%d,%d,%d]:mk=%d\n",k,l,r,mk[k]);
    for(auto&u:ca[k]) printf("(%d,%d)",u.x,u.y);puts("");
    if(l==r) return; down(k,l,r);
    Print(ls),Print(rs);
}

//Main
int main(){
    scanf("%d%d%d",&n,&m,&p),pl=100/p;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]); build();
    for(int i=1;i<=m;i++){
        int o; scanf("%d",&o);
        if(o==1){int l,r,id; scanf("%d%d%d",&l,&r,&id); fix(l,r,id);}
        else {
            int l,r; scanf("%d%d",&l,&r);
            vpii res=query(l,r); printf("%d",sz(res));
            for(auto&u:res) printf(" %d",u.x); puts("");
        }
//      puts("+++++");
//      Print();
//      puts("-----");
    }
    return 0;
}

祝大家学习愉快！