NOIP2023未来共同体 模拟八

最集集的一集。

A. 硬币机（coin）

题目简介

给定 个物品，每个物品可以花费 的代价获得 的贡献，对 求出恰好花费 时得到的最大贡献。

数据范围：

上强度了， 是早年 压轴题。

记录价值函数 有 的贡献，然后考虑朴素 。

设 表示前 个物品付出了 的代价。那么有：

$$f_{i,j}=\max\{f_{i-1,k}+g_{i,k-j}\}$$

容易发现这是一个 卷积。时间复杂度 。

这个形式不怎么好优化，所以我们换一种形式 表示考虑了 内的物品总代价为 时的最大贡献。这是一种背包合并的方式。

这是 卷积的经典优化形式，但必须保证 必须是凸函数，而这道题并不满足——吗？

贡献是单增的，这我还真不知道是不是单增的，但是即使贡献不单增，也有一种凸函数的方法，那就是对于固定的 ， 是凸函数。至于怎么发现的我还真不知道，但是我们按照 的同余系分治转移即可。

时间复杂度 。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Vector=std::vector<ll>;
const int MAXN=1e5+10;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M;
ll a[MAXN],b[MAXN],ans;
Vector vec[MAXN];
Vector solve(int l,int r)
{
	if(l==r) return vec[l];
	int mid=(l+r)>>1;
	auto _l=solve(l,mid),_r=solve(mid+1,r);
	int lenl=_l.size()-1,lenr=_r.size()-1;
	Vector f;f.resize(lenl+lenr+1,-INF);
	for(int i=0;i<12;++i)
		for(int j=0;j<12;++j)
			for(int x=i,y=j;x<=lenl&&y<=lenr;)
			{
				checkMax(f[x+y],_l[x]+_r[y]);
				if(y+12>lenr||(x+12<=lenl&&_l[x+12]+_r[y]>_l[x]+_r[y+12])) x+=12;
				else y+=12;
			}
	return f;
}
int main()
{
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) read(a[i]);
	for(int i=1;i<=N;++i) read(b[i]);
	for(int i=1;i<=N;++i)
	{
		vec[i].resize(4);
		vec[i][0]=0,vec[i][1]=a[i],vec[i][2]=a[i]+b[i],vec[i][3]=2*a[i]+b[i];
	}
	auto res=solve(1,N);
	for(int i=1;i<=M&&i<=3*N;++i) ans^=res[i];
	for(int i=3*N+1;i<=M;++i) ans^=res[3*N];
	write(ans);
	return 0;
}
/*

*/

---

B. 文章查重（string）

题目简介

给定 ，满足 。之后会构造 个字符串，每个字符串由一个长度为 的序列和字符串 组成。即 由 和 依次拼接而成。

对 求出 在里面出现的次数。对 取模。

数据范围：

容易发现特殊限制很多，所以肯定不是那么难做（当然还是很难做）。

考虑到 的组合方式很震撼，所以我们可以将贡献拆分成 ，也就是通过前面的答案组合，然后缺少的就是相邻的组合时产生的新答案以及 和 组合时产生的新答案。这意味着我们要对一些前缀和后缀进行处理。

然后有 ，所以有 的前缀一定是 。所以我们只需要对 的前缀进行处理。

然后考虑贡献，显然是一个 集合，所以我们对 处理 后匹配，维护 的最长的 前缀的后缀。

时间复杂度 。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){return x>y?x=y,1:0; }
const int MAXN=1e6+10,MAXS=2e6+10;
int N;
char S[MAXS],T0[MAXS],D[MAXS];
ull ans[MAXS],cnt[MAXS];
int Nxt[MAXS][2],Kmp[MAXS],Pos[MAXS],val[MAXS],p;
bool flg[MAXS];
int main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	read(N);
	scanf("%s%s",S+1,T0+1);
	int Slen=std::strlen(S+1),Tlen=std::strlen(T0+1);
	std::reverse(S+1,S+Slen+1),std::reverse(T0+1,T0+Tlen+1);
	for(int i=2,j=0;i<=Slen;++i)
	{
		while(j&&S[j+1]!=S[i]) j=Kmp[j];
		if(S[i]==S[j+1]) ++j;
		Kmp[i]=j;
	}
	for(int i=1;i<=Tlen;++i)
	{
		while(p&&T0[i]!=S[p+1]) p=Kmp[p];
		if(S[p+1]==T0[i]) ++p;
		ans[0]+=(p==Slen);
	}
	if(p==Slen) p=Kmp[p];
	while(p) flg[Slen-p]=1,p=Kmp[p];
	std::reverse(S+1,S+Slen+1),std::reverse(T0+1,T0+Tlen+1);
	p=0;
	for(int i=2;i<=Slen;++i)
	{
		while(p&&S[p+1]!=S[i]) p=Kmp[p];
		if(S[p+1]==S[i]) ++p;
		Kmp[i]=p;
	}
	p=0;
	for(int i=1;i<=Tlen;++i)
	{
		while(p&&S[p+1]!=T0[i]) p=Kmp[p];
		if(S[p+1]==T0[i]) ++p;
	}
	Pos[0]=p;
	Nxt[0][S[1]-'0']=1;
	for(int i=1;i<=Slen;++i)
	{
		cnt[i]=flg[i]+cnt[Kmp[i]];
		Nxt[i][0]=Nxt[Kmp[i]][0];
		Nxt[i][1]=Nxt[Kmp[i]][1];
		if(i<Slen) Nxt[i][S[i+1]-'0']=i+1;
	}
	for(int i=1,Ki;i<=N;++i)
	{
		read(Ki);
		for(int j=1;j<=Ki;++j)
		{
			read(val[j]);
			ans[i]+=ans[val[j]];
			if(j!=Ki) ans[i]+=cnt[Pos[val[j]]];
		}
		scanf("%s",D+1);
		int Dlen=std::strlen(D+1);
		p=Pos[val[Ki]];
		for(int l=1;l<=Dlen;++l)
		{
			p=Nxt[p][D[l]-'0'];
			ans[i]+=(p==Slen);
		}
		Pos[i]=p;
		write(ans[i],'\n');
	}
	return 0;
}
/*

*/

---

C. 酒杯（glass）

题目简介

给定一棵深度为 的满二叉树（有 个结点），每次随机标记树上一个结点，结点可被重复标记。标记具有顺序。操作 次操作后，求出有多少种方案使得每一层至少存在 个结点被标记。对 取模。

数据范围：。

特殊数据：

考虑朴素做法，设 表示第 层共操作 次合法的方案数。那么转移：

$$f_{i,j}=\sum_{k}f_{i,j-k}\cdot(2^{i-1})^k$$

这个可以做到 。

这个方法的优化很奇妙，好像是回到原题中概率的思路上去，没听懂，所以我们选择题解中给出的方法。

考虑子集反演，设 表示至少当前还没有标记的层数的状态，即未在内的状态可能也没有被标记，而 表示恰好。

有 ，即结点总数减去 中层数的结点之和的 次方。设 表示 的 popcount，则有：

$$ans=g_\varnothing=\sum_S (-1)^{|S|}f_S=\sum_{i=0}^{2^n-1}(-1)^{n-c(i)}i^m$$

所以可以做到 ，过掉特殊数据。

然后考虑优化，记：

$$f_{i,j}=\sum_{x=0}^{2^i-1}(-1)^{n-c(x)}x^j$$

那么我们只需要关注 位是否为 即可统一计算，通过二项式定理直接求解。时间复杂度 。

然后发现因为只需要关注第 位，所以位与位之间贡献独立，所以逐位转移变为倍增转移，时间复杂度 。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){return x>y?x=y,1:0; }
#define popcount(x) __builtin_popcount(x)
const int MAXN=2e3+10;
const int Mod=1e9+7;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M;
ll Dp[MAXN][MAXN],Mul[MAXN],Inv[MAXN];
ll Pw2[MAXN][MAXN];
inline ll qPow(ll a,ll b=Mod-2)
{
	ll res=1;
	for(;b;b>>=1,a=a*a%Mod) (b&1)&&(res=res*a%Mod);
	return res;
}
int main()
{
	freopen("glass.in","r",stdin);
	freopen("glass.out","w",stdout);
	read(N,M);
	if(N<=20)
	{
		ll ans=0,m=M<0?1145141919ll:M;
		for(int s=0;s<(1<<N);++s)
		{
			if((N-popcount(s))&1) add(ans,Mod-qPow(s,m));
			else add(ans,qPow(s,m));
		}
		return write(ans),0;
	}
	Dp[0][0]=Mul[0]=Inv[0]=1;
	for(int i=1;i<=M;++i) Mul[i]=Mul[i-1]*i%Mod;
	Inv[M]=qPow(Mul[M]);
	for(int i=M-1;i;--i) Inv[i]=Inv[i+1]*(i+1)%Mod;
	for(int i=0,pw=1;i<=N;++i,pw=pw*2%Mod)
	{
		Pw2[i][0]=1;
		for(int j=1;j<=M;++j) Pw2[i][j]=Pw2[i][j-1]*pw%Mod;
		for(int j=1;j<=M;++j) Pw2[i][j]=Pw2[i][j]*Inv[j]%Mod;
	}
	for(int i=1;i<=N;++i)
		for(int j=i-1;j<=M-N+i+1;++j)
		{
			if(!Dp[i-1][j]) continue;
			for(int l=1;j+l<=M-N+i+1;++l) add(Dp[i][j+l],Dp[i-1][j]*Pw2[i-1][l]%Mod);
		}
	write(Dp[N][M]*Mul[M]%Mod);
	return 0;
}
/*

*/

---

D. 第K大MEX（kthmex）

题目简介

给定一个长度为 的序列 ，维护 次操作：

• 将区间 内所有 变成 ；
• 求出区间 中的第 大 。

第 大 指区间内第 大未出现的正整数。

数据范围：

起猛了，NOIP模拟赛出大分块。

这个数据范围，以及奇妙的修改操作，所以我们可以直接断定这是一道分块题，而第一个操作在 中也经常见到，对值域维护并查集，均摊复杂度下查询权值即可。

我们按照 的部分分中，维护主席树的 表示 中 最后一次出现的位置，然后二分查找可以做到 的区间 ，但是这个方法并不能扩展到维护第 大 。

首先对序列进行分块，然后维护 个关键点的 ，然后对于 ，本质上是一个 的二维偏序，所以我们再套上值域分块 ，维护 之间的 前后缀信息，对于单点修改，可以套上 进行实现。然后离散化，可以做到 的查询复杂度。

对于修改操作，序列分块维护 ，处理关键点的 ，套上 单点修改。时间复杂度 。

至于查询，找到距离 最近的比 小的关键点 ，如果 ，则暴力维护，否则直接使用 ，然后维护 ，时间复杂度 。

取 可以做到 。

出题人给出了一种卡空间常数的方法，但是做到 的空间需要将 劣化为平衡树，时间会翻倍。

AC Code

// std1:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cmath>
#include <map>
const int Q = 100005;
const int P = 200005;
const int O = 62;
const int H = 62;
const int INF = (1 << 30);
typedef long long ll;
#define rg register int
#define cint const register int
const int SZ = 1 << 21;
char ibuf[SZ | 5], *IP1 = ibuf, *IP2 = ibuf;
#define gc() (__builtin_expect(IP1 == IP2, 0) && (IP2 = (IP1 = ibuf) + fread(ibuf, 1, SZ, stdin), __builtin_expect(IP1 == IP2, 0)) ? EOF : *IP1++)
char obuf[SZ | 5], *OP1 = obuf;
const char *OP2 = obuf + SZ;
inline void pc(const char c)
{
    *OP1++ = c;
    __builtin_expect(OP1 == OP2, 0) && (fwrite(obuf, 1, SZ, stdout), OP1 = obuf);
}
inline bool ig(const char c) { return c >= 48 && c <= 57; }
inline void read(rg &oi)
{
    char c;
    rg f = 1, res = 0;
    while (c = gc(), (!ig(c)) && c ^ '-')
        ;
    c ^ '-' ? res = (c ^ 48) : f = -1;
    while (c = gc(), ig(c))
        res = res * 10 + (c ^ 48);
    oi = f * res;
}
inline void print(rg oi)
{
    char io[23];
    rg l = 0;
    if (oi < 0)
        pc('-'), oi = ~oi + 1;
    do
        io[++l] = (oi % 10 + 48);
    while (oi /= 10);
    for (; l; --l)
        pc(io[l]);
}
inline void write(cint oi, const char c)
{
    print(oi);
    pc(c);
}
char _ST_;
inline int min(cint x, cint y) { return x < y ? x : y; }
inline int max(cint x, cint y) { return x > y ? x : y; }
int n, m, a[Q], b[P], Mx, B, T, bl[Q], bx[P], cb, lp[Q], rp[Q];
struct oper
{
    int op, l, r, x, y;
    oper() = default;
} q[Q];
bool in[Q];
std::map<int, bool> vst;
int ps[O][P], rt[O][H], pt[O][P];
namespace dsu
{
    int prt[Q];
    inline void init(cint N)
    {
        for (rg i = 1; i <= N; ++i)
            prt[i] = i;
    }
    inline int Grt(cint x) { return x ^ prt[x] ? prt[x] = Grt(prt[x]) : x; }
}
int sz[H], stk[Q], tn;
unsigned short pool[Q * 40 * 41], *cur = pool;
struct BIT
{
    unsigned short *c;
    int lim;
    inline void insert(cint x)
    {
        for (rg i = x; i; i -= i & -i)
            ++c[i];
    }
    inline void erase(cint x)
    {
        for (rg i = x; i; i -= i & -i)
            --c[i];
    }
    inline int qry(cint x)
    {
        rg res = 0;
        for (rg i = x; i <= lim; i += i & -i)
            res += c[i];
        return res;
    }
    inline void bld()
    {
        for (rg i = 1; i <= tn; ++i)
            ++c[stk[i]];
        for (rg i = lim; i >= 1; --i)
            c[i - (i & -i)] += c[i];
    }
};
BIT rn[O][H];
int cc[H], st[Q];
bool vs[P];
inline void rbd(cint l, cint r, cint x, cint y)
{
    cint o = bl[l], L = lp[o], R = rp[o], vx = bx[x], vy = bx[y];
    cint tx = ps[o][x], ty = ps[o][y];
    pt[o][x] = pt[o][y] = ps[o][x] = ps[o][y] = 0;
    rg top = 0;
    for (rg i = L; i <= R; ++i)
    {
        a[i] = a[dsu::Grt(i)];
        if (a[i] == x || a[i] == y)
            st[++top] = i;
    }
    for (rg i = l; i <= r; ++i)
        if (a[i] == x)
            a[i] = y;
    for (rg i = 1; i <= top; ++i)
    {
        cint t = st[i], v = a[t];
        ps[o][v] = t;
        rg &ro = pt[o][v];
        if (!ro)
            ro = t;
        dsu::prt[t] = ro;
    }
    if (!ps[o][x])
        ps[o][x] = ps[o - 1][x];
    if (!ps[o][y])
        ps[o][y] = ps[o - 1][y];
    if (tx ^ ps[o][x])
        rn[o][vx].erase(tx), rn[o][vx].insert(ps[o][x]);
    if (ty ^ ps[o][y])
        rn[o][vy].erase(ty), rn[o][vy].insert(ps[o][y]);
}
inline void mdy(cint l, cint r, cint x, cint y)
{
    if (x == y)
        return;
    cint lb = bl[l], rb = bl[r], vx = bx[x], vy = bx[y];
    if (lb == rb)
    {
        rbd(l, r, x, y);
        cint px = ps[lb][x], py = ps[lb][y];
        for (rg i = lb + 1; i <= cb - 1; ++i)
        {
            if (ps[i][x] >= l && ps[i][x] <= r && (ps[i][x] != px))
            {
                rn[i][vx].erase(ps[i][x]);
                ps[i][x] = px;
                if (px)
                    rn[i][vx].insert(px);
            }
            if (py && (!ps[i][y] || ps[i][y] < py))
            {
                if (ps[i][y])
                    rn[i][vy].erase(ps[i][y]);
                ps[i][y] = py;
                rn[i][vy].insert(py);
            }
        }
        return;
    }
    rbd(l, rp[lb], x, y);
    for (rg i = lb + 1; i <= rb - 1; ++i)
    {
        if (!pt[i][x])
        {
            if (ps[i][x] ^ ps[i - 1][x])
            {
                if (ps[i][x])
                    rn[i][vx].erase(ps[i][x]);
                ps[i][x] = ps[i - 1][x];
                if (ps[i][x])
                    rn[i][vx].insert(ps[i][x]);
            }
            if (ps[i][y] ^ ps[i - 1][y])
            {
                if (!pt[i][y])
                {
                    if (ps[i][y])
                        rn[i][vy].erase(ps[i][y]);
                    ps[i][y] = ps[i - 1][y];
                    if (ps[i][y])
                        rn[i][vy].insert(ps[i][y]);
                }
            }
            continue;
        }
        if (!pt[i][y])
            pt[i][y] = pt[i][x], a[pt[i][y]] = y;
        else
            dsu::prt[pt[i][x]] = dsu::prt[pt[i][y]];
        if (ps[i][x])
            rn[i][vx].erase(ps[i][x]);
        if (!ps[i][y] || (ps[i][y] < ps[i][x]))
        {
            if (ps[i][y])
                rn[i][vy].erase(ps[i][y]);
            ps[i][y] = ps[i][x];
            if (ps[i][y])
                rn[i][vy].insert(ps[i][y]);
        }
        ps[i][x] = ps[i - 1][x];
        if (ps[i][x])
            rn[i][vx].insert(ps[i][x]);
        pt[i][x] = 0;
    }
    rbd(lp[rb], r, x, y);
    cint px = ps[rb][x], py = ps[rb][y];
    for (rg i = rb + 1; i <= cb - 1; ++i)
    {
        if (ps[i][x] >= l && ps[i][x] <= r && (ps[i][x] != px))
        {
            rn[i][vx].erase(ps[i][x]);
            ps[i][x] = px;
            if (px)
                rn[i][vx].insert(px);
        }
        if (py && (!ps[i][y] || ps[i][y] < py))
        {
            if (ps[i][y])
                rn[i][vy].erase(ps[i][y]);
            ps[i][y] = py;
            rn[i][vy].insert(py);
        }
    }
}
inline void qry(cint l, cint r, rg k)
{
    cint o = bl[r] - 1, p = rp[o];
    if (p < l)
    {
        for (rg i = l; i <= r; ++i)
        {
            cint o = a[dsu::Grt(i)];
            if (!vs[o])
                ++cc[bx[o]], vs[o] = 1;
        }
        rg i = 1, j = 1;
        for (; j <= Mx; ++i, j += T)
        {
            cint t = sz[i] - cc[i];
            if (t >= k)
                break;
            k -= t;
        }
        j = min(j, Mx + 1);
        for (; k && j <= i * T && j <= Mx; ++j)
        {
            cint t = b[j] - b[j - 1] - vs[j];
            if (t >= k)
                break;
            k -= t;
        }
        write(b[j - 1] + k, '\n');
        for (rg i = l; i <= r; ++i)
        {
            cint o = a[dsu::Grt(i)];
            cc[bx[o]] = vs[o] = 0;
        }
        return;
    }
    for (rg i = p + 1; i <= r; ++i)
    {
        cint v = a[dsu::Grt(i)];
        if (!vs[v] && ps[o][v] < l)
            ++cc[bx[v]], vs[v] = 1;
    }
    rg i = 1, j = 1;
    for (; j <= Mx; ++i, j += T)
    {
        cint t = sz[i] - rn[o][i].qry(l) - cc[i];
        if (t >= k)
            break;
        k -= t;
    }
    j = min(j, Mx + 1);
    for (; k && j <= i * T && j <= Mx; ++j)
    {
        cint t = b[j] - b[j - 1] - (vs[j] || ps[o][j] >= l);
        if (t >= k)
            break;
        k -= t;
    }
    write(b[j - 1] + k, '\n');
    for (rg i = p + 1; i <= r; ++i)
    {
        cint v = a[dsu::Grt(i)];
        cc[bx[v]] = vs[v] = 0;
    }
}
char _ED_;
int main()
{
#ifdef ONLINE_JUDGE
    freopen("kthmex.in", "r", stdin);
    freopen("kthmex.out", "w", stdout);
#endif
    fprintf(stderr, "static memory:%.6lf MB\n", (&_ST_ - &_ED_) / 1024. / 1024.);
    read(n);
    read(m);
    for (rg i = 1; i <= n; ++i)
        read(a[i]), vst[a[i]] = 1;
    for (rg i = 1; i <= m; ++i)
    {
        read(q[i].op), read(q[i].l), read(q[i].r), read(q[i].x), (q[i].op == 1) && (read(q[i].y), 1);
        if (q[i].op == 1)
        {
            if (vst.find(q[i].x) == vst.end())
                in[i] = 1;
            else
                vst[q[i].y] = 1;
        }
    }
    for (rg i = 1; i <= n; ++i)
        b[++Mx] = a[i];
    for (rg i = 1; i <= m; ++i)
        (q[i].op == 1 && !in[i]) && (b[++Mx] = q[i].y);
    std::sort(b + 1, b + 1 + Mx);
    Mx = std::unique(b + 1, b + 1 + Mx) - b - 1;
    B = (n - 1) / 60 + 1;
    T = (Mx - 1) / 40 + 1;
    for (rg i = 1; i <= n; ++i)
        bl[i] = (i - 1) / B + 1;
    cb = bl[n];
    for (rg i = 1; i <= cb; ++i)
        lp[i] = rp[i - 1] + 1, rp[i] = i * B;
    rp[cb] = n;
    for (rg i = 1; i <= Mx + T; ++i)
        bx[i] = (i - 1) / T + 1;
#define Gv(x) (std::lower_bound(b + 1, b + 1 + Mx, x) - b)
    for (rg i = 1; i <= n; ++i)
        a[i] = Gv(a[i]);
    for (rg i = T, j = 1; i - T <= Mx; i += T, ++j)
        sz[j] = b[min(i, Mx)] - b[i - T];
    dsu::init(n);
    for (rg i = B, o = 1; o <= cb; i += B, ++o)
    {
        memcpy(ps[o], ps[o - 1], (Mx + 1) << 2);
        for (rg j = i - B + 1; j <= min(i, n); ++j)
        {
            cint v = a[j];
            ps[o][v] = j;
            rg &ro = pt[o][v];
            if (!ro)
                ro = j;
            else
                dsu::prt[j] = ro;
        }
        for (rg j = 1; j <= bx[Mx + T]; ++j)
            rn[o][j].c = cur, rn[o][j].lim = min(i, n), cur += rn[o][j].lim + 1;
        for (rg j = T, p = 1; j - T <= Mx; j += T, ++p)
        {
            tn = 0;
            for (rg k = j - T + 1; k <= j; ++k)
                if (ps[o][k])
                    stk[++tn] = ps[o][k];
            rn[o][p].bld();
        }
    }
    for (rg i = 1; i <= m; ++i)
    {
        if (q[i].op == 1)
        {
            if (!in[i])
                mdy(q[i].l, q[i].r, Gv(q[i].x), Gv(q[i].y));
        }
        else
            qry(q[i].l, q[i].r, q[i].x);
    }
    return fwrite(obuf, 1, OP1 - obuf, stdout), 0;
}
/*
std1:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cmath>
#include<map>
#include<string>
const int Q=100005;
const int P=200005;
const int O=35;
const int H=55;
const int INF=(1<<30);
typedef long long ll;
#define rg register int
#define cint const register int
const int SZ=1<<21;
char ibuf[SZ|5],*IP1=ibuf,*IP2=ibuf;
#define gc() (__builtin_expect(IP1==IP2,0)&&(IP2=(IP1=ibuf)+fread(ibuf,1,SZ,stdin),__builtin_expect(IP1==IP2,0))?EOF:*IP1++)
char obuf[SZ|5],*OP1=obuf;const char*OP2=obuf+SZ;
inline void pc(const char c){*OP1++=c;__builtin_expect(OP1==OP2,0)&&(fwrite(obuf,1,SZ,stdout),OP1=obuf);}
inline bool ig(const char c){return c>=48&&c<=57;}
inline void read(rg&oi){char c;rg f=1,res=0;while(c=gc(),(!ig(c))&&c^'-');c^'-'?res=(c^48):f=-1;while(c=gc(),ig(c))res=res*10+(c^48);oi=f*res;}
inline void print(rg oi){char io[23];rg l=0;if(oi<0)pc('-'),oi=~oi+1;do io[++l]=(oi%10+48);while(oi/=10);for(;l;--l)pc(io[l]);}
inline void write(cint oi,const char c){print(oi);pc(c);}char _ST_;
inline int min(cint x,cint y){return x<y?x:y;}
inline int max(cint x,cint y){return x>y?x:y;}
int n,m,a[Q],b[P],Mx,B,T,bl[Q],bx[P],cb,lp[Q],rp[Q];
struct oper{int op,l,r,x,y;oper()=default;}q[Q];bool in[Q];std::map<int,bool>vst;
int ps[O][P],rt[O][H],pt[O][P];
namespace dsu{
    int prt[Q];inline void init(cint N){for(rg i=1;i<=N;++i)prt[i]=i;}
    inline int Grt(cint x){return x^prt[x]?prt[x]=Grt(prt[x]):x;}
}
int ft[Q<<1],ct,sz[H],stk[Q],tn;
constexpr double alp=0.7;
constexpr int G=(1<<30)-1;
struct Scpt{
    struct scpt{int ls,rs,sz,rz,v;}t[Q<<1];int rb[Q<<1],rc,tot;
    inline void New(rg&x,cint y){t[x=rc?rb[rc--]:++tot]=(scpt){0,0,1,1,y|(1<<30)};}
    inline void upd(cint x){t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+1;
    t[x].rz=t[t[x].ls].rz+t[t[x].rs].rz+(t[x].v>>30);}
    inline void flt(cint x){if(!x)return;flt(t[x].ls);if(t[x].v>>30)ft[++ct]=x;else rb[++rc]=x;flt(t[x].rs);}
    inline int rbd(cint l,cint r){if(l==r)return 0;cint mid=l+r>>1,x=ft[mid];
    t[x].ls=rbd(l,mid);t[x].rs=rbd(mid+1,r);return upd(x),x;}
    inline void rbd(rg&x){ct=0;flt(x);x=rbd(1,ct+1);}
    inline bool nbd(cint x){return (t[x].v>>30)&&
    ((t[x].sz*alp<max(t[t[x].ls].sz,t[t[x].rs].sz))||t[x].rz<t[x].sz*alp);}
    inline void insert(rg&x,cint y){
        if(!x)return New(x,y);cint o=t[x].v&G;if(o==y)t[x].v|=1<<30;
        else insert(o<y?t[x].rs:t[x].ls,y);upd(x);if(nbd(x))rbd(x);
    }
    inline void erase(rg&x,cint y){
        if(!x)return;--t[x].rz;cint o=t[x].v&G;if(o==y)t[x].v-=1<<30;
        else erase(o<y?t[x].rs:t[x].ls,y);upd(x);if(nbd(x))rbd(x);
    }
    inline int qry(cint x,cint y){
        if(!x)return 0;cint o=(t[x].v&G);if(o==y)return t[t[x].rs].rz+(t[x].v>>30);
        return o>y?((t[x].rz-t[t[x].ls].rz)+qry(t[x].ls,y)):qry(t[x].rs,y);
    }
    inline void bld(rg&x){
        std::sort(stk+1,stk+1+tn);ct=tn;
        for(rg i=1;i<=tn;++i)New(ft[i],stk[i]);x=rbd(1,ct+1);
    }
};
Scpt rn[O];int cc[H],st[Q];bool vs[P];
inline void rbd(cint l,cint r,cint x,cint y){
    cint o=bl[l],L=lp[o],R=rp[o],vx=bx[x],vy=bx[y];
    cint tx=ps[o][x],ty=ps[o][y];
    pt[o][x]=pt[o][y]=ps[o][x]=ps[o][y]=0;rg top=0;
    for(rg i=L;i<=R;++i){a[i]=a[dsu::Grt(i)];
    if(a[i]==x||a[i]==y)st[++top]=i;}
    for(rg i=l;i<=r;++i)if(a[i]==x)a[i]=y;
    for(rg i=1;i<=top;++i){
        cint t=st[i],v=a[t];ps[o][v]=t;
        rg&ro=pt[o][v];if(!ro)ro=t;dsu::prt[t]=ro;
    }
    if(!ps[o][x])ps[o][x]=ps[o-1][x];if(!ps[o][y])ps[o][y]=ps[o-1][y];
    if(tx^ps[o][x])rn[o].erase(rt[o][vx],tx),rn[o].insert(rt[o][vx],ps[o][x]);
    if(ty^ps[o][y])rn[o].erase(rt[o][vy],ty),rn[o].insert(rt[o][vy],ps[o][y]);
}
inline void mdy(cint l,cint r,cint x,cint y){
    if(x==y)return;cint lb=bl[l],rb=bl[r],vx=bx[x],vy=bx[y];if(lb==rb){
        rbd(l,r,x,y);cint px=ps[lb][x],py=ps[lb][y];
        for(rg i=lb+1;i<=cb-1;++i){
            if(ps[i][x]>=l&&ps[i][x]<=r&&(ps[i][x]!=px)){
                rn[i].erase(rt[i][vx],ps[i][x]);ps[i][x]=px;
                if(px)rn[i].insert(rt[i][vx],px);
            }
            if(py&&(!ps[i][y]||ps[i][y]<py)){
                if(ps[i][y])rn[i].erase(rt[i][vy],ps[i][y]);ps[i][y]=py;
                rn[i].insert(rt[i][vy],py);
            }
        }
        return;
    }
    rbd(l,rp[lb],x,y);for(rg i=lb+1;i<=rb-1;++i){
        if(!pt[i][x]){
            if(ps[i][x]^ps[i-1][x]){if(ps[i][x])rn[i].erase(rt[i][vx],ps[i][x]);
            ps[i][x]=ps[i-1][x];if(ps[i][x])rn[i].insert(rt[i][vx],ps[i][x]);}
            if(ps[i][y]^ps[i-1][y]){if(!pt[i][y]){if(ps[i][y])rn[i].erase(rt[i][vy],ps[i][y]);
            ps[i][y]=ps[i-1][y];if(ps[i][y])rn[i].insert(rt[i][vy],ps[i][y]);}}continue;
        }
        if(!pt[i][y])pt[i][y]=pt[i][x],a[pt[i][y]]=y;
        else dsu::prt[pt[i][x]]=dsu::prt[pt[i][y]];
        if(ps[i][x])rn[i].erase(rt[i][vx],ps[i][x]);
        if(!ps[i][y]||(ps[i][y]<ps[i][x])){
            if(ps[i][y])rn[i].erase(rt[i][vy],ps[i][y]);
            ps[i][y]=ps[i][x];if(ps[i][y])rn[i].insert(rt[i][vy],ps[i][y]);
        }
        ps[i][x]=ps[i-1][x];if(ps[i][x])rn[i].insert(rt[i][vx],ps[i][x]);pt[i][x]=0;
    }
    rbd(lp[rb],r,x,y);cint px=ps[rb][x],py=ps[rb][y];
    for(rg i=rb+1;i<=cb-1;++i){
        if(ps[i][x]>=l&&ps[i][x]<=r&&(ps[i][x]!=px)){
            rn[i].erase(rt[i][vx],ps[i][x]);ps[i][x]=px;
            if(px)rn[i].insert(rt[i][vx],px);
        }
        if(py&&(!ps[i][y]||ps[i][y]<py)){
            if(ps[i][y])rn[i].erase(rt[i][vy],ps[i][y]);ps[i][y]=py;
            if(py)rn[i].insert(rt[i][vy],py);
        }
    }
}
inline void qry(cint l,cint r,rg k){
    cint o=bl[r]-1,p=rp[o];if(p<l){
        for(rg i=l;i<=r;++i){cint o=a[dsu::Grt(i)];if(!vs[o])++cc[bx[o]],vs[o]=1;}
        rg i=1,j=1;for(;j<=Mx;++i,j+=T){cint t=sz[i]-cc[i];if(t>=k)break;k-=t;}j=min(j,Mx+1);
        for(;k&&j<=i*T&&j<=Mx;++j){cint t=b[j]-b[j-1]-vs[j];if(t>=k)break;k-=t;}write(b[j-1]+k,'\n');
        for(rg i=l;i<=r;++i){cint o=a[dsu::Grt(i)];cc[bx[o]]=vs[o]=0;}return;
    }
    for(rg i=p+1;i<=r;++i){cint v=a[dsu::Grt(i)];if(!vs[v]&&ps[o][v]<l)++cc[bx[v]],vs[v]=1;}
    rg i=1,j=1;for(;j<=Mx;++i,j+=T){cint t=sz[i]-rn[o].qry(rt[o][i],l)-cc[i];if(t>=k)break;k-=t;}j=min(j,Mx+1);
    for(;k&&j<=i*T&&j<=Mx;++j){cint t=b[j]-b[j-1]-(vs[j]||ps[o][j]>=l);if(t>=k)break;k-=t;}write(b[j-1]+k,'\n');
    for(rg i=p+1;i<=r;++i){cint v=a[dsu::Grt(i)];cc[bx[v]]=vs[v]=0;}
}
char _ED_;int main(){
    fprintf(stderr,"static memory:%.6lf MB\n",(&_ST_-&_ED_)/1024./1024.);
    read(n);read(m);for(rg i=1;i<=n;++i)read(a[i]),vst[a[i]]=1;
    for(rg i=1;i<=m;++i){
        read(q[i].op),read(q[i].l),read(q[i].r),read(q[i].x),(q[i].op==1)&&(read(q[i].y),1);
        if(q[i].op==1){if(vst.find(q[i].x)==vst.end())in[i]=1;else vst[q[i].y]=1;}
    }
    for(rg i=1;i<=n;++i)b[++Mx]=a[i];
    for(rg i=1;i<=m;++i)(q[i].op==1&&!in[i])&&(b[++Mx]=q[i].y);
    std::sort(b+1,b+1+Mx);Mx=std::unique(b+1,b+1+Mx)-b-1;B=(n-1)/20+1;T=(Mx-1)/20+1;
    for(rg i=1;i<=n;++i)bl[i]=(i-1)/B+1;cb=bl[n];
    for(rg i=1;i<=cb;++i)lp[i]=rp[i-1]+1,rp[i]=i*B;rp[cb]=n;
    for(rg i=1;i<=Mx+T;++i)bx[i]=(i-1)/T+1;
#define Gv(x)(std::lower_bound(b+1,b+1+Mx,x)-b)
    for(rg i=1;i<=n;++i)a[i]=Gv(a[i]);
    for(rg i=T,j=1;i-T<=Mx;i+=T,++j)sz[j]=b[min(i,Mx)]-b[i-T];
    dsu::init(n);for(rg i=B,o=1;o<=cb;i+=B,++o){
        memcpy(ps[o],ps[o-1],(Mx+1)<<2);
        for(rg j=i-B+1;j<=min(i,n);++j){
            cint v=a[j];ps[o][v]=j;rg&ro=pt[o][v];
            if(!ro)ro=j;else dsu::prt[j]=ro;
        }
        for(rg j=T,p=1;j-T<=Mx;j+=T,++p){
            tn=0;for(rg k=j-T+1;k<=j;++k)
            if(ps[o][k])stk[++tn]=ps[o][k];rn[o].bld(rt[o][p]);
        }
    }
    for(rg i=1;i<=m;++i){
        if(q[i].op==1){if(!in[i])mdy(q[i].l,q[i].r,Gv(q[i].x),Gv(q[i].y));}
        else qry(q[i].l,q[i].r,q[i].x);
    }
    return fwrite(obuf,1,OP1-obuf,stdout),0;
}
*/

---