题意

有一个 $n$ 个数的序列，每个数都在 $[1,k]$ 范围内，有 $m$ 次操作，有以下操作。

• 1 l r v，把区间 $[l,r]$ 的数字覆盖成 $v$。
• 2 l r，把区间 $[l,r]$ 的数字加 $1$，如果有数字大于 $k$，这些数字变成 $1$，也就是 $a_i \gets a_i \bmod k + 1$。
• 3 l r，查询区间 $[l,r]$，查询的值如下。

每次按照顺序从左往右取出数字 $[1,k]$，取数字要从小到大。问最多可以操作几次？

注意，一定要按数字从小到大，比如序列 $2,1,3$ 是无法取出的。

分析

我们先考虑询问怎么做。很明显我并不会。

如果直接 $O(nm)$ 暴力的话，我们可以考虑直接依次扫过去，定义 $s_x$ 表示之前可以取出 $[1,x]$ 的方案数。如果当前的数字是 $V$，我们可以直接 $s_{V-1} \gets s_{V-1}-1,s_V \gets s_V+1$。

但是这样子做我们不好使用诡异数据结构维护。我们考虑转化题意。题目要让我们取出若干个 $[1,k]$ 的子序列。这个形式很网络流。

一开始考虑的是为一个点 $i$ 往后面所有 $a_j = a_i + 1$ 的 $j$ 连边，流量为 $1$，然后超级源点 $S$ 向所有 $a_i = 1$ 的连流量为 $1$ 的边，所有 $a_i = k$ 向超级汇点 $T$ 连流量为 $1$ 的边。但是后来发现，我们这样子就会有一个点重复用的情况。经典的，我们把一个点拆成入点和出点，入点向出点连流量为 $1$ 的点，进来的边都连上入点，出去的边都连上出点。这样子我们就可以每个点只选一次了。

这个问题就很 dp 了。我们定义 $f_{i,j}$ 表示前 $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}$$

其余的直接拿过来，不用修改。

这个式子就是最大流转化成最小割，考虑的就是当前点是否割掉。

这个式子就是经典的动态 dp 了。具体的，我们知道这个 dp 的转移一定可以表示成矩阵乘法。每个点的转移方式只取决于 $a_i$ 的值。我们考虑用矩阵表示转移。然后直接矩阵乘法。根据结合律，我们可以线段树维护区间矩阵积。这一部分就可以做完了。

矩阵的构造也是简单的。设 $x = a_{i+1}$。首先明确我们用的是广义矩阵乘法，也就是 $C_{i,j} = \min A_{i,k} + B_{k,j}$。所有直接拿过来的，就是对角线全都是 $0$。但是特殊的是 $(x,x)$，因为 $f_{i,x} + 1 \to f_{i+1,x}$，所以 $(x,x)$ 是 $1$，并且我们考虑 $f_{i,x} \to f_{i+1,x+1}$。所以 $(x,x+1)$ 是 $0$。

似乎做完了。

吗？

我们似乎还剩下了一些修改。如果只是单点修改是简单的，但是这题是诡异区间修改。

首先是区间推平。如果一段区间的 $a_i$ 都是 $V$，那么所有矩阵就是相同的，并且积就是矩阵的 $r - l + 1$ 次方。这个是容易的。

然后是区间加。我们发现不好直接做，但是我们发现了一种好玩的做法，就是每个节点直接存 $+0,+1,+2,+3,+4$ 的答案，每个值都是好维护的，区间加就是直接交换顺序即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 150005
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, k, a[N], op, l, r;

struct Mat{
    int a[7][7];
    auto& operator [](const int& x){return a[x];}
}INF, M[7], E, Mt[7][N];
Mat operator * (Mat a, Mat b){
    Mat ans = INF;
    for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) for (int t = 0; t < k; t++)
        ans[i][j] = min(ans[i][j], a[i][t] + b[t][j]);
    return ans;
}
il int getmin(Mat x){
    int ans = 1e9;
    for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) ans = min(ans, x[i][j]);
    return ans;
}
// Mat

struct ST{
    Mat m[7];
    auto& operator [](const int& x){return m[x];}
}tr[N << 2];
int tag_cover[N << 2], tag_add[N << 2];
ST operator + (ST x, ST y){
    ST ans;
    for (int i = 0; i < k; i++) ans[i] = x[i] * y[i];
    return ans;
}
il void upd_cover(int p, int l, int r, int v){
    for (int i = 0; i < k; i++) tr[p][i] = Mt[(v + i) % k][r - l + 1];
    tag_add[p] = 0, tag_cover[p] = v;
}
il void upd_add(int p, int l, int r, int v){
    ST ans;
    for (int i = 0; i < k; i++) ans[i] = tr[p][(v + i) % k];
    tr[p] = ans, tag_add[p] = (tag_add[p] + v) % k;
}

il void pd(int p, int l, int r){
    int mid = (l + r) >> 1;
    if (tag_cover[p] != -1) upd_cover(p << 1, l, mid, tag_cover[p]), upd_cover(p << 1 | 1, mid + 1, r, tag_cover[p]), tag_cover[p] = -1;
    if (tag_add[p]) upd_add(p << 1, l, mid, tag_add[p]), upd_add(p << 1 | 1, mid + 1, r, tag_add[p]), tag_add[p] = 0;
}
void build(int p, int l, int r){
    tag_cover[p] = -1;
    if (l == r){
        for (int i = 0; i < k; i++) tr[p][i] = M[(a[l] + i) % k];
        return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
void cover(int p, int l, int r, int nl, int nr, int v){
    if (nl <= l && r <= nr) return upd_cover(p, l, r, v), void(0);
    int mid = (l + r) >> 1;
    pd(p, l, r);
    if (nl <= mid) cover(p << 1, l, mid, nl, nr, v);
    if (nr > mid) cover(p << 1 | 1, mid + 1, r, nl, nr, v);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
void add(int p, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return upd_add(p, l, r, 1), void(0);
    int mid = (l + r) >> 1;
    pd(p, l, r);
    if (nl <= mid) add(p << 1, l, mid, nl, nr);
    if (nr > mid) add(p << 1 | 1, mid + 1, r, nl, nr);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
Mat query(int p, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[p][0];
    int mid = (l + r) >> 1;
    pd(p, l, r);
    if (nl <= mid && nr > mid) return query(p << 1, l, mid, nl, nr) * query(p << 1 | 1, mid + 1, r, nl, nr);
    if (nl <= mid) return query(p << 1, l, mid, nl, nr);
    return query(p << 1 | 1, mid + 1, r, nl, nr);
}
// Segment_Tree

int main(){
    n = rd(), k = rd();
    for (int i = 1; i <= n; i++) a[i] = rd() - 1;
    for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) INF[i][j] = 1e9;
    E = INF;
    for (int i = 0; i < k; i++) E[0][i] = 0;
    for (int p = 0; p < k; p++){
        M[p] = INF;
        for (int i = 0; i < k; i++) M[p][i][i] = 0;
        M[p][p][p] = 1, M[p][p][p + 1] = 0;
        Mt[p][1] = M[p];
        for (int i = 2; i <= n; i++) Mt[p][i] = Mt[p][i - 1] * M[p];
    }
    build(1, 1, n);
    for (int T = rd(); T--;){
        op = rd(), l = rd(), r = rd();
        if (op == 1) cover(1, 1, n, l, r, rd() - 1);
        else if (op == 2) add(1, 1, n, l, r);
        else{
            Mat f = E * query(1, 1, n, l, r);
            printf ("%d\n", getmin(f));
        }
    }
    return 0;
}