Ynoi2018 未来日记

$\color{deeppink}link$

1 l r x y 把区间 $[l,r]$ 中的 $x$ 变成 $y$
2 l r k 查找区间 $[l,r]$ 中第 $k$ 小值

分块儿，考虑 $I$ 为块的编号， $i$ 为序列中或值的编号。

将值域和序列分块，令 $cnt[I][val]$ 表示在前 $I$ 块中值是 $val$ 中的个数，

$valcnt[I][VAL]$ 表示在前 $I$ 块中值在 $VAL$ 中的个数。

对于 $query(l,r,k)$ ，考虑先把答案的块求出来。

令不在整块中的元素集为 $P$ ，求出 $Pcnt[VAL]$ 表示 $P$ 中值域在 $VAL$ 元素的元素个数。

则有：

\sum_{I=1}^{ANS}Pcnt[I]+valcnt[R][I]-valcnt[L-1][I]\ge k

从 $1$ 开始枚举即可。

而后考虑具体地求出答案。

又令 $pcnt[val]$ 表示在 $P$ 中， $val$ 的个数，则有：

\sum_{i=1}^{ans}=pcnt[i]+cnt[R][i]-cnt[L-1][i]\ge k-\text{rest}

rest 就是值域在 $[1,ANS]$ 中的元素个数。

接下来就是修改了。

对于某一个块，维护 $fa_x$ 表示值 $x$ 在并查集中对应的第一个的位置， $val_x$ 表示 $x$ 位置对应的值， $pos_x=fa_{a_x}$ 。

则对于 $i$ 位置的权值即为 $val_{pos_i}$ 。

有以下情况：

无 $x$

跳过。

有 $x$ 无 $y$

将 $fa_y=fa_x,val_{fa_x}=y,fa_x=0$ 。

有 $x,y$

注意到所有的权值最多有 $n+m$ 个，而这种情况会少一个权值，故可以暴力重构，时间是 $O((n+m)\sqrt n)$ 。

修改的时候把每一个块从头枚举一遍即可，顺便修改下 $cnt$ 一类的值即可。

复杂的是~~优秀的~~ $O((n+m)\sqrt n)$ 。

//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50,M=N/500+50;

int n,b[N],q,ed[N],bg[N],belong[N],a[N],siz=500,mx,cnt[M][N],valcnt[M][M],Pcnt[M],pcnt[N],fa[M][N],pos[N],val[N];

void change(int l,int r,int x,int y)
{
	int s=0,nx=cnt[belong[l]][x];
	if(belong[l]==belong[r])
	{
		for(int i=bg[belong[l]];i<=ed[belong[l]];i++)
		{
			fa[belong[l]][val[i]]=0,a[i]=val[pos[i]];
		}
		for(int i=l;i<=r;i++)if(a[i]==x)a[i]=y,++s;
		for(int i=bg[belong[l]];i<=ed[belong[l]];i++)
		{
			fa[belong[l]][a[i]]=(fa[belong[l]][a[i]]?fa[belong[l]][a[i]]:i);
			pos[i]=fa[belong[l]][a[i]];val[i]=a[i];
		}
		for(int i=belong[l];i<=belong[n];i++)
		{
			valcnt[i][belong[x]]-=s;
			valcnt[i][belong[y]]+=s;
			cnt[i][x]-=s;
			cnt[i][y]+=s;
		}
		return;
	}
	if(fa[belong[l]][x])
	{
		for(int i=bg[belong[l]];i<=ed[belong[l]];i++)
		{
			fa[belong[l]][val[i]]=0,a[i]=val[pos[i]];
		}
		for(int i=l;i<=min(ed[belong[l]],r);i++)if(a[i]==x)a[i]=y,++s;
		for(int i=bg[belong[l]];i<=ed[belong[l]];i++)
		{
			fa[belong[l]][a[i]]=(fa[belong[l]][a[i]]?fa[belong[l]][a[i]]:i);
			pos[i]=fa[belong[l]][a[i]];val[i]=a[i];
		}
		valcnt[belong[l]][belong[x]]-=s;
		valcnt[belong[l]][belong[y]]+=s;
		cnt[belong[l]][x]-=s;
		cnt[belong[l]][y]+=s;
	}
	for(int i=belong[l]+1;i<belong[r];i++)
	{
		if(!fa[i][x])
		{
			valcnt[i][belong[x]]-=s;
			valcnt[i][belong[y]]+=s;
			cnt[i][x]-=s;
			cnt[i][y]+=s;
			continue;
		}
		if(!fa[i][y])
		{
			fa[i][y]=fa[i][x];
			val[fa[i][x]]=y;
			fa[i][x]=0;
		}
		else
		{
			for(int j=bg[i];j<=ed[i];j++)
			{
				a[j]=val[pos[j]];
				fa[i][val[j]]=0;
				if(a[j]==x)a[j]=y;
			}
			for(int j=bg[i];j<=ed[i];j++)
			{
				fa[i][a[j]]=(fa[i][a[j]]?fa[i][a[j]]:j);
				pos[j]=fa[i][a[j]];val[j]=a[j];
			}
		}
		s+=cnt[i][x]-nx;nx=cnt[i][x];
		valcnt[i][belong[x]]-=s;
		valcnt[i][belong[y]]+=s;
		cnt[i][x]-=s;
		cnt[i][y]+=s;
	}
	if(fa[belong[r]][x])
	{
		for(int i=bg[belong[r]];i<=ed[belong[r]];i++)
		{
			fa[belong[r]][val[i]]=0,a[i]=val[pos[i]];
		}
		for(int i=bg[belong[r]];i<=r;i++)if(a[i]==x)a[i]=y,++s;
		for(int i=bg[belong[r]];i<=ed[belong[r]];i++)
		{
			fa[belong[r]][a[i]]=(fa[belong[r]][a[i]]?fa[belong[r]][a[i]]:i);
			pos[i]=fa[belong[r]][a[i]];val[i]=a[i];
		}
	}
	for(int i=belong[r];i<=belong[n];i++)
	{
		valcnt[i][belong[x]]-=s;
		valcnt[i][belong[y]]+=s;
		cnt[i][x]-=s;
		cnt[i][y]+=s;
	}
}

void find(int l,int r,int k)
{
	if(belong[l]==belong[r])
	{
		for(int i=l;i<=r;i++)b[i-l+1]=val[pos[i]];
		sort(b+1,b+1+r-l+1);printf("%ld\n",b[k]);return;
	}
	for(int i=1;i<=belong[n];i++)Pcnt[i]=0;
	for(int i=l;i<=ed[belong[l]];i++)++Pcnt[belong[val[pos[i]]]];
	for(int i=bg[belong[r]];i<=r;i++)++Pcnt[belong[val[pos[i]]]];
	int re=0,u=0;
	while(++u)
	{
		if(re+Pcnt[u]+valcnt[belong[r]-1][u]-valcnt[belong[l]][u]>=k)break;
		re+=Pcnt[u]+valcnt[belong[r]-1][u]-valcnt[belong[l]][u];
	}
	for(int i=bg[u];i<=ed[u];i++)pcnt[i]=0;
	for(int i=l;i<=ed[belong[l]];i++)++pcnt[val[pos[i]]];
	for(int i=bg[belong[r]];i<=r;i++)++pcnt[val[pos[i]]];
	for(int i=bg[u];i<=ed[u];i++)
	{
		re+=pcnt[i]+cnt[belong[r]-1][i]-cnt[belong[l]][i];
		if(re>=k){printf("%ld\n",i);return;}
	}
}

char cch,B0[1<<15],*S=B0,*TT=B0;
#define getc() (S==TT&&(TT=(S=B0)+fread(B0,1,1<<15,stdin),S==TT)?0:*S++)
int aa;inline int read(){
	while(cch=getc(),cch<'0'||cch>'9');aa=cch-'0';
	while(cch=getc(),cch>='0'&&cch<='9')aa=((aa<<3)+(aa<<1))+cch-'0';return aa;
}

main()
{
//	freopen("data.txt","r",stdin);
//	freopen("wa.txt","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)belong[i]=(i-1)/siz+1;
	for(int i=1;i<=belong[n];i++)
	{
		bg[i]=((i-1)*siz+1),ed[i]=(i*siz);
		for(int j=1;j<=n;j++)cnt[i][j]=cnt[i-1][j];
		for(int j=1;j<=belong[n];j++)valcnt[i][j]=valcnt[i-1][j];
		for(int j=bg[i];j<=ed[i];j++)cnt[i][a[j]]++,valcnt[i][belong[a[j]]]++;
		for(int j=bg[i];j<=ed[i];j++)
		{
			if(!fa[i][a[j]])fa[i][a[j]]=j;
			pos[j]=fa[i][a[j]];val[j]=a[j];
		}
	}
	while(q--)
	{
		int opt,l,r,k,x,y;
		opt=read(),l=read(),r=read();
		if(opt==1)
		{
			x=read(),y=read();
			if(x==y)continue;
			change(l,r,x,y);
		}
		else
		{
			k=read();
			find(l,r,k);
		}
	}
}

感谢您的支持，我会继续努力的!