代码

#include<bits/stdc++.h>
#define cnt(x,c) (s[x][c]-s[x][c-1])
using namespace std;
int const B=370,N=100000,C=100005/B+1;
int n,a[100005],bel[100005],s[100005][C],s2[C][C],
id[100005][C],rid[100005][C],b[100005],t1[100005],t2[100005],c1[C],c2[C];
void rebuild(int c,int x,int y)
{
    int l=(c-1)*B+1,r=min(n,c*B),smod=0;
    for(int i=l;i<=r;i++)
    {
        b[i]=a[i],a[i]=id[a[i]][c];
        if(a[i]==x)a[i]=y,smod++;
    }
    for(int i=l;i<=r;i++)rid[id[b[i]][c]][c]=0,id[b[i]][c]=0;
    for(int i=l;i<=r;i++)id[a[i]][c]=rid[a[i]][c]=a[i];
    for(int i=c;i<=bel[n];i++)s[x][i]-=smod,s[y][i]+=smod,s2[bel[x]][i]-=smod,s2[bel[y]][i]+=smod;
}
void rebuild(int c,int x,int y,int L,int R)
{
    int l=(c-1)*B+1,r=min(n,c*B),smod=0;
    for(int i=l;i<=r;i++)b[i]=a[i],a[i]=id[a[i]][c];
    for(int i=l;i<=r;i++)rid[id[b[i]][c]][c]=0,id[b[i]][c]=0;
    for(int i=L;i<=R;i++)if(a[i]==x)a[i]=y,smod++;
    for(int i=l;i<=r;i++)id[a[i]][c]=rid[a[i]][c]=a[i];
    for(int i=c;i<=bel[n];i++)s[x][i]-=smod,s[y][i]+=smod,s2[bel[x]][i]-=smod,s2[bel[y]][i]+=smod;
}
namespace input
{
    const int InputBufferSize=(1<<23)+5;
    char buffer[InputBufferSize],*s,*eof;
    inline void init()
    {
        assert(stdin!=NULL);
        s=buffer;
        eof=s+fread(buffer,1,InputBufferSize,stdin);
    }
    inline bool read(int &x)
    {
        x=0;
        while(!isdigit(*s))s++;
        if(eof<=s)return false;
        while(isdigit(*s))x=x*10+*s++-'0';
        return true;
    }
}
using input::init,input::read;
int main()
{
    int ttt=clock();
    //init();
    int q,op,l,r,x,y;
    n=100000,q=100000;
	  default_random_engine random(time(0));
    uniform_int_distribution<int>rnd(1,n);
    for(int i=1;i<=N;i++)bel[i]=(i-1)/B+1;
    for(int i=1;i<=n;i++)a[i]=rnd(random),s[a[i]][bel[i]]++,id[a[i]][bel[i]]=rid[a[i]][bel[i]]=a[i];
    for(int i=1;i<=N;i++)
        for(int j=1;j<=bel[n];j++)
            s[i][j]+=s[i][j-1],s2[bel[i]][j]+=s[i][j];
    while(q--)
    {
        op=2,l=rnd(random),r=rnd(random),x=rnd(random);
		   if(l>r)swap(l,r);
        if(op==1)
        {
            read(y);
            if(x==y)continue;
            if(bel[l]==bel[r]){rebuild(bel[l],x,y,l,r);continue;}
            int smod=0;
            for(int i=bel[l]+1;i<bel[r];i++)c1[i]=cnt(x,i),c2[i]=cnt(y,i);
            rebuild(bel[l],x,y,l,bel[l]*B);
            rebuild(bel[r],x,y,(bel[r]-1)*B+1,r);
            for(int i=bel[l]+1;i<bel[r];i++)
            {
                if(!c1[i]);
                else if(!c2[i])smod+=c1[i],id[rid[x][i]][i]=y,rid[y][i]=rid[x][i],rid[x][i]=0;
                else rebuild(i,x,y);
                s[x][i]-=smod,s[y][i]+=smod,s2[bel[x]][i]-=smod,s2[bel[y]][i]+=smod;
            }
            for(int i=bel[r];i<=bel[n];i++)s[x][i]-=smod,s[y][i]+=smod,s2[bel[x]][i]-=smod,s2[bel[y]][i]+=smod;
        }
        else
        {
            if(bel[l]==bel[r])
            {
                for(int i=l;i<=r;i++)b[i]=id[a[i]][bel[l]];
                nth_element(b+l,b+l+x-1,b+r+1);
                //printf("%d\n",b[l+x-1]);
            }
            else
            {
                int L=bel[l]*B,R=(bel[r]-1)*B+1,u=bel[l],v=bel[r];
                for(int i=l;i<=L;i++)t1[id[a[i]][u]]++,t2[bel[id[a[i]][u]]]++;
                for(int i=R;i<=r;i++)t1[id[a[i]][v]]++,t2[bel[id[a[i]][v]]]++;
                int t;
                for(t=1;t<=bel[N];t++)
                    if(s2[t][v-1]-s2[t][u]+t2[t]>=x)break;
                    else x-=s2[t][v-1]-s2[t][u]+t2[t];
                for(int i=(t-1)*B+1;i<=t*B;i++)
                    if(s[i][v-1]-s[i][u]+t1[i]>=x)break;//{printf("%d\n",i);break;}
                    else x-=s[i][v-1]-s[i][u]+t1[i];
                for(int i=l;i<=L;i++)t1[id[a[i]][u]]=0,t2[bel[id[a[i]][u]]]=0;
                for(int i=R;i<=r;i++)t1[id[a[i]][v]]=0,t2[bel[id[a[i]][v]]]=0;
            }
        }
    }
    cout<<clock()-ttt;
    return 0;
}

评测结果