模拟赛搬了这题的 加强版。于是有了一个复杂度和 无关的做法。感觉学到了。
设 为左端点为 时，最小的可行右端点。考虑维护这个东西。但是你发现修改一个位置的值很难维护。
你又发现每次只修改一个数，考虑线段树分治。但是你又发现你连插入都不会做。但是删除非常简单。设删了 位置的一个 ，左右第一个 分别在 ，就只要 就行。于是还是线段树分治，但是对删除操作进行。
具体地，把修改操作视作一次删除一次插入。先默认进行所有插入，再在某一些时间区间上进行删除。再来看看我们要维护什么：
- 找一个数的前驱后继，删除/插入一个数。
使用 multiset 维护即可。
- 区间对 取 。
一般需要吉司机，但是发现这题 一定单调递增，于是转化成一段区间赋值 。使用线段树，支持区间赋值以及线段树上二分。
同时注意到将一个区间 赋值成 的时候，区间 内的答案一定是 ，于是可以同时维护答案。
至于线段树分治上的撤销操作，只需要每次这棵线段树上维护的值改变（包括 tag），就将原来的值压进一个栈里，撤销时直接修改即可。
时间复杂度 解决。
code：
int n,m,q,top,a[N],f[N],ans[N];
bool vis[N];
multiset<int> st[N];
vector<int> g[N];
struct node{
int l,r,k;
node(int _l=0,int _r=0,int _k=0):l(_l),r(_r),k(_k){}
bool operator<(const node &rhs)const{
return k<rhs.k;
}
};
struct Node{
int o,x,y,z;
}d[N*400];
struct Sgt{
int tr[N<<2],tag[N<<2],mn[N<<2];
il void pushup(int o){
d[++top]={o,tr[o],tag[o],mn[o]};
tr[o]=max(tr[o<<1],tr[o<<1|1]);
mn[o]=min(mn[o<<1],mn[o<<1|1]);
}
il void reset(int l,int r,int o,int k){
d[++top]={o,tr[o],tag[o],mn[o]};
tr[o]=k,tag[o]=k;
mn[o]=k-r+1;
}
il void pushdown(int l,int r,int o){
if(tag[o]){
int mid=(l+r)>>1;
reset(l,mid,o<<1,tag[o]);
reset(mid+1,r,o<<1|1,tag[o]);
d[++top]={o,tr[o],tag[o],mn[o]};
tag[o]=0;
}
}
void update(int l,int r,int o,int x,int y,int k){
if(l>=x&&r<=y){
reset(l,r,o,k);
return;
}
pushdown(l,r,o);
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y,k);
}
if(y>mid){
update(mid+1,r,o<<1|1,x,y,k);
}
pushup(o);
}
int find(int l,int r,int o,int k){
if(l==r){
return tr[o]>=k?l:n+1;
}
pushdown(l,r,o);
int mid=(l+r)>>1;
if(tr[o<<1]<k){
return find(mid+1,r,o<<1|1,k);
}
return find(l,mid,o<<1,k);
}
int query(int l,int r,int o,int x){
if(l==r){
return tr[o];
}
pushdown(l,r,o);
int mid=(l+r)>>1;
if(x<=mid){
return query(l,mid,o<<1,x);
}
return query(mid+1,r,o<<1|1,x);
}
}R;
il void upd(int l,int r,int k){
l=max(l,1),r=min(r,R.find(1,n,1,k)-1);
if(l>r){
return;
}
R.update(1,n,1,l,r,k);
}
struct SGT{
vector<pii> tr[N<<2];
void delet(int o,int tmp){
while(top>tmp){
Node u=d[top--];
R.tr[u.o]=u.x,R.tag[u.o]=u.y,R.mn[u.o]=u.z;
}
for(auto [i,j]:tr[o]){
st[j].insert(i);
}
}
void update(int l,int r,int o,int x,int y,int a,int b){
if(x<0||y>q||x>y){
return;
}
if(l>=x&&r<=y){
tr[o].eb(a,b);
return;
}
int mid=(l+r)>>1;
if(x<=mid){
update(l,mid,o<<1,x,y,a,b);
}
if(y>mid){
update(mid+1,r,o<<1|1,x,y,a,b);
}
}
void solve(int l,int r,int o){
int tmp=top;
for(auto [i,j]:tr[o]){
st[j].erase(st[j].find(i));
if(st[j].find(i)!=st[j].end()){
continue;
}
auto it=st[j].lower_bound(i);
int x=*prev(it),y=*it;
upd(x+1,i,y);
}
if(l==r){
ans[l]=R.mn[1];
return delet(o,tmp);
}
int mid=(l+r)>>1;
solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
return delet(o,tmp);
}
}T;
void Yorushika(){
read(n,m,q);
rep(i,1,m){
st[i].insert(-inf),st[i].insert(inf);
}
rep(i,1,n){
read(a[i]),st[a[i]].insert(i);
g[i].eb(a[i]);
}
rep(i,1,q){
int op,x,y;read(op);
if(op==1){
read(x,y);
st[y].insert(x);
g[x].eb(y);
T.update(1,q,1,1,i-1,x,y);
T.update(1,q,1,i,q,x,a[x]);
a[x]=y;
}else{
vis[i]=1;
}
}
rep(i,1,m){
f[1]=max(f[1],*st[i].lower_bound(1));
}
rep(i,2,n){
f[i]=f[i-1];
for(int j:g[i-1]){
f[i]=max(f[i],*st[j].lower_bound(i));
}
}
rep(i,1,n){
R.update(1,n,1,i,i,f[i]);
}
top=0;
T.solve(1,q,1);
rep(i,1,q){
if(vis[i]){
printf("%d\n",ans[i]>1e9?-1:ans[i]);
}
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
