这个做法与 \(k\) 无关。
非常好常数，爱来自 Hanghang。
Hanghang 给出了一个空间 \(O(n)\)，常数很小，代码很短的单侧递归做法。
我们考虑维护哪些区间是不符合要求的，对于一个数 \(a_x\)，下一个 \(a_x\) 下标是 \(d_x\)，则满足 \(x<l\le r<d_x\) 的区间 \((l,r)\) 是不符合要求的。
然后我们将 \((i,d_i)\) 画在二维平面上，则我们发现限制形如：
红色的是限制，表示我们不能选这个三角形内部的点，除此之外的点都可以选取，我们需要令 \(r-l+1\) 最小。
我们观察后得到，我们的答案只可能存在于蓝色部分的点，即 \(d_i\) 的前缀最大值之处。
然后我们拿一颗线段树维护，需要左区间的 \(\max\)，和当前的下标，这个你发现可以单侧递归维护。
然后就做完了， \(O(n\log n+m\log^2 n)\)，常数很小。
代码中 res 维护的左边对于右边贡献得到的答案，然后 ans 表示这个区间的答案。
常数很小，目前是最优解。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=0x3f3f3f3f;
int n,m,q,a[N],d[N];
set<int>S[N];
multiset<int>E;
namespace ST{#define k1 (k<<1)#define k2 (k<<1|1)#define mid ((l+r)>>1)#define ls k1,l,mid#define rs k2,mid+1,rint mx[N<<2],ans[N<<2],res[N<<2];inline int calc(int v,int k,int l,int r){if(mx[k]<v||v==n+1) return INF;if(l==r) return v-l+1;if(v<mx[k1]) return min(res[k],calc(v,ls));else return calc(v,rs);}inline void up(int k,int l,int r){mx[k]=max(mx[k1],mx[k2]),ans[k]=min(ans[k1],res[k]=calc(mx[k1],rs));}inline void build(int k=1,int l=0,int r=n){if(l==r) return mx[k]=d[l],ans[k]=INF,void();build(ls),build(rs),up(k,l,r);}inline void change(int x,int v,int k=1,int l=0,int r=n){if(l==r) return mx[k]=v,void();if(x<=mid) change(x,v,ls);else change(x,v,rs);up(k,l,r);}
}
inline void del(int x,int y){auto it=S[y].find(x),pre=prev(it),nxt=next(it);if(!(*pre)) E.erase(E.find(x)),E.insert(*nxt),d[0]=*E.rbegin();else d[*pre]=*nxt;ST::change(*pre,d[*pre]),S[y].erase(*it);
}
inline void add(int x,int y){auto nxt=S[y].lower_bound(x),pre=prev(nxt);if(!(*pre)) E.erase(E.find(*nxt)),E.insert(x),d[0]=*E.rbegin();else d[*pre]=x;d[x]=*nxt,ST::change(x,d[x]),ST::change(*pre,d[*pre]),S[y].insert(x);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=m;++i) S[i].insert(n+1);for(int i=1;i<=n;++i) cin>>a[i],S[a[i]].insert(i);for(int i=1;i<=n;++i) d[i]=*S[a[i]].upper_bound(i);for(int i=1;i<=m;++i) E.insert(*S[i].begin()),d[0]=max(d[0],*S[i].begin());for(int i=1;i<=m;++i) S[i].insert(0);ST::build();for(int i=1,pos,val;i<=q;++i){cin>>pos>>val;if(a[pos]!=val) del(pos,a[pos]),add(pos,a[pos]=val);if(ST::ans[1]>n) cout<<"-1\n";else cout<<ST::ans[1]<<"\n";}
}
