My code's time complexity is right. But the constant is so large that it's TLE. Who can help me.
#include<cstdio>
#define N 100005
#define NN 135
#define _ 800
int n,m,a[N],va[N],p[N],cnt[N],cnt2[NN];
struct kuai{
int v[NN],va[N],vc[NN],vac[N];
int r[N];
}k[NN];
inline void reco(){
for(int i=0;i<NN;i++)k[0].vc[i]=k[0].v[i];
for(int i=0;i<N;i++)k[0].vac[i]=k[0].va[i];
for(int i=1;i<NN;i++){
for(int j=0;j<NN;j++)k[i].vc[j]=k[i-1].vc[j]+k[i].v[j];
for(int j=0;j<N;j++)k[i].vac[j]=k[i-1].vac[j]+k[i].va[j];
}
}
inline void recoo(int x,int y){
k[0].vc[x/_]=k[0].v[x/_];
k[0].vc[y/_]=k[0].v[y/_];
k[0].vac[x]=k[0].va[x];
k[0].vac[y]=k[0].va[y];
for(int i=1;i<NN;i++){
k[i].vc[x/_]=k[i].v[x/_]+k[i-1].vc[x/_];
k[i].vc[y/_]=k[i].v[y/_]+k[i-1].vc[y/_];
k[i].vac[x]=k[i].va[x]+k[i-1].vac[x];
k[i].vac[y]=k[i].va[y]+k[i-1].vac[y];
}
}
int qu(int now){
if(p[now]!=now)p[now]=qu(p[now]);
return p[now];
}
bool bb[100005],b2[100005];
inline void rebuild(int id,int x,int y,int l,int r){//printf("(%d %d %d)",id,l,r);
if(l>r)return;
k[id].v[x/_]-=k[id].va[x];
k[id].va[x]=k[id].r[x]=0;
for(int i=id*_;i<(id+1)*_&&i<=n;i++){
if(va[qu(i)]==x&&i>=l&&i<=r)bb[i]=1;
else if(va[qu(i)]==x)b2[i]=1;
}
for(int i=id*_;i<(id+1)*_&&i<=n;i++){
if(bb[i]){
if(!k[id].r[y])k[id].r[y]=i,va[i]=y;
p[i]=k[id].r[y];
k[id].v[y/_]++;
k[id].va[y]++;
bb[i]=0;
}
else if(b2[i]){
if(!k[id].r[x])k[id].r[x]=i,va[i]=x;
p[i]=k[id].r[x];
k[id].v[x/_]++;
k[id].va[x]++;
b2[i]=0;
}
}
}
inline void read(int &a)
{
a=0;char c;
while((c=getchar())<48);
do a=(a<<3)+(a<<1)+(c^48);
while((c=getchar())>47);
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void gor(int ll,int rr,int x,int y){
for(int i=ll;i<=rr;i++){
if(k[i].r[y])p[k[i].r[x]]=k[i].r[y];
else k[i].r[y]=k[i].r[x],va[k[i].r[y]]=y;
k[i].r[x]=0;
int tt=k[i].va[x];
k[i].v[x/_]-=tt;
k[i].va[x]-=tt;
k[i].v[y/_]+=tt;
k[i].va[y]+=tt;
}
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
int nowk=i/_,kn=a[i]/_;
k[nowk].va[a[i]]++;
k[nowk].v[kn]++;
if(!k[nowk].r[a[i]]) k[nowk].r[a[i]]=i,va[i]=a[i];
p[i]=k[nowk].r[a[i]];
}
reco();
while(m--){
int op,l,r,K,x,y;
read(op),read(l),read(r);
if(op==2){
read(K);
bool b=0;
int ll=-1,rr=-1;
for(int i=l;i<=r;i++){
if(i%_==0){
ll=i/_;
break;
}
//printf("^%d",va[qu(i)]);
cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++;
if(i==r)b=1;
}
if(!b)for(int i=r;i>=l;i--){
if((i+1)%_==0){
rr=i/_;
break;
}
cnt[va[qu(i)]]++,cnt2[va[qu(i)]/_]++;
}
if((ll==-1||rr==-1)||ll>rr){
int dd=0,sum=0;
for(int i=0;i<NN;i++){
if(sum+cnt2[i]>=K)break;
sum+=cnt2[i];dd+=_;
}
for(;;dd++){
if(sum+cnt[dd]>=K){
write(dd);
break;
}
sum+=cnt[dd];
}
}
else{
int dd=0,sum=0;
for(int i=0;i<NN;i++){
if(sum+cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i]>=K)break;
sum+=cnt2[i]+k[rr].vc[i]-k[ll-1].vc[i];dd+=_;
}
for(;dd<N;dd++){
if(sum+cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd]>=K){
write(dd);
break;
}
sum+=cnt[dd]+k[rr].vac[dd]-k[ll-1].vac[dd];
}
}
for(int i=l;i<=r;i++){
if(i%_==0)break;
cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0;
}
for(int i=r;i>=l;i--){
if((i+1)%_==0)break;
cnt[va[qu(i)]]=0,cnt2[va[qu(i)]/_]=0;
}
putchar('\n');
}
else{
read(x),read(y);
if(x==y)continue;
int ll=(l-1)/_+1,rr=(r+1)/_-1;
if(ll>rr+1){
rebuild(rr+1,x,y,l,r);
recoo(x,y);
continue;
}
rebuild(ll-1,x,y,l,ll*_-1);
rebuild(rr+1,x,y,(rr+1)*_,r);
gor(ll,rr,x,y);
recoo(x,y);
}
}
}
