这个做法与 \(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,r
int 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";
}
}