\(\color{black}{P4119\ [Ynoi2018]\ 未来日记}\)

思路：分块+值域分块

复杂度：\(O(n\sqrt n+m\sqrt n)\)

主题思路

数列分块需要维护：

值域分块需要维护：

预处理：

• 序列分块、值域分块块长。
• 序列、值域每个值对应块。
• 每个块用 \(nid,fid\) 建立映射，\(f_i\) 连向此块与当前点值相同的第一个值（的下标），若此块中第一次出现当前点值，则考虑对 \(nid,fid\) 赋值。
• 显著地，扫一遍序列同时现将 \(ncnt,bcnt\) 赋上初值，再进行一遍前缀和。

修改：

• 碎块直接暴力赋值暴力重构，记得更新前缀和。
• 整块直接合并 \(x,y\) 两值，若 \(y\) 值不存在则直接将 \(x\) 并查集根节点所代表值改为 \(y\)。
• 整块的前缀和合并更新，扫整块的时候记录一个 \(temp\) 用来一次性更新前缀和，保证复杂度。

查询：

• 碎块处理需要先访问到序列真实值。
• 考虑开两个数组维护碎块的每个值出现次数、值域块内值个数。
• 查询直接先一点点跳整块（要算上碎块维护的值以及整块的值），然后一个个跳数字找到答案。
• 查询完毕记得清空维护碎块数组，注意要用添加的镜像操作回退，保证复杂度。

整体思路比较清晰，维护时注意细节，考虑每一个变量是否会在操作是变化，再卡卡常即可。

\(\text{code:}\)

#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
//IO
int rd()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
//--------------------//
const int N=1e5+5,QN=400,QN2=500;

int n,m;
//--------------------//
struct Dec
{
	struct Block
	{
		int l,r;
		int nid[N];
	}b[QN];
	int ncnt[QN][N],bcnt[QN][QN2];

	int fid[N],f[N];
	int len1,bcnt1,bl1[N];
	int len2,bcnt2,bl2[N];
	int s[N];

	inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

	inline void init()
	{
		len1=512;
		len2=256;
		for(register int i=1;i<=1e5;i++)
			bl2[i]=((bl2[i-1]*len2+1)==i?++bcnt2:bcnt2);
        int maxt=0;
		for(register int i=1;i<=n;i++)
		{
			bl1[i]=((bl1[i-1]*len1+1)==i?++bcnt1:bcnt1);
			if(!b[bl1[i]].nid[s[i]])
			{
				b[bl1[i]].nid[s[i]]=i;
				fid[i]=s[i];
			}
			f[i]=b[bl1[i]].nid[s[i]];
			ncnt[bl1[i]][s[i]]++;
			bcnt[bl1[i]][bl2[s[i]]]++;
		}
		for(register int i=1;i<=bcnt1;i++)
		{
			b[i].l=(i-1)*len1+1,b[i].r=min(n,i*len1);
			for(register int j=1;j<=1e5;j++)
				ncnt[i][j]+=ncnt[i-1][j];
			for(register int j=1;j<=bcnt2;j++)
				bcnt[i][j]+=bcnt[i-1][j];
		}
		return;
	}
	inline void cha_pic(int id,int l,int r,int x,int y)
	{
		int xcnt=0;
		//printf("\npic:\n");
		for(register int i=b[id].l;i<=b[id].r;i++)
			s[i]=fid[find(f[i])];
        for(register int i=l;i<=r;i++)
        {
			if(s[i]==x)
			{
				xcnt++;
				s[i]=y;
			}
        }
		for(register int i=b[id].l;i<=b[id].r;i++)
		{
			if(f[i]==i)
			{
				b[id].nid[fid[i]]=0;
				fid[i]=0;
			}
			f[i]=0;
		}
		for(register int i=b[id].l;i<=b[id].r;i++)
		{
			if(!b[id].nid[s[i]])
			{
				b[id].nid[s[i]]=i;
				fid[i]=s[i];
			}
			f[i]=b[id].nid[s[i]];
		}
		for(register int i=id;i<=bcnt1;i++)
		{
			ncnt[i][x]-=xcnt,ncnt[i][y]+=xcnt;
			bcnt[i][bl2[x]]-=xcnt,bcnt[i][bl2[y]]+=xcnt;
		};
		return;
	}

	inline void change(int l,int r,int x,int y)
	{
		if(x==y)
			return;
		int now1=bl1[l],now2=bl1[r];
        if(!(ncnt[now2][x]-ncnt[now1-1][x]))
            return;
		if(now1==now2)
		{
			cha_pic(now1,l,r,x,y);
			return;
		}
		cha_pic(now1,l,b[now1].r,x,y);
		cha_pic(now2,b[now2].l,r,x,y);
		int tem=0;
		for(register int temp,i=now1+1;i<now2;i++)
		{
			temp=ncnt[i][x]-ncnt[i-1][x];
			ncnt[i-1][x]-=tem,ncnt[i-1][y]+=tem;
			bcnt[i-1][bl2[x]]-=tem,bcnt[i-1][bl2[y]]+=tem;
			tem+=temp;
			if(!b[i].nid[y])
			{
				b[i].nid[y]=b[i].nid[x];
				fid[b[i].nid[y]]=y;
			}
			else
			{
				fid[b[i].nid[x]]=0;
				f[b[i].nid[x]]=b[i].nid[y];
			}
			b[i].nid[x]=0;
		}
		if(now1+1<now2)
		{
            for(register int i=now2-1;i<=bcnt1;i++)
            {
                ncnt[i][x]-=tem,ncnt[i][y]+=tem;
                bcnt[i][bl2[x]]-=tem,bcnt[i][bl2[y]]+=tem;
            }
		}
		return;
	}
	int temnc[N],tembc[QN];
	inline int get_ans(int k,int l,int r)
	{
		int now=1;
		while(k>tembc[now]+bcnt[r][now]-bcnt[l-1][now])
			k-=tembc[now]+bcnt[r][now]-bcnt[l-1][now],now++;
		for(register int i=(now-1)*len2+1;i<=min(now*len2,100000);i++)
		{
			k-=temnc[i]+ncnt[r][i]-ncnt[l-1][i];
			if(k<=0)
				return i;
		}
		return 114514;
	}
	inline int query(int l,int r,int k)
	{
		int now1=bl1[l],now2=bl1[r],res=0;
		if(now1==now2)
		{
			for(register int i=l;i<=r;i++)
				s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
			res=get_ans(k,1,0);
			for(register int i=l;i<=r;i++)
				temnc[s[i]]--,tembc[bl2[s[i]]]--;
			return res;
		}
        for(register int i=l;i<=b[now1].r;i++)
            s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
        for(register int i=b[now2].l;i<=r;i++)
            s[i]=fid[find(i)],temnc[s[i]]++,tembc[bl2[s[i]]]++;
		res=get_ans(k,now1+1,now2-1);
        for(register int i=l;i<=b[now1].r;i++)
            temnc[s[i]]--,tembc[bl2[s[i]]]--;
        for(register int i=b[now2].l;i<=r;i++)
            temnc[s[i]]--,tembc[bl2[s[i]]]--;
		return res;
	}
}D;
//--------------------//
int main()
{
	n=rd(),m=rd();
	for(int i=1;i<=n;i++)
		D.s[i]=rd();
	D.init();
	for(int op,l,r,x,y,i=1;i<=m;i++)
	{
		op=rd();
		if(op==1)
			l=rd(),r=rd(),x=rd(),y=rd(),D.change(l,r,x,y);
		else
			l=rd(),r=rd(),x=rd(),printf("%d\n",D.query(l,r,x));
	}
    return 0;
}