codeforces

一句话题意

求区间数字出现次数的mex，带修改

sol

带修膜队不解释

带修膜队的排序！

struct query{

	int id,l,r,t;

	bool operator < (const query &b) const

		{

			if (l/block!=b.l/block) return l/block<b.l/block;

			if (r/block!=b.r/block) return r/block<b.r/block;

			return t<b.t;

		}

}q1[N];

左端点所在块为第一关键字，右端点所在块为第二关键字，操作版本为第三关键字。

块的大小是\(n^{\frac{2}{3}}\)，复杂度是\(O(n^{\frac{5}{3}})\)

然后就是离散化数组要开两倍

code

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int gi()

{

    int x=0,w=1;char ch=getchar();

    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

    if (ch=='-') w=0,ch=getchar();

    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return w?x:-x;

}

const int N = 2e5+5;

int n,m,block,gen,a[N],b[N],o[N],cnt1,cnt2,len,vis[N],cnt[N],num[N],t[N],ans[N];

struct query{

	int id,l,r,t;

	bool operator < (const query &b) const

		{

			if (l/block!=b.l/block) return l/block<b.l/block;

			if (r/block!=b.r/block) return r/block<b.r/block;

			return t<b.t;

		}

}q1[N];

struct modify{int pos,val,pre;}q2[N];

void update(int x)

{

	--num[cnt[a[x]]];

	if (num[cnt[a[x]]]==0) --t[cnt[a[x]]/gen];

	if (!vis[x]) ++cnt[a[x]];else --cnt[a[x]];

	vis[x]^=1;

	++num[cnt[a[x]]];

	if (num[cnt[a[x]]]==1) ++t[cnt[a[x]]/gen];

}

void change(int x,int v)

{

	if (!vis[x]) a[x]=v;

	else update(x),a[x]=v,update(x);

}

int calc()

{

	for (int i=0;;++i)

		if (t[i]<gen)

			for (int j=i*gen;;++j)

				if (!num[j]) return j;

}

int main()

{

	n=gi();m=gi();block=pow(n,0.666);gen=pow(n,0.5);

	for (int i=1;i<=n;++i) a[i]=b[i]=o[++len]=gi();

	for (int i=1;i<=m;++i)

	{

		int opt=gi(),l=gi(),r=gi();

		if (opt==1) q1[++cnt1]=(query){cnt1,l,r,cnt2};

		else q2[++cnt2]=(modify){l,r,b[l]},b[l]=o[++len]=r;

	}

	sort(o+1,o+len+1);len=unique(o+1,o+len+1)-o-1;

	for (int i=1;i<=n;++i) a[i]=lower_bound(o+1,o+len+1,a[i])-o;

	for (int i=1;i<=cnt2;++i)

	{

		q2[i].val=lower_bound(o+1,o+len+1,q2[i].val)-o;

		q2[i].pre=lower_bound(o+1,o+len+1,q2[i].pre)-o;

	}

	sort(q1+1,q1+cnt1+1);

	int L=1,R=0,X=1;num[0]=1e9;t[0]=1;//出现了0次的数字有无限多个

	for (int i=1;i<=cnt1;++i)

	{

		while (X<q1[i].t) ++X,change(q2[X].pos,q2[X].val);

		while (X>q1[i].t) change(q2[X].pos,q2[X].pre),--X;

		while (L>q1[i].l) update(--L);

		while (R<q1[i].r) update(++R);

		while (L<q1[i].l) update(L++);

		while (R>q1[i].r) update(R--);

		ans[q1[i].id]=calc();

	}

	for (int i=1;i<=cnt1;++i) printf("%d\n",ans[i]);

	return 0;

}