to路过的大佬：【LGR-204】T3求条

已老实，求放过

#include <cstdio>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0;
    char c = getchar();
    while (c<'0'||'9'<c) c = getchar();
    while ('0'<=c&&c<='9') x = x*10+c-'0',c = getchar();
    return x;
}
const int MAXN = 2e6 + 12;
int cnt = 0;
int a[23][MAXN],n,m,q,mp[MAXN];
bool sorted[23];
int tot[MAXN],toid[MAXN],lst[23][MAXN];
struct node
{
    int v;
    int i,j;
    bool operator<(const node&rhs) const{
        return v<rhs.v;
    }
}N[MAXN];
struct treeNode
{
    int sum[23],lz[23];
}*T[23];
void buildTree(int l,int r,int x,int k)
{
    if (r<l) return ;
    for (int i=1;i<=m;i++) T[x][k].lz[i] = T[x][k].sum[i] = 0;
    T[x][k].sum[x] = r-l+1;
    if (l==r) 
    {
        return ;
    }
    int md = (l+r)>>1;
    buildTree(l,md,x,k*2),buildTree(md+1,r,x,k*2+1);
}
void pushdown(int x,int k)
{
    for (int i=1;i<=m;i++) 
    {
        if (sorted[i]==0) continue;
        if (T[x][k].lz[i]==0) continue;
        T[x][k*2].lz[i] = T[x][k].lz[i];
        T[x][k*2+1].lz[i] = T[x][k].lz[i];
        T[x][k*2].sum[T[x][k].lz[i]] += T[x][k*2].sum[i];
        T[x][k*2+1].sum[T[x][k].lz[i]] += T[x][k*2+1].sum[i];
        T[x][k*2].sum[i] = 0;
        T[x][k*2+1].sum[i] = 0;
        T[x][k].lz[i] = 0;
    }
}
int ask(int l,int r,int x,int k,int L,int R,int tar)
{
    if (r<l) return 0;
    pushdown(x,k);
    if (L<=l&&r<=R) return T[x][k].sum[tar];
    else if (l>R||r<L) return 0;
    int md = (l+r)>>1;
    return ask(l,md,x,k*2,L,R,tar)+ask(md+1,r,x,k*2+1,L,R,tar);
}
void change(int l,int r,int x,int k,int L,int R,int tar1,int tar2)
{
    //printf("%d %d %d\n",l,r,k);
    if (r<l) return ;
    pushdown(x,k);
    if (L<=l&&r<=R) 
    {
        T[x][k].sum[tar2] += T[x][k].sum[tar1];
        T[x][k].sum[tar1] = 0;
        T[x][k].lz[tar1] = tar2;
        return ;
    }
    else if (l>R||r<L) return ;
    int md = (l+r)>>1;
    change(l,md,x,k*2,L,R,tar1,tar2),change(md+1,r,x,k*2+1,L,R,tar1,tar2);
    for (int i=1;i<=m;i++) 
        if (sorted[i]) T[x][k].sum[i] = T[x][k*2].sum[i] + T[x][k*2+1].sum[i];
}
void init(int x)
{
    sorted[x] = 1;
    sort(a[x]+1,a[x]+n+1);
    for (int i=1;i<=n;i++)
    {
        tot[a[x][i]] = x;
        toid[a[x][i]] = i;
    }
    for (int i=1;i<=cnt;i++)
    {
        lst[x][i] = (tot[i]==x)? toid[i]:lst[x][i-1];
    }
    buildTree(1,n,x,1);
}
int count(int x,int v) 
{
    int res = 0;
    for (int i=1;i<=m;i++)
    {
        if (sorted[i]==0) continue;
        res += ask(1,n,i,1,1,lst[i][v],x);
    }
    return res;
}
void work1(int x,int y)
{
    if (sorted[x]==0) init(x);
    if (sorted[y]==0) init(y);
    int l=1,r=cnt,md,ans;
    while (l<=r)
    {
        md = (l+r)>>1;
        if (count(x,md)+count(y,md)<=n) ans = md,l = md+1;
        else r = md-1;
    }
    for (int i=1;i<=m;i++)
        if(sorted[i]) change(1,n,i,1,1,lst[i][ans],y,x),change(1,n,i,1,lst[i][ans]+1,n,x,y);
}
void work2(int i,int j)
{
    if (sorted[i]==0)
    {
        printf("%d\n",mp[a[i][j]]);
        return ;
    }
    int l=1,r=cnt,md,ans;
    while (l<=r)
    {
        md = (l+r)>>1;
        if (count(i,md)>=j) ans = md,r = md-1;
        else l = md+1;
    }
    printf("%d\n",mp[ans]);

}
int main()
{
    n=read(),m=read(),q=read();
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++) 
        {
            a[i][j] = read();
            cnt++;
            N[cnt].v=a[i][j],N[cnt].i=i,N[cnt].j=j;
        }

    sort(N+1,N+cnt+1);
    for (int i=1;i<=cnt;i++)
    {
        mp[i] = N[i].v;
        a[N[i].i][N[i].j] = i;
    }
    for (int i=1;i<=m;i++) T[i] = new treeNode[n*8+12];
    while (q--)
    {
        int op,i,j;
        op = read(),i=read(),j=read();
        if (op==1) work1(i,j);
        else if(op==2) work2(i,j);
    }
    for (int i=1;i<=m;i++) delete T[i];
    return 0;
}