# Problem : Bó Hoa Tối Thiểu, Tình Cảm Tối Đa
* **Time limit per Test : 3 second.**
* **Memory limit per test : 1024 megabytes.**
* **Rating : 2000.**

Ở Khánh Hòa – xứ Trầm Hương, nắng mặn gió biển, sóng Nha Trang vỗ bờ như máy metronome có chàng trai tên **Hưng** – tuyển thủ bida hệ "đánh một quên mười". Tốc độ đời thường của Hưng chầm chậm như tàu gỗ dạo vịnh, nhưng trái tim thì nồng như nắng trưa Hòn Chồng. Đáng tiếc, Hưng đã phạm tội "thiên cổ": quên kỷ niệm 1 năm với **Hoàng Châu** vì đang mãi trong cơn mê với "cú đánh bi số 8 thần sầu". Kết quả? Tin nhắn từ người yêu vỏn vẹn ba chữ: "Chia tay đi". Để dỗ dành, Hưng quyết tặng một bó hoa tuyệt mỹ nhưng vì ví mỏng như tờ vé xe buýt Cam Ranh, nên **mục tiêu là mua 1 bó hoa gồm ít bông nhất nhưng vẫn phải thỏa chuẩn “Châu-approved”**.

Con phố bán hoa giữa lòng Nha Trang có **$N$ cửa hàng đứng liên tiếp**, **mỗi nơi chỉ bán đúng một loại hoa $A_i$ ($1 \le A_i \le K$)**. Ngỡ đâu êm đềm như biển yên, nào ngờ đời đẩy độ khó lên bằng dòng thời gian gồm **$Q$ thời điểm** : mỗi thời điểm **Hưng** sẽ nhận được $1$ trong $2$ loại tin nhắn sau :
- Tin nhắn loại $1$ có dạng $1$ $p$ $v$ ($1 \le p \le N$ ; $1 \le v \le K$): **Cửa hàng $p$ đổi sang bán loại hoa $v$**.
- Tin nhắn loại $2$ có dạng $2$ $L$ $R$ ($1 \le L \le R \le N$ : **Chuẩn "Châu-approved"** lúc này là :
- Chỉ được **chọn một dãy cửa hàng liên tiếp** $[U,V]$ để mua hoa sao cho **$L \le U \le V \le R$**.
- Mỗi cửa hàng trong dãy $[U,V]$ **phải mua ít nhất 1 bông hoa.**
- Bó hoa hợp lệ khi **có đủ mọi loại hoa từ $1$ đến $K$**.

Vì tính tình chậm chạp (và một trái tim nóng muốn làm lành ngay), Hưng đành nhờ bạn - người có tốc độ vượt gió Nam, với mỗi tin nhắn loại 2, hãy giúp Hưng mua 1 bó hoa đúng chuẩn **"Châu-approved"** lúc này nhưng cũng phải ít bông nhất.
## Input
- Dòng $1$ : ba số nguyên $N, K, Q$ ( $1 \le N, Q \le 10^5$ ; $1 \le K \le 50$ ).
- Dòng $2$ : $N$ số nguyên dương $A_i$ ( $1 \le i \le N$ ; $1 \le A_i \le K$ ).
- Mỗi dòng trong $Q$ dòng tiếp theo gồm một trong $2$ loại tin nhắn trên.
## Output
- Ứng với mỗi tin nhắn loại $2$ theo trình tự trong $Q$ thời điểm : in ra kết quả trên mỗi dòng, nếu không có kết quả in ra $-1$.
## Ví dụ
### Input :

8 3 8
2 1 2 3 2 1 1 2
2 1 5
2 3 7
1 6 3
2 5 8
1 2 2
2 1 3
2 1 8
1 7 2

### Output :

3
3
3
-1
3

## Subtask
- Subtask $1$ : $30$% số điểm thỏa mãn : $1 \le N, Q \le 5000$.
- Subtask $2$ : $70$% số điểm thỏa mãn : $5000 < N, Q \le 10^5$.

## Lời Giải
### Tóm tắt bài toán :
Bạn có mảng $A$ gồm $N$ phần tử, mỗi $A_i$ nằm trong khoảng $[1,K]$.
Có $Q$ truy vấn, xử lí theo đúng thứ tự gồm hai loại truy vấn:
- **Cập nhật :** $1$ $p$ $v$ $->$ gán $A_p=v$ ($1 \le p \le N$ ; $1 \le v \le K$).
- **Hỏi đoạn :** $2$ $L$ $R$ $->$ trong đoạn $[L, R]$, tìm dãy con liên tiếp ngắn nhất $[U,V]$ với ( $L \le U \le V \le R$ ) sao cho mọi giá trị từ $1$ đến $K$ đều xuất hiện trong $A[U..V]$.
- Nếu tồn tại : In độ dài $V-U+1$.
- Nếu không tồn tại : In $-1$.
### Subtask $1$ : $1 \le N, Q \le 5000$.
---
#### Ý tưởng :
Cập nhật loại $1$ chỉ là gán $A_p=v$, sau đó các truy vấn sau làm trên mảng mới.
Vì $N,Q$ còn nhỏ ta xử lý mỗi truy vấn loại $2$ bằng hai con trỏ trực tiếp trên đoạn $[L,R]$:
- Dùng hai con trỏ (sliding window) và mảng đếm :
- $cnt[x]$ : số lần loại $x$ xuất hiện trong cửa sổ hiện tại.
- $have$ : số loại đang có trong cửa sổ ($cnt[x]>0$).
- Bất biến : cửa sổ luôn là đoạn $[l,r]$ với $L \le l \le r \le R$.
- **Thao tác :**
- Tăng $r$ từ $L$ đến $R$, mỗi lần thêm $A_r$ vào $cnt$. Nếu $cnt[A_r]$ tăng từ $0$ lên $1$ thì $have=have+1$.
- Khi $have==K$ (đã đủ loại), cố gắng co trái: lặp $while(have==K)$
- Cập nhật $ans=min(ans,r-l+1)$.
- Bớt $cnt[A_l]$; nếu về $0$ thì $have=have-1$.
- tăng $l=l+1$.
#### Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    const int INF = 1e9;

    auto solveQuery = [&](int L, int R) -> int {
        if (R - L + 1 < K) return -1;              
        vector<int> cnt(K + 1, 0);
        int have = 0;                               
        int ans = INF;
        int l = L;

        for (int r = L; r <= R; ++r) {
            int x = A[r];
            if (++cnt[x] == 1) ++have;

            while (have == K) {                     
                ans = min(ans, r - l + 1);
                int y = A[l];
                if (--cnt[y] == 0) --have;
                ++l;
            }
        }
        return (ans == INF ? -1 : ans);
    };

    for (int qi = 0; qi < Q; ++qi) {
        int type; cin >> type;
        if (type == 1) {
            int p, v; cin >> p >> v;
            A[p] = v;                               
        } else if (type == 2) {
            int L, R; cin >> L >> R;
            cout << solveQuery(L, R) << '\n';       
        }
    }
    return 0;
}

Độ phức tạp : $O(Q*N)$.
Bộ nhớ : $O(K)$

### Subtask $2$ : $5000 < N, Q \le 10^5$.
#### Vì sao cách ở Subtask $1$ không đủ ?
Ở subtask $1$, mỗi truy vấn loại 2 ta quét được (sliding window) trực tiếp trên đoạn $[L,R]$. Với $Q$ tới $10^5$ thì $O(R-L)$ mỗi truy vấn sẽ quá chậm, chưa kể còn có truy vấn cập nhật (đổi $A_p=v$) làm mọi tiền xử lí hỏng hết.
#### Ý tưởng :
DP trên Segment tree, coi mỗi node con của Segment Tree chính là một “trạng thái con” và được ghép lại bằng quy hoạch động. Mỗi node đại diện một đoạn và lưu 3 thứ :
- $best$ - độ dài ngắn nhất của một đoạn con trong node hiện tại chứa đủ tất cả $K$ loại (nếu chưa có thì $+\infty$).
- $pref$ - một danh sách các "$mask$ $OR$ tiền tố" theo biên trái -> phải.
Phần tử là $(mask,pos)$ nghĩa là nếu ta đi từ biên trái của node đến $pos$ thì $OR$ các loại nhận được chính là $mask$.
Danh sách chỉ lưu khi $mask$ thay đổi (mỗi lần thêm là phải bật thêm $\geq 1$ bit mới), nên kích thước tối đa $\le K$.
- $suff$ - tương tự như $pref$ nhưng là một danh sách các "$mask$ $OR$ hậu tố" theo biên phải -> trái : $(mask,pos)$ nghĩa là từ $pos$ đến biên phải $OR$ được $mask$. Cũng có có kích thước $\le K$.
- Vì $K\le 50$, ta có thể lưu $mask$ bằng $64-bit$ (unsigned long long).

Hợp hai node con ($merge$) :
- $best = min(LEFT.best,RIGHT.best)$ (đáp án nằm hoàn toàn bên bên trong node trái hoặc phải).
- $pref$ : bắt đầu bằng $LEFT.pref$, rồi ghép thêm với từng phần tử của $RIGHT.pref$ (mỗi lần $OR$ với $pref.back()$.mask$, nếu có bit mới thì đẩy vào).
- $suff$ : bắt đầu bằng $RIGHT.suff$, rồi ghép thêm với từng phần tử của $LEFT.suff$ như tháo tác của $pref$.
- Đoạn bắc cầu (cắt qua ranh giới của hai node):
- Dùng hai con trỏ trên $LEFT.suff$ (đi từ cuối về đầu) và $RIGHT.pref$ (đi từ đầu về cuối).
- Gọi $FULL = (1LL<<K)-1$.
- Với mỗi $RIGHT.pref_i.mask$, lùi con trỏ $j$ cho tới khi $(LEFT.suff_(j-1).mask$ $|$ $RIGHT.pref_i.mask)$ không còn $= FULL$ thì dừng. Nếu $LEFT.suff_j.mask | RIGHT.pref_i.mask == FULL$ thì cập nhật $best = min(best, RIGHT.pref_i.pos - LEFT.suff_j.pos + 1)$.
- Độ phức tạp của $merge$ là $O(K)$.

Cập nhật & truy vấn :
- Cập nhật một lá : gán lại $pref,suf$ với $mask$ của loại mới, $best=1$ nếu $K=1$, ngược lại $+\infty$. Rồi dồn lên trên bằng $merge$. Chi phí $O(K * log(N))$.
- Truy vấn $[L,R]$ : lấy các $node$ che phủ, $merge$ dần để được $node$ kết quả, in $best$ hoặc $-1$ nếu là $+\infty$. Chi phí $O(K * log(N))$.

#### CODE

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long U64;

const int MAXN = 100000 + 5;
const int KMAX = 64;
const int MAXSZ = 1 << 18;
const int INF32 = 1000000007;

int n, k, q;
int a[MAXN];
U64 FULLMASK;
U64 VALMASK[64];

struct Pair64 { U64 m; int p; };

struct Node {
    int ans, lsz, rsz;
    Pair64 L[KMAX], R[KMAX];
    Node(): ans(INF32), lsz(0), rsz(0) {}
};

Node st[MAXSZ];
int SZ;

inline bool isEmpty(const Node& x){ return x.lsz==0; }

inline void pushCompressL(Node& res, U64 m, int p){
    if(res.lsz==0){ res.L[0].m=m; res.L[0].p=p; res.lsz=1; return; }
    U64 nm = (res.L[res.lsz-1].m | m);
    if(nm!=res.L[res.lsz-1].m){ res.L[res.lsz].m=nm; res.L[res.lsz].p=p; ++res.lsz; }
}

inline void pushCompressR(Node& res, U64 m, int p){
    if(res.rsz==0){ res.R[0].m=m; res.R[0].p=p; res.rsz=1; return; }
    U64 nm = (res.R[res.rsz-1].m | m);
    if(nm!=res.R[res.rsz-1].m){ res.R[res.rsz].m=nm; res.R[res.rsz].p=p; ++res.rsz; }
}

inline Node make_leaf(int pos, int val){
    Node t;
    U64 m = VALMASK[val];
    t.L[0].m=m; t.L[0].p=pos; t.lsz=1;
    t.R[0].m=m; t.R[0].p=pos; t.rsz=1;
    t.ans = (k==1?1:INF32);
    return t;
}

inline Node Merge(const Node& A, const Node& B){
    if(isEmpty(A)) return B;
    if(isEmpty(B)) return A;
    Node res;
    res.ans = (A.ans<B.ans?A.ans:B.ans);
    res.lsz=0;
    for(int i=0;i<A.lsz;++i){ res.L[res.lsz]=A.L[i]; ++res.lsz; }
    for(int i=0;i<B.lsz;++i){ pushCompressL(res,B.L[i].m,B.L[i].p); }
    res.rsz=0;
    for(int i=0;i<B.rsz;++i){ res.R[res.rsz]=B.R[i]; ++res.rsz; }
    for(int i=0;i<A.rsz;++i){ pushCompressR(res,A.R[i].m,A.R[i].p); }
    if(A.rsz>0 && B.lsz>0){
        int j=A.rsz-1;
        for(int i=0;i<B.lsz;++i){
            while(j>0 && ((A.R[j-1].m | B.L[i].m)==FULLMASK)) --j;
            if((A.R[j].m | B.L[i].m)==FULLMASK){
                int len = B.L[i].p - A.R[j].p + 1;
                if(len<res.ans) res.ans=len;
            }
        }
    }
    return res;
}

inline void seg_init(int n_){
    SZ=1; while(SZ<n_) SZ<<=1;
    for(int i=1;i<(SZ<<1);++i) st[i]=Node();
}

inline void seg_build(int n_){
    for(int i=0;i<n_;++i) st[SZ+i]=make_leaf(i+1,a[i+1]);
    for(int i=SZ-1;i>=1;--i) st[i]=Merge(st[i<<1],st[i<<1|1]);
}

inline void seg_update(int pos){
    int p=SZ+(pos-1);
    st[p]=make_leaf(pos,a[pos]);
    p>>=1;
    while(p>=1){ st[p]=Merge(st[p<<1],st[p<<1|1]); p>>=1; }
}

inline Node seg_query(int L,int R){
    int l=SZ+(L-1), r=SZ+(R-1);
    Node leftRes, rightRes;
    while(l<=r){
        if(l&1){ leftRes=Merge(leftRes,st[l]); ++l; }
        if((r&1)==0){ rightRes=Merge(st[r],rightRes); --r; }
        l>>=1; r>>=1;
    }
    return Merge(leftRes,rightRes);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    FULLMASK = (k>=64)?~0ULL:((1ULL<<k)-1ULL);
    for(int v=1;v<=k && v<=63;++v) VALMASK[v]=(1ULL<<(v-1));
    seg_init(n);
    seg_build(n);
    for(int i=1;i<=q;++i){
        int type; cin>>type;
        if(type==2){
            int L,R; cin>>L>>R;
            Node res = seg_query(L,R);
            cout<<(res.ans>=INF32?-1:res.ans)<<"\n";
        }else{
            int pos,val; cin>>pos>>val;
            a[pos]=val;
            seg_update(pos);
        }
    }
    return 0;
}

#### Độ phức tạp :
Xây cây : $O(N*K*log(N))$.
Mỗi lần update : $O(K * log(N))$.
Mỗi lần query $[L,R]$ : $O(K * log(N))$.
Tổng thời gian cho $Q$ thao tác : $O(N*K*log(N)+Q*K*log(N))$.

--------