思路
先考虑一下 \(p > 50\) 的情况
这时候就是求“绝对众数”
一个方法就是用“摩尔投票”法
方法就是：每次将不同的两个数去掉，剩下的那种数就是绝对众数（这是保证在有的情况下，才能求出正确的众数）
再考虑 \(20\le p \le 50\) 时，其实我们可以维护 \(\lfloor\frac{p}{100}\rfloor\) 个这样的数
当新增一个数时，我们与维护的数进行比较：如果维护的数有与新增的数相同的，就将这种数的“个数”＋1；否则，我们就所有维护的数的“个数”都减一，如果出现 \(-1\) 的，就用新增的数替代它
有区间赋值和询问，采用线段树维护即可
有个辣鸡因为把一个 \(i\) 打成 \(j\) 导致调了接近一个下午，我不说是谁
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int reads()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, p; int cnt;
struct Node
{
int val[6], cnt[6], num; bool tag;
}tr[600005];
#define ls (now << 1)
#define rs ((now << 1) | 1)
inline void down(int now, int l, int r)
{
if(tr[now].tag)
{
int mid = (l + r) >> 1;
tr[ls].tag = tr[rs].tag = 1;
tr[ls].num = tr[rs].num = 1;
tr[ls].val[1] = tr[rs].val[1] = tr[now].val[1];
tr[ls].cnt[1] = mid - l + 1, tr[rs].cnt[1] = r - mid;
tr[now].tag = 0;
}
}
inline Node merge(Node a, Node b)
{
FOR(i, 1, a.num)
{
bool same = 0;
FOR(j, 1, b.num)
if(a.val[i] == b.val[j])
{
b.cnt[j] += a.cnt[i];
same = 1;
break;
}
if(same) continue;
if(b.num < p)
{
++b.num,
b.val[b.num] = a.val[i],
b.cnt[b.num] = a.cnt[i];
continue;
}
int id = 1;
FOR(j, 2, b.num)
if(b.cnt[j] < b.cnt[id]) id = j;
if(b.cnt[id] < a.cnt[i])
std::swap(a.val[i], b.val[id]), std::swap(a.cnt[i], b.cnt[id]);
FOR(j, 1, b.num)
b.cnt[j] -= a.cnt[i];
}
b.tag = 0;
return b;
}
void build(int now, int l, int r)
{
if(l == r)
{
tr[now].val[1] = reads();
tr[now].num = tr[now].cnt[1] = 1;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
tr[now] = merge(tr[ls], tr[rs]);
}
void modify(int now, int l, int r, int L, int R, int val)
{
if(L <= l && r <= R)
{
tr[now].val[1] = val;
tr[now].num = 1;
tr[now].cnt[1] = r - l + 1;
tr[now].tag = 1;
return;
}
down(now, l, r);
int mid = (l + r) >> 1;
if(L <= mid) modify(ls, l, mid, L, R, val);
if(mid < R) modify(rs, mid + 1, r, L, R, val);
tr[now] = merge(tr[ls], tr[rs]);
}
Node query(int now, int l, int r, int L, int R)
{
if(L <= l && r <= R) return tr[now];
down(now, l, r);
int mid = (l + r) >> 1;
if(R <= mid) return query(ls, l, mid, L, R);
if(mid < L) return query(rs, mid + 1, r, L, R);
return merge(query(ls, l, mid, L, R), query(rs, mid + 1, r, L, R));
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = reads(), m = reads(), p = reads(), p = 100 / p;
build(1, 1, n);
FOR(i, 1, m)
{
int ty = reads(), l = reads(), r = reads();
if(ty == 1)
{
int val = reads();
modify(1, 1, n, l, r, val);
}
else
{
cnt++;
Node ans = query(1, 1, n, l, r);
printf("%d ", ans.num);
FOR(j, 1, ans.num) printf("%d ", ans.val[j]);
puts("");
}
}
return 0;
}