[Codeforces Round #466 (Div. 2)][Codeforces 940F] Machine Learning

        题意：给出数列\(\{a_i\}\)，有两种操作：

        1.给出\(l,r\)，\(c_i\)表示数字\(i\)在\(a_l ~ a_r\)中出现的次数，求出最小的非负整数x，使得\(c_0,c_1,\cdots,c_{10^9}\)都不等于x。

        2.给出两个整数\(p,x\)，将\(a_p\)改成\(x\)。

        \(n,q\leq 10^5\)。

        题解：显然询问的答案最大是\(O(\sqrt{n})\)的，因为每个最坏情况是这些数字分别出现\(1,2,3,\cdots\)次。所以对于询问，如果实现记录好出现过x次的数字有多少个的话，直接暴力求解即可，时间复杂度\(O(n\sqrt{n})\)。

        剩下的事情，我们可以发现，若现在已经记录下某一时刻\(l~r\)的状态，转移到\(l-1~r,l+1~r,l~r-1,l~r+1\)以及做一次修改都只需要\(O(1)\)的时间，所以就是一个带修改的莫队就好了，时间复杂度\(O(n^{\frac{5}{3}})\)。

        注意要事先离散化过，否则会超时（如果擅长常数优化的话当我没说）。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxv=2e5+10;

struct Query
{
	int x,y,id,bx,by,ans;
	bool operator< (const Query &b) { return bx<b.bx || (bx==b.bx && (by<b.by || (by==b.by && id<b.id)));}
}q[maxn];

bool cmp(const Query &a,const Query &b) {return a.id<b.id;}

struct Change
{
	int x,y,id;
}c[maxn];

unordered_map <int,int> MP;int Mcnt;
int a[maxn];
int M[maxv];
int f[maxv];
int n,T,qn,cn,N;

int ID(int x)
{
	if (!MP.count(x)) return MP[x]=++Mcnt;
	else return MP[x];
}

void Add(int x)
{
	int t=M[x]++;
	f[t]--,f[t+1]++;
}

void Del(int x)
{
	int t=M[x]--;
	f[t]--,f[t-1]++;
}

int main()
{
	scanf("%d%d",&n,&T);
	N=(int)(pow((long long)n*T,1.0/3)+1);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1,ctr;i<=T;i++)
	{
		scanf("%d",&ctr);
		if (ctr==1)
			++qn,scanf("%d%d",&q[qn].x,&q[qn].y),q[qn].id=i,q[qn].bx=q[qn].x/N,q[qn].by=q[qn].y/N;
		else {
			++cn,scanf("%d%d",&c[cn].x,&c[cn].y);
			c[cn].id=i;
		}
	}
	for (int i=1;i<=n;i++) a[i]=ID(a[i]);
	for (int i=1;i<=cn;i++) c[i].y=ID(c[i].y)-a[c[i].x],a[c[i].x]+=c[i].y;
	sort(q+1,q+1+qn);
	f[0]=n+1;
	M[a[1]]=1;
	f[1]=1;
	for (int i=1,l=1,r=1,t=cn;i<=qn;i++)
	{
		while (t<cn && c[t+1].id<=q[i].id)
		{
			t++;
			int x = c[t].x;
			if (x >= l && x <= r) Del(a[x]);
			a[x] += c[t].y;
			if (x >= l && x <= r) Add(a[x]);
		}
		while (t && c[t].id>q[i].id)
		{
			int x = c[t].x;
			if (x >= l && x <= r) Del(a[x]);
			a[x] -= c[t].y;
			if (x >= l && x <= r) Add(a[x]);
			t--;
		}
		while (l > q[i].x) Add(a[--l]);
		while (r < q[i].y) Add(a[++r]);
		while (l < q[i].x) Del(a[l++]);
		while (r > q[i].y) Del(a[r--]);
		for (int j = 1; j <= n + 1; j++) if (!f[j])
		{
			q[i].ans=j;
			break;
		}
	}
	sort(q+1,q+1+qn,cmp);
	for (int i=1;i<=qn;i++) printf("%d\n",q[i].ans);
	return 0;
}