记录编号	611368	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 Final] 列队	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	61.419 s
提交时间	2026-01-28 23:21:01	内存使用	21.98 MiB

#include <bits/stdc++.h>

using uint = unsigned;

const uint Lim=200000,B=500;
uint n,m,q,cnt;
uint A[Lim+5],P[Lim+5],L[Lim+5],bid;
uint Cnt[Lim/B+5][Lim+5],CCnt[Lim/B+5][Lim+5];
int main()
{
    freopen("thupc_2025_linesort.in", "r", stdin);
    freopen("thupc_2025_linesort.out", "w", stdout);
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    scanf("%u%u%u",&n,&m,&q);
    for(uint i=0;i<n;i++)for(uint j=0;j<m;j++)scanf("%u",A+i*m+j),P[--A[i*m+j]]=i*m+j,cnt+=j&&A[i*m+j-1]>A[i*m+j];
    for(uint i=0;i<n*m;i++)L[i]=P[i]/m;
    for(uint i=0;i<n*m;i++)
    {
        if(!(i%B))
        {
            for(uint j=0;j<n;j++)Cnt[bid+1][j]=Cnt[bid][j];
            for(uint j=0;j<m;j++)CCnt[bid+1][j]=CCnt[bid][j];
            bid++;
        }
        CCnt[bid][Cnt[bid][L[i]]++]++;
    }
    while(q--)
    {
        uint o;scanf("%u",&o);
        if(o==1)
        {
            uint x1,y1,x2,y2;scanf("%u%u%u%u",&x1,&y1,&x2,&y2),x1--,y1--,x2--,y2--;
            if(x1==x2&&y1==y2)continue;
            if(y1>y2)std::swap(y1,y2),std::swap(x1,x2);
            if(y1)cnt-=A[x1*m+y1-1]>A[x1*m+y1];
            if(y1<m-1)cnt-=A[x1*m+y1+1]<A[x1*m+y1];
            if(y2&&(x1!=x2||y1+1!=y2))cnt-=A[x2*m+y2-1]>A[x2*m+y2];
            if(y2<m-1)cnt-=A[x2*m+y2+1]<A[x2*m+y2];
            uint a=A[x1*m+y1],b=A[x2*m+y2];std::swap(P[a],P[b]),std::swap(L[a],L[b]),std::swap(A[P[a]],A[P[b]]);
            if(y1)cnt+=A[x1*m+y1-1]>A[x1*m+y1];
            if(y1<m-1)cnt+=A[x1*m+y1+1]<A[x1*m+y1];
            if(y2&&(x1!=x2||y1+1!=y2))cnt+=A[x2*m+y2-1]>A[x2*m+y2];
            if(y2<m-1)cnt+=A[x2*m+y2+1]<A[x2*m+y2];
            if(L[a]==L[b])continue;
            if(a>b)std::swap(a,b);
            for(uint j=a/B+1;j<=b/B;j++)--CCnt[j][--Cnt[j][L[b]]],CCnt[j][Cnt[j][L[a]]++]++;
        }
        else
        {
            uint x,y;scanf("%u%u",&x,&y),x--,y--;if(!cnt){printf("%u\n",A[x*m+y]+1);continue;}
            uint p=0;while(CCnt[p+1][y]<=x)p++;
            uint t=CCnt[p][y];
            p*=B;
            while(t<=x)
            {
                if(Cnt[p/B][L[p]]++==y)t++;
                p++;
            }
            printf("%u\n",p);
            do p--,Cnt[p/B][L[p]]--;while(p%B);
        }
    }
    return 0;
}