RT，显然 $\log^2$ , 为什么过不了？

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

typedef long long i64;

int read() {
	int x(0), f(0);
	char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return f ? -x : x;
}
int __stk[128], __len;
void put(int x) {
	if (x < 0) putchar('-'), x = -x;
	do {
		__stk[++__len] = x % 10, x /= 10;
	} while (x);
	while (__len) putchar(__stk[__len--] ^ 48);
}

const int N = 2e5+1000, M=2e5+30;

struct Sgt {
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	#define mid ((l + r) >> 1)
	int t[N << 2], tag[N <<2];
	void pushup(int x) {
		t[x] = t[ls] + t[rs];
	}
	void pushdown(int x,int l,int r) {
		if(tag[x]!=-1) {
			t[ls]=(mid-l+1)*tag[x],tag[ls]=tag[x];
			t[rs]=(r-mid)*tag[x],tag[rs]=tag[x];
			tag[x]=-1;
		}
	}
	void modify(int x, int l, int r, int L, int R, bool v) {
		if(L>R)return;
		if (l >= L && r <= R) {
			t[x]=(r-l+1)*v, tag[x]=v;
			return;
		}
		pushdown(x,l,r);
		if (mid >= L) modify(ls, l, mid, L, R, v);
		if (mid < R) modify(rs, mid + 1, r, L, R, v);
		pushup(x);
	}
	int ask(int x, int l, int r, int L, int R) {
		if(L>R) return 0;
		if (l >= L && r <= R) return t[x];
		pushdown(x,l,r);
		int res = 0;
		if (mid >= L) res = res + ask(ls, l, mid, L, R);
		if (mid < R) res = res + ask(rs, mid + 1, r, L, R);
		return res;
	}
	int get(int x, int l, int r) {
		if(l==r) return l;
		pushdown(x,l,r);
		if(t[rs]) return get(rs,mid+1,r);
		return get(ls,l,mid);
	}
	void init() {
		memset(t,0,sizeof t);
		memset(tag,-1,sizeof tag);
	}
} St;

int n,m,a[N];
void add(int x) {
	int l=x,r=M,p=x-1;
	while(l<=r) {
		if(St.ask(1,1,M,x,mid)==mid-x+1) p=mid,l=mid+1;
		else r=mid-1;
	}
	St.modify(1,1,M,x,p,0);
	St.modify(1,1,M,p+1,p+1,1);
}
void del(int x) {
	int l=x,r=M,p=x-1;
	while(l<=r) {
		if(St.ask(1,1,M,x,mid)==0) p=mid,l=mid+1;
		else r=mid-1;
	}
	St.modify(1,1,M,x,p,1);
	St.modify(1,1,M,p+1,p+1,0);
}
signed main() {
	St.init(), n = read(),m=read();
	for(int i=1; i<=n; ++i) add(a[i]=read());
	while(m--) {
		int x=read(),y=read();
		del(a[x]),add(a[x]=y);
		put(St.get(1,1,M)),putchar('\n');
	}
	return 0;
}