12062

myee · 2025-04-08 21:22:29 · 题解

前言

出题人题解。

其实是军训的时候整出来的 idea……

这题原本可能是今年的省选题，不过一月的时候因为一些原因我主动撤下了，于是塞进了 THUPC 中。（快说：谢谢 Itst）

命题会上大家发现这似乎是唯一一道能用的 ds 了，所以就毫无疑问地选上了。

实际赛时居然没人写正解，全去写根号分治然后卡常了……

我寻思着这题开了 7 倍 std 时限而且 std 还没卡过常，不知道为啥这么多人还要卡常。

本题应该会有 Ynoi ver.，只保留做法中的第二种情况并开大数据范围卡常。

思路

首先注意到一个小结论：最多排序两次。

为什么？观察到如果矩阵只有 0 和 1，那这点是显然的。

对于矩阵中的每个数，我们考虑把比其小的赋值为 0，其余都赋值为 1，那么显然也满足这点。于是直接得证。

由于第二次就退出和第二次排序后第三次退出对矩阵形态的实践行为是一样的，我们实际上只用分为两种情况：

• 一次也没排序。
• 恰好排序了两次。

至于是哪种情况，我们只用维护每行是否分别有序就行。也就是我们只用维护每个行内相邻的元素是否均有序。

这个是容易做到 O(1) 的。哪怕比较懒用 set 也是 O(\log(nm)) 的。没有特意卡这部分常数，但是要注意一些代码细节，比如交换操作刚好交换相邻元素。

分辨出是哪种情况后，由于第一种情况就是输出矩阵对应位置元素，直接维护矩阵形态即可，显然是 O(1) 的。

于是接下来我们只用考虑第二种情况。这种情况实际上是在求：假设各行分别取出第 y 小的数，求出这些数中第 x 小的。

一种很基础的思路是根号分治，场上确实大家都是这么写的。但是这个做法非常难写，所以我们这里换个思路。

注意到本题始终保持了排列的性质，于是考虑反过来维护每个数在矩阵中对应的行号。那么问题就变成了找到最小的位置，使得这个这个位置之前出现了至少 y 次的数有 x 个。

这个显然是可以直接分块维护的。具体地，我们设 B 为块长，取 0,B,2B,3B,\cdots 为间断点，那么我们只用维护每个间断点之前的所有元素的出现次数，及每种出现次数被多少种数达到即可。

信息维护与查询较为简单，不作赘述了。总之取 B=\Theta(\sqrt{nm}) 后本题总复杂度是 O((q+nm)\sqrt{nm}) 的。

值得一提的是，如果允许离线，就算不保证是排列，该做法也仍旧适用。

Code

// ぼたぼたと
// しゃりしゃりと
// うとうとと
// はらはらと
// ぱりぱりと
// しんしんと
// この世界を閉ざした
// 今もひとり宇宙を覗き込んだまま
#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()
{
#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;
}