My code's time complexity is right. But the constant is so large that it's TLE. Who can help me.↵
↵
```cpp↵
↵
#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);↵
}↵
}↵
}↵
↵
```
↵
```cpp↵
↵
#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);↵
}↵
}↵
}↵
↵
```
