未来日记
纪念第一道自己独立想出Solution的Ynoi
题意：支持区间定值修改和区间第\(k\)大，数据范围\(10^5\)，空间限制\(512MB\)，时间限制\(1000ms\)
显然1e5是分块，考虑怎么做
区间定值修改，做过这个的人都知道使用冰茶姬和桶来支持
但显然，这题桶无法满足我们的需求，求第\(k\)大通用三个方法：可持久化线段树，树套树，值域分块优化莫队
这里前两个一看就是废物，值域分块貌似有优化的空间？
那么考虑使用值域分块来优化，一看lxl开的\(512MB\)，\(100\)%是对每个块开一个值域进行维护。
所以说，这时候就涉及到怎么搞的问题了
首先对于区间定值修改，整块直接把\(x\)位置删掉(冰茶姬维护siz，把其有的数插入到\(y\)的位置，并将冰茶姬连上
对于散块先暴力重构然后修改(冰茶姬归零)
再次对于区间第\(k\)大查询，怎么搞呢？
值域分块使得我们只需要快速地知道某个数出现次数就可以找\(k\)大了
总的做法：
按照套路：设\(sum[i][j]\)表示前\(i\)个序列块中前\(j\)个值域块里出现的次数总数，\(cnt[i][j]\)表示前\(i\)个序列块中数\(j\)出现次数总数
显然可以递推求解，复制前一个复杂度\(O(n)\)，总共\(O(\sqrt n)\)次。递推总计复杂度\(O(n)\)，所以总预处理复杂度\(O(n\sqrt n)\)
再考虑询问：对于这个块，可以先将散块开个桶统计，复杂度\(O(\sqrt n)\)，然后直接在整块两端进行差分统计，按照值域分块，一块一块地跳，找到块之后一个个找即可。
最后考虑修改怎么搞：我们以块内此数字第一次出现的位置的下标为代表元
设\(sit[i][j]\)表示第\(i\)个块第一个值为\(j\)的数的下标，\(id[i][j]\)表示第\(i\)个块代表元\(j\)所代表的的值(与\(f\)构成一对映射)，设\(f[i]\)表示冰茶姬
则\(a[x]=id[pos[x]][f[x]]\)，其中\(pos[x]\)表示\(x\)所属块编号
散块直接按照这个式子还原原序列然后暴力修改重构，并重新统计\(cnt,sum\)，由于只涉及两个值，所以复杂度\(O(\sqrt n)\)
对于整块，设当前第\(i\)个块：
-
区间没有\(x\)：跳过
-
区间有\(x\)没\(y\)，则\(sit[i][y]=sit[i][x],id[i][sit[i][x]]=y,sit[i][x]=0\)
-
有\(x\)还有\(y\)，非常麻烦，看上去只能暴力重构，事实上这是正确的。Why?
容易发现，每一个块进行某次操作，出现这种情况，会使得其维护值的个数少一。有操作2的存在，我们可以发现，维护值的个数是单调不增的，所以操作三实际上每个块只会执行\(O(\sqrt n)\)次，总复杂度\(O( n)\)，每个块的复杂度总和是\(O(n\sqrt n)\)级的。
这里我们忽视了一个问题：\(cnt,sum\)的更新问题
事实上，在块的后移的时候用变量tmp维护即可。
坑人的是：经过bdfs，我知道了，分块块长350,值域块块长317才能跑过……
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 105500
#define re register
#define S 375
int V=100000;
inline void read(int &x){
x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
int n,m,siz,a[N],tot,tt[N],L[S],R[S],pos_v[N],cnt1[S],cnt2[N],cnt[S][N],scnt[S][N],sum[S][S],f[N],sit[S][N],block,len_v=317;
inline int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
inline int get(int x){
return (x+block-1)/block;
}
inline void build(int id,int l,int r,int x,int y){
re int tmp=0;
tot=0;
sit[id][x]=sit[id][y]=0;
for(re int i=L[id];i<=R[id];i++){
a[i]=a[find(i)];
if(a[i]==x||a[i]==y)tt[++tot]=i;
}
for(re int i=l;i<=r;i++)if(a[i]==x)a[i]=y,tmp++;
cnt[id][x]-=tmp,cnt[id][y]+=tmp;
for(re int i=1;i<=tot;i++)f[tt[i]]=tt[i];
for(re int i=1;i<=tot;i++){
if(!sit[id][a[tt[i]]])sit[id][a[tt[i]]]=tt[i];
else f[tt[i]]=sit[id][a[tt[i]]];
}
for(int i=id;i<=siz;i++){
scnt[i][x]-=tmp,scnt[i][y]+=tmp;
if(pos_v[x]!=pos_v[y])sum[i][pos_v[x]]-=tmp,sum[i][pos_v[y]]+=tmp;
}
}
inline void change(int l,int r,int x,int y){
re int lpos=get(l),rpos=get(r);
if(lpos==rpos)build(lpos,l,r,x,y);
else {
build(lpos,l,R[lpos],x,y);
build(rpos,L[rpos],r,x,y);
int tmp=0;
for(re int i=lpos+1;i<rpos;i++){
if(sit[i][x]){
if(!sit[i][y])sit[i][y]=sit[i][x],a[sit[i][x]]=y;
else f[sit[i][x]]=sit[i][y];
sit[i][x]=0,tmp+=cnt[i][x],cnt[i][y]+=cnt[i][x],cnt[i][x]=0;
}
scnt[i][x]-=tmp,scnt[i][y]+=tmp;
if(pos_v[x]!=pos_v[y])sum[i][pos_v[x]]-=tmp,sum[i][pos_v[y]]+=tmp;
}
for(re int i=rpos;i<=siz;i++){
scnt[i][x]-=tmp,scnt[i][y]+=tmp;
if(pos_v[x]!=pos_v[y])sum[i][pos_v[x]]-=tmp,sum[i][pos_v[y]]+=tmp;
}
}
}
inline int query(int l,int r,int k){
re int lpos=get(l),rpos=get(r),cnt=0;
if(lpos==rpos){
for(re int i=l;i<=r;i++)a[i]=a[find(i)],cnt1[pos_v[a[i]]]++,cnt2[a[i]]++;
for(re int i=1;i<=len_v;i++){
cnt+=cnt1[i];
if(cnt>=k){
cnt-=cnt1[i];
for(re int j=(i-1)*len_v+1;j<=i*len_v;j++){
cnt+=cnt2[j];
if(cnt>=k){
for(re int i=l;i<=r;i++)cnt2[a[i]]--,cnt1[pos_v[a[i]]]--;
return j;
}
}
}
}
}
else {
for(re int i=l;i<=R[lpos];i++)a[i]=a[find(i)],cnt1[pos_v[a[i]]]++,cnt2[a[i]]++;
for(re int i=L[rpos];i<=r;i++)a[i]=a[find(i)],cnt1[pos_v[a[i]]]++,cnt2[a[i]]++;
for(re int i=1;i<=len_v;i++){
cnt+=cnt1[i]+sum[rpos-1][i]-sum[lpos][i];
if(cnt>=k){
cnt-=cnt1[i]+sum[rpos-1][i]-sum[lpos][i];
for(re int j=(i-1)*len_v+1;j<=i*len_v;j++){
cnt+=cnt2[j]+scnt[rpos-1][j]-scnt[lpos][j];
if(cnt>=k){
for(re int i=l;i<=R[lpos];i++)cnt1[pos_v[a[i]]]--,cnt2[a[i]]--;
for(re int i=L[rpos];i<=r;i++)cnt1[pos_v[a[i]]]--,cnt2[a[i]]--;
return j;
}
}
}
}
}
}
int main() {
read(n);read(m);
for(re int i=1;i<=n;i++){
read(a[i]);f[i]=i;
}
block=350,siz=(n+block-1)/block;
for(re int i=1;i<=V;i++)pos_v[i]=(i-1)/len_v+1;
for(re int i=1;i<=siz;i++){
L[i]=R[i-1]+1,R[i]=min(L[i]+block-1,n);
for(re int j=L[i];j<=R[i];j++){
if(!sit[i][a[j]])sit[i][a[j]]=j;
else f[j]=sit[i][a[j]];
cnt[i][a[j]]++;
}
}
for(re int i=1;i<=siz;i++){
for(re int j=1;j<=len_v;j++)sum[i][j]=sum[i-1][j];
for(re int j=L[i];j<=R[i];j++)sum[i][pos_v[a[j]]]++;
for(re int j=1;j<=V;j++)scnt[i][j]=scnt[i-1][j]+cnt[i][j];
}
while(m--){
re int opt,x,y,l,r,k;
read(opt);
if(opt==1){
read(l),read(r),read(x),read(y);
if(x==y)continue;//114514
change(l,r,x,y);
}
else {
read(l),read(r),read(k);
printf("%d\n",query(l,r,k));
}
}
return 0;
}