首先考虑暴力怎么做。
记 $c_i$ 表示 $[1,i]$ 都出现过的顾客数量，那么遇到 $x$ 这道菜的时候就执行 $c_x \leftarrow c_x - 1$，$c_{x+1} \leftarrow c_{x+1}+1$，要特判 $c_x \gt 0$。
然后“不难”注意到这类似于网络流。考虑把每道菜拆成出入点，那么每道菜内部容量为 $1$，对于上述这种关系将出点和后面的入点连边，容量 $\infty$，那么就转化为求最大流。
最大流不好刻画，所以将其表示为最小割。考虑设 $f_{i,j}$ 表示 $[1,i]$ 中上菜数量最多的顾客拥有 $[1,j)$ 的菜，注意右开。
转移方程：

$$f_{i,a_{i+1}} + 1 \to f_{i+1,a_{i+1}}$$
$$f_{i,a_{i+1}} \to f_{i+1,a_{i+1}+1}$$

由于有两个修改操作，考虑线段树维护。这就需要类似于 DDP 的矩阵乘法辅助转移。
矩阵是好推的，考虑当前加入数是 $x$，那么显然 $M(x,x)=1$，且 $M(x-1,x)=0$，其它和单位矩阵没有区别，注意是广义矩阵乘法。
由于二操作的存在，我们需要记录线段树上区间内 $[0,k)$ 所有的偏移量乘积矩阵。做完了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1.5e5 + 5, INF = 0x3f3f3f3f;

int n, k, m, a[N];

void sub_k1() {
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    while (m--) {
        int opt, l, r, v; scanf("%d", &opt);
        if (opt == 1) scanf("%d%d%d", &l, &r, &v);
        else if (opt == 2) scanf("%d%d", &l, &r);
        else scanf("%d%d", &l, &r), printf("%d\n", r - l + 1);
    }
}

struct Matrix {
    int a[7][7];
    void init() {   //全部设为正无穷
        for (int i = 1; i <= k; i++)
            for (int j = 1; j <= k; j++) a[i][j] = INF;
    }
    void init2() { init(); for (int i = 1; i <= k; i++) a[i][i] = 0; }
} Init;

Matrix mul(Matrix a, Matrix b) {
    Matrix res; res.init();
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            for (int l = 1; l <= k; l++)
                res.a[i][j] = min(res.a[i][j], a.a[i][l] + b.a[l][j]);
    return res;
}
void print(Matrix a) {
    for (int i = 1; i <= k; i++, puts(""))
        for (int j = 1; j <= k; j++) cout << a.a[i][j] << ' ';
}

Matrix Mat[7], qmi[7][N];  //对于每个 x 的固定转移矩阵、矩阵幂
void initMat() {    //求固定转移矩阵
    Init.init(); for (int i = 1; i <= k; i++) Init.a[1][i] = 0; //区间乘的初始矩阵
    for (int x = 1; x <= k; x++) {
        Mat[x].init2();
        Mat[x].a[x][x] = 1, Mat[x].a[x - 1][x] = 0;
    }
    for (int x = 1; x <= k; x++) {
        qmi[x][1] = Mat[x];
        for (int i = 2; i <= n; i++) qmi[x][i] = mul(qmi[x][i - 1], Mat[x]);
    }
}

struct Segment_Tree {
    int l, r;
    int add, cover; //两个懒标记
    Matrix prod[6]; //区间矩阵乘积
} tr[N << 2];
void pushup(int u) { for (int i = 0; i < k; i++) tr[u].prod[i] = mul(tr[u << 1].prod[i], tr[u << 1 | 1].prod[i]); }
void update_cover(int u, int d) {
    tr[u].cover = d, tr[u].add = 0;
    int len = tr[u].r - tr[u].l + 1;
    for (int i = d, j = 0; j < k; i = (i % k) + 1, j++) tr[u].prod[j] = qmi[i][len];
}
Matrix tt[7];
void update_add(int u, int d) {
    for (int i = 0; i < k; i++) tt[i] = tr[u].prod[i];
    tr[u].add += d;
    for (int i = 0; i < k; i++) tr[u].prod[i] = tt[(i + d) % k];
}
void pushdown(int u) {
    if (tr[u].cover) update_cover(u << 1, tr[u].cover), update_cover(u << 1 | 1, tr[u].cover), tr[u].cover = 0;
    if (tr[u].add) update_add(u << 1, tr[u].add), update_add(u << 1 | 1, tr[u].add), tr[u].add = 0;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        for (int i = a[l], j = 0; j < k; i = (i % k) + 1, j++) tr[u].prod[j] = Mat[i];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void change(int u, int l, int r) {   //区间加
    if (tr[u].l >= l && tr[u].r <= r) return update_add(u, 1), void();
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= mid) change(u << 1, l, r);
    if (r > mid) change(u << 1 | 1, l, r);
    pushup(u);
}
void cover(int u, int l, int r, int d) {    //区间覆盖
    if (tr[u].l >= l && tr[u].r <= r) return update_cover(u, d), void();
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= mid) cover(u << 1, l, r, d);
    if (r > mid) cover(u << 1 | 1, l, r, d);
    pushup(u);
}
Matrix query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].prod[0];
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (r <= mid) return query(u << 1, l, r);
    if (l > mid) return query(u << 1 | 1, l, r);
    return mul( query(u << 1, l, r), query(u << 1 | 1, l, r) );
}

int main() {
    scanf("%d%d", &n, &k);
    if (k == 1) return sub_k1(), 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    initMat(), build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int opt, l, r, v; scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%d", &l, &r, &v);
            cover(1, l, r, v);
        } else if (opt == 2) {
            scanf("%d%d", &l, &r);
            change(1, l, r);
        } else {
            scanf("%d%d", &l, &r);
            Matrix now = query(1, l, r);
            int Min = INF;
            for (int i = 1; i <= k; i++)
                for (int j = 1; j <= k; j++) Min = min(Min, now.a[i][j]);
            printf("%d\n", Min);
        }
    }
    return 0;
}