Problem

Description

给定一个长度为$n$的序列和一个整数 $p$。

有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p$% 的数。

输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过$[\frac{100}{p}]$（下取整）

Input

第一行$n$，$m$，$p$。

接下来$m$行是询问包含$opt$，$l$，$r$，$a$（可无）。

如果$opt=1$表示区间$[l,r]$赋值为$a$

如果$opt=2$表示询问$[l,r]$

Output

对每一个$opt=2$，先输出个数，再输出具体数字

Sample Input

Sample Output

3 1 2 3
2 1 3
2 2 1
3 1 1000 1000
1 5
2 5 3
2 1 5

HINT

$n,m \leq 1.5\times 10^3$

$20 \leq p \leq 100$

Solution

Analysis

考虑$p>50$时，我们采用绝对众数投票法获得答案

同理，如果$p\leq50$我们可以统计一部分可能的众数来获得答案

保留的名单个数应该为$\frac{100}{q}$

Attention

可用重载运算符减小代码数量

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il void filejudge(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
const int N=150100;
#define ls (o<<1)
#define rs ((o<<1)|1)
int n,m,p;
struct node{
    int num[8],sum[8],tag,len;
    il node operator +(const node & other) const{
        node res=other;
        res.tag=0;
        rep(i,1,len){
            bool f=0;
            rep(j,1,res.len)
                if(num[i]==res.num[j]){
                    res.sum[j]+=sum[i];
                    f=1;
                }
            if(f) continue;
            if(res.len<p){
                res.len++;
                res.num[res.len]=num[i];
                res.sum[res.len]=sum[i];
            }else{
                int mn=INT_MAX,pos=0;
                rep(j,1,res.len) if(res.sum[j]<mn){ mn=res.sum[j];pos=j;}
                if(res.sum[pos]>sum[i])
                    rep(j,1,res.len)  res.sum[j]-=sum[i];
                else{
                    int k=res.sum[pos];
                    rep(j,1,res.len) res.sum[j]-=k;
                    res.sum[pos]=sum[i]-k;
                    res.num[pos]=num[i];
                    int lst=0;
                    rep(j,1,res.len)
                        if(res.sum[j]>0){
                            lst++;
                            res.num[lst]=res.num[j];
                            res.sum[lst]=res.sum[j];
                        }
                    res.len=lst;
                }
            }
        }
        return res;
    }
} t[N<<2];
int a[N];
il void up(int o){ t[o]=t[ls]+t[rs];}
il void down(int o,int oo,int sum){
    t[oo].tag=t[o].tag;
    t[oo].len=1;
    t[oo].num[1]=t[o].tag;
    t[oo].sum[1]=sum;
}
il void pushdown(int o,int l,int r){
    if(!t[o].tag) return;
    int mid=(l+r)>>1;
    down(o,ls,mid-l+1);
    down(o,rs,r-mid);
    t[o].tag=0;
}
il void make(int o,int l,int r,int addv){
    t[o].tag=addv;
    t[o].len=1;
    t[o].num[1]=addv;
    t[o].sum[1]=r-l+1;
}
il void update(int o,int l,int r,int L,int R,int addv){
    if(l>=L && r<=R){ make(o,l,r,addv);return;}
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) update(ls,l,mid,L,R,addv);
    if(R>mid) update(rs,mid+1,r,L,R,addv);
    up(o);
}
il node query(int o,int l,int r,int L,int R){
    if(l>=L && r<=R) return t[o];
    pushdown(o,l,r);
    int mid=(l+r)>>1;
    if(L<=mid && R>mid) return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
    if(L<=mid) return query(ls,l,mid,L,R);
    if(R>mid) return query(rs,mid+1,r,L,R);
}
il void build(int o,int l,int r){
    if(l==r){ make(o,l,r,a[l]);return;}
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(o);
}
int main(){
    n=read();m=read();p=read();p=100/p;
    rep(i,1,n) a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            int addv=read();
            update(1,1,n,l,r,addv);
        }else{
            node ans=query(1,1,n,l,r);
            printf("%d ",ans.len);
            rep(i,1,ans.len) printf("%d ",ans.num[i]);
            puts("");
        }
    }
    return 0;
}

太菜了，码力不足，写了1h

CF643G Choosing Ads