# tioj 1169 氣球博覽會

https://tioj.ck.tp.edu.tw/problems/1169

* 開$2^c$棵動態開點線段樹，每個代表區間不包含某顏色的最長長度
* 線段樹節點存從左邊，從右邊以及全部的最長不包含某顏色的長度，跟區間最大連續和一樣
* 如果某節點是nullptr，代表全部都不包含那個顏色

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
using namespace std;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef long long ll;

struct dat{
    ll pre=0;
    ll suf=0;
    ll mx=0;
};

struct tree{
    dat d;
    tree *left=nullptr;
    tree *right=nullptr;
}*root[(1<<24)+10];

tree* upd(tree *node, int l, int r, ll pos, int x){
    if(node==nullptr) node=new tree;
    if(l==r){
        node->d.pre=x;
        node->d.suf=x;
        node->d.mx=x;
        return node;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) node->left=upd(node->left, l, mid, pos, x);
    else node->right=upd(node->right, mid+1, r, pos, x);

    dat a, b;
    if(node->left==nullptr) a={mid-l+1, mid-l+1, mid-l+1};
    else a=node->left->d;
    if(node->right==nullptr) b={r-mid, r-mid, r-mid};
    else b=node->right->d;
    node->d.mx=max(max(a.mx, b.mx), a.suf+b.pre);
    if(a.pre==mid-l+1) node->d.pre=a.pre+b.pre;
    else node->d.pre=a.pre;
    if(b.suf==r-mid) node->d.suf=a.suf+b.suf;
    else node->d.suf=b.suf;

    return node;
}

dat get(tree *node, int l, int r, int ql, int qr){
    if(ql<=l && qr>=r){
        if(node==nullptr) return {r-l+1, r-l+1, r-l+1};
        return node->d;
    }
    int mid=(l+r)>>1;
    if(qr<=mid) return get(node?node->left:nullptr, l, mid, ql, qr);
    else if(ql>mid) return get(node?node->right:nullptr, mid+1, r, ql, qr);
    else{
        dat a, b, res;
        a=get(node?node->left:nullptr, l, mid, ql, mid);
        b=get(node?node->right:nullptr, mid+1, r, mid+1, qr);
        res.mx=max(max(a.mx, b.mx), a.suf+b.pre);
        if(a.pre==mid-l+1) res.pre=a.pre+b.pre;
        else res.pre=a.pre;
        if(b.suf==r-mid) res.suf=a.suf+b.suf;
        else res.suf=b.suf;
        return res;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, q, c;
    cin>>n>>q>>c;
    ll k;
    vector<ll> num(n);
    rep(i,0,n){
        cin>>k;
        num[i]=k;
        root[k]=upd(root[k], 0, n-1, i, 0);
    }
    rep(i,0,q){
        int a;
        cin>>a;
        if(a==1){
            ll x, y, k;
            cin>>x>>y>>k;
            cout<<get(root[k], 0, n-1, x, y-1).mx<<NL;
        }
        else{
            ll p, k;
            cin>>p>>k;
            root[num[p]]=upd(root[num[p]], 0, n-1, p, 1);
            num[p]=k;
            root[k]=upd(root[k], 0, n-1, p, 0);
        }
    }
}