很有趣的一道题。
首先令 \(p \gets \lfloor\frac{p}{100}\rfloor\)，那么我们可以把问题转化成求出所有出现次数 \(\ge \frac{n}{p + 1}\) 的至多 \(p\) 个数。
考虑 \(p=1\) 的时候，发现这个问题就是一个主元素的问题，而区间主元素有经典的摩尔投票合并法。考虑将这个做法进行拓展。
考虑摩尔投票法的本质，实际上是每次将两个不相等的数配对删去，然后最后仅会剩下一个数。那么考虑直接拓展为每次将 \(p+1\) 个不相等的数删去，然后剩下至多 \(p\) 个数。
正确性：这样至多配对 \(\lfloor\frac{n}{p + 1}\rfloor\) 次，那么对于所有出现次数大于 \(\frac{n}{p}\) 的数，最坏情况下也会有剩余（\(\lfloor\frac{n}{p + 1}\rfloor \le \frac{n}{p}\)），所以这样一定能够留下所有出现次数大于 \(\frac{n}{p}\) 的数。那么直接线段树上维护这个过程就做完了。区间修改很容易实现。
我写的实现比较丑，精细实现一下能够做到 \(O(np \log n)\)，合并过程我直接无脑 \(O(p^2)\) 合并了，反正 \(p\le 5\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150005;
int n, m, p;
int a[MAXN];
struct SegmentTree {
struct Value {
int v[5], c[5];
};
struct Node {
Value val;
int tag, len;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void tag(int i, int x) {
t[i].val.v[0] = x, t[i].val.c[0] = t[i].len;
for (int j = 1; j < p; j++) {
t[i].val.v[j] = t[i].val.c[j] = 0;
}
t[i].tag = x;
}
void pushDown(int i) {
if (t[i].tag) {
tag(lc, t[i].tag);
tag(rc, t[i].tag);
t[i].tag = 0;
}
}
Value Merge(Value x, Value y) {
static int tmp[15], cnt[15], id[15];
Value z;
merge(x.v, x.v + p, y.v, y.v + p, tmp);
sort(tmp, tmp + 2 * p);
int o = unique(tmp, tmp + 2 * p) - tmp;
for (int i = 0; i < o; i++) {
id[i] = i, cnt[i] = 0;
}
for (int j = 0; j < p; j++) {
cnt[lower_bound(tmp, tmp + o, x.v[j]) - tmp] += x.c[j];
cnt[lower_bound(tmp, tmp + o, y.v[j]) - tmp] += y.c[j];
}
sort(id, id + o, [&](int x, int y) { return cnt[x] > cnt[y]; });
for (int i = o - 1; i >= p; i--) {
for (int j = i - p; j <= i; j++) {
cnt[id[j]] -= cnt[id[i]];
}
}
for (int j = 0; j < p; j++) {
if (j < o) {
z.v[j] = tmp[id[j]];
z.c[j] = cnt[id[j]];
} else {
z.v[j] = z.c[j] = 0;
}
}
return z;
}
void pushUp(int i) {
t[i].val = Merge(t[lc].val, t[rc].val);
}
void build(int i = 1, int l = 1, int r = n) {
t[i].len = r - l + 1;
if (l == r) {
t[i].val.v[0] = a[l], t[i].val.c[0] = 1;
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
pushUp(i);
}
void update(int a, int b, int v, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) {
tag(i, v);
return;
}
int mid = (l + r) >> 1;
pushDown(i);
if (a <= mid) update(a, b, v, lc, l, mid);
if (b > mid) update(a, b, v, rc, mid + 1, r);
pushUp(i);
}
Value query(int a, int b, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) return t[i].val;
int mid = (l + r) >> 1;
pushDown(i);
if (b <= mid) return query(a, b, lc, l, mid);
if (a > mid) return query(a, b, rc, mid + 1, r);
return Merge(query(a, b, lc, l, mid), query(a, b, rc, mid + 1, r));
}
} st;
int main() {
scanf("%d%d%d", &n, &m, &p);
p = 100 / p;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
st.build();
while (m--) {
int op, l, r; scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
int v; scanf("%d", &v);
st.update(l, r, v);
} else {
auto val = st.query(l, r);
printf("%d ", p);
for (int i = 0; i < p; i++) {
printf("%d ", val.v[i]);
}
printf("\n");
}
}
return 0;
}