上一次 P1903 调半天

现在这题也是半天调不出来QAQ

每次都是 Time limit exceeded on test 3

代码就是正常的的带修莫队暴力统计答案

我猜要么排序出了问题，要么块长出了问题别的要是有问题就真的不知道了

// TLE on test #3
#pragma GCC optimize(2,3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio> 
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

inline void read(int &x)
{
	x = 0; char c = getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
}
void print(int x)
{
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

const int MAXN = 100010;

int n, m, a[MAXN], pos[MAXN], d[MAXN<<1], num = 0, len; 

struct qry{
	int l, r, ind, t;
	qry(int L=0,int R=0,int T=0,int I=0):l(L),r(R),t(T),ind(I){}
	bool operator<(const qry &o)const
	{
		if(pos[l] ^ pos[o.l]) return pos[l]<pos[o.l];
		if(pos[r] ^ pos[o.r]) return pos[r]<pos[o.r];
		return t<o.t;
	}
	//bool operator<(const qry &o)const{return pos[l]^pos[o.l]?l<o.l:pos[r]^pos[o.r]?r<o.r:t<o.t;}
}b[MAXN];
struct chg{
	int pos, val;
	chg(int P=0,int V=0):pos(P),val(V){}
}c[MAXN];
int cntq = 0, cntc = 0;

int l = 1, r = 0, t = 0, res = 0, ans[MAXN];
int cnt[MAXN<<1], tot[MAXN<<1];

inline void add(int x)
{
	--tot[cnt[x]];
	++tot[++cnt[x]];
}
inline void del(int x)
{
	--tot[cnt[x]];
	++tot[--cnt[x]];
}
inline void modify(int x, int y)
{
	if(c[y].pos >= b[x].l && c[y].pos <= b[x].r)
	{
		del(a[c[y].pos]);
		add(c[y].val);
	}
	swap(a[c[y].pos], c[y].val);
}

int main()
{
	read(n); read(m);
	len = pow(n, 1.33333);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		d[++num] = a[i];
		pos[i] = (i-1)/len+1;
	}
	for(int i=1;i<=m;i++)
	{
		int opt, x, y;
		read(opt); read(x); read(y);
		if(opt == 1) ++cntq, b[cntq] = qry(x, y, cntc, cntq);
		else c[++cntc] = chg(x, y), d[++num] = y;
	}
	sort(d+1, d+num+1);
	int k = unique(d+1, d+num+1) - d - 1;
	for(int i=1;i<=n;i++)
		a[i] = lower_bound(d+1, d+k+1, a[i]) - d;
	for(int i=1;i<=cntc;i++)
		c[i].val = lower_bound(d+1, d+k+1, c[i].val) - d;
	for(int i=1;i<=cntq;i++)
	{
		while(l < b[i].l) del(a[l++]);
		while(l > b[i].l) add(a[--l]);
		while(r < b[i].r) add(a[++r]);
		while(r > b[i].r) del(a[r--]);
		while(t < b[i].t) modify(i, ++t);
		while(t > b[i].t) modify(i, t--);
		ans[b[i].ind] = 1;
		while(tot[ans[b[i].ind]]) ++ans[b[i].ind];
	}
	for(int i=1;i<=cntq;i++)
		print(ans[i]), putchar('\n');
	return 0;
}