P12062 列队 题解
来篇
首先有一个很关键的性质：按行排序与按列排序至多只会进行一次
考虑证明：若进行了第二次排序，则意味着按列排序后出现了一个位置，使得其右侧的值比当前位置更小。不妨对按行排序后相邻的两列考虑，此时若再进行列排序，则形成的相邻对的情况则是 两列元素从大到小排序后，大小排名相同 的元素相匹配，而对于左排列中每个元素而言，在右排列中大于其的元素的数量显然大于等于它的排名(左排列中比其大的元素都会贡献一个比其大的右排列元素)，所以不会产生左大于右的相邻对。
接下来就好办了，考虑维护这两次操作后的影响即可，观察到数据范围中有
情况一： m \le \sqrt{N}
因为
考虑查询，我们考虑 大步小步算法 的过程，具体的，我们从值域最小处开始向大跳跃，一开始先一个块一个块(
于是我们就做到了
情况二： n < \sqrt{N}
考虑查询怎么做，我们可以枚举每一行求出他们的第 nth_element )。
而修改等价于对某行进行增删元素，要求能做到
在这里提出一种新的分块结构(雾)，我称之为 朝鲜块状链表 ，具体的，我们对外部的块使用数组进行维护，块内元素使用 vector 维护，查询时即可在外部的块使用二分查找，修改是平凡的，但是修改次数过多可能会导致块长不平衡，所以我们借用 朝鲜树 的思想，每进行
于是我们就做到了
注意事项
注意当每一行都已经有序时，列排序则不会进行，所以需要进行特判，具体的可以记录一个 cnt 代表整个矩阵中
码丑，勿喷（
#include<bits/stdc++.h>
// #define fp_on
#define ll long long
#define pii pair<int,int>
#define db double
#define fi first
#define se second
using namespace std;
const int Max=2.5e5+5,Mod=998244353,inf=0x7fffffff,bMax=500;
namespace mygr{
ll qpow(ll a,ll b){
ll ans=1;
while(b)
{ if(b&1)
ans=(ans*a)%Mod;
a=(a*a)%Mod;b>>=1;
}return ans;}
ll read()
{
char c=getchar();
ll w=1,a=0;
while(!isdigit(c)){
if(c=='-')w=-1;
c=getchar();}
while(isdigit(c)){
a=a*10+c-'0';
c=getchar();}
return a*w;
}
struct graph{
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx=0;
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
};
template<class T>
struct vector2{
T x,y;
vector2()
{x=y=0;}
vector2(T xx,T yy)
{x=xx;y=yy;}
friend vector2 operator + (vector2 A,vector2 B)
{return vector2(A.x+B.x,A.y+B.y);}
friend vector2 operator - (vector2 A,vector2 B)
{return vector2(A.x-B.x,A.y-B.y);}
friend T operator * (vector2 A,vector2 B)
{return A.x*B.y-A.y*B.x;}
friend T dot(vector2 A,vector2 B)
{return A.x*B.x+A.y*B.y;}
};
int Turn(int num)
{return (num%Mod+Mod)%Mod;}
int lowbit(int num)
{return num&(-num);}
}
using namespace mygr;
const int B=400;
int CB;
struct Blo{
int p[Max],S[Max];
int qs()
{
int ans=0;
for(int i=0;i<=bMax;i++)
ans+=S[i];
return ans;
}
void upd(int pos,int num)
{
int ps=pos/B;
p[pos]+=num;
S[ps]+=num;
}
void upd(int l,int r,int num)
{
int np=l/B;
int i=l;
for(;i/B==np and i<=r;i++)
p[i]+=num;
if(i>r)return ;
for(;i/B!=r/B;i+=B)
S[i/B]+=num;
for(;i<=r;i++)
p[i]+=num;
}
int query(int k)
{
int now=0;
while(k>S[now])
{
k-=S[now];
now++;
}
now=now*B;
while(k>p[now])
{
k-=p[now];
now++;
}
return now;
}
int qry(int pos)
{
return p[pos]+S[pos];
}
}T[bMax];
struct Blo_list{
int tot,cntq;
struct node{
int l;
vector<int> v;
}p[bMax];
void rebuild()
{
CB++;
vector<int> d;
for(int i=1;i<=tot;i++)
{
for(auto j : p[i].v)
d.push_back(j);
p[i].v.clear();
}
tot=1;
p[1].l=1;
for(auto i : d)
{
if(p[tot].v.size()>=B)
{
tot++;
p[tot].l=p[tot-1].l+p[tot-1].v.size();
}
p[tot].v.push_back(i);
}
}
void del(int num)
{
cntq++;
if(cntq>=B)
rebuild(),cntq=0;
int now=1;
while(now<tot and p[now+1].v[0]<=num)
now++;
p[now].v.erase( lower_bound(p[now].v.begin(),p[now].v.end(),num) );
if(p[now].v.size()<=0)
{
if(now==tot)
tot--;
else
rebuild();
return ;
}
now++;
for(;now<=tot;now++)
p[now].l--;
}
void add(int num)
{
cntq++;
if(cntq>=B)
rebuild(),cntq=0;
int now=1;
while(now<tot and p[now+1].v[0]<=num)
now++;
p[now].v.insert( lower_bound(p[now].v.begin(),p[now].v.end(),num) ,num );
now++;
for(;now<=tot;now++)
p[now].l++;
}
int qry(int k)
{
int l=1,r=tot;
while(l<r)
{
int mid=(l+r+1)>>1;
if(p[mid].l<=k)
l=mid;
else
r=mid-1;
}
return p[l].v[k-p[l].l];
}
}P[bMax];
int n,m,q;
int *a[Max],*s[Max];
int buf[Max*4],bufs[Max*4];
void init(int* A[],int Bf[])
{
for(int i=0;i<=n;i++)
A[i]=&(Bf[i*(m+1)]);
}
int cnt;
void updc(int x,int y,int op)
{
if(y<=0 or y>=m)return ;
cnt+=op*(a[x][y]>a[x][y+1]);
}
void updnr(int x,int y,int op)
{
updc(x,y-1,op);
updc(x,y,op);
}
void solve1()
{
init(s,bufs);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=a[i][j]=read();
for(int i=1;i<=n;i++)
sort(s[i]+1,s[i]+m+1);
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
updc(i,j,1);
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
T[j].upd(s[i][j],1);
while(q--)
{
if(read()==1)
{
int X1=read(),Y1=read(),X2=read(),Y2=read();
if(X1==X2 and Y1==Y2)
continue;
for(int i=1;i<=m;i++)
{
T[i].upd(s[X1][i],-1);
if(X1!=X2)T[i].upd(s[X2][i],-1);
}
updnr(X1,Y1,-1);updnr(X2,Y2,-1);
if(X1==X2 and abs(Y1-Y2)==1){cnt+=(a[X1][min(Y1,Y2)]>a[X2][max(Y1,Y2)]);}
swap(a[X1][Y1],a[X2][Y2]);
updnr(X1,Y1,1);updnr(X2,Y2,1);
if(X1==X2 and abs(Y1-Y2)==1){cnt-=(a[X1][min(Y1,Y2)]>a[X2][max(Y1,Y2)]);}
for(int i=1;i<=m;i++)
{
s[X1][i]=a[X1][i];
s[X2][i]=a[X2][i];
}
sort(s[X1]+1,s[X1]+m+1);
sort(s[X2]+1,s[X2]+m+1);
for(int i=1;i<=m;i++)
{
T[i].upd(s[X1][i],1);
if(X1!=X2)T[i].upd(s[X2][i],1);
}
}
else
{
int x=read(),y=read();
if(cnt==0)
printf("%d\n",a[x][y]);
else
{
int ans=T[y].query(x);
printf("%d\n",ans);
}
}
}
}
int Buf[Max];
void solve2()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
updc(i,j,1);
for(int i=1;i<=n;i++)P[i].tot=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
P[i].p[1].v.push_back(a[i][j]);
for(int i=1;i<=n;i++)
{
sort(P[i].p[1].v.begin(),P[i].p[1].v.end());
P[i].rebuild();
}
while(q--)
{
if(read()==1)
{
int X1=read(),Y1=read(),X2=read(),Y2=read();
if(X1==X2 and Y1==Y2)
continue;
P[X1].del(a[X1][Y1]);
P[X2].del(a[X2][Y2]);
updnr(X1,Y1,-1);updnr(X2,Y2,-1);
if(X1==Y1 and abs(Y1-Y2)==1){cnt+=(a[X1][min(Y1,Y2)]>a[X2][max(Y1,Y2)]);}
swap(a[X1][Y1],a[X2][Y2]);
updnr(X1,Y1,1);updnr(X2,Y2,1);
if(X1==Y1 and abs(Y1-Y2)==1){cnt-=(a[X1][min(Y1,Y2)]>a[X2][max(Y1,Y2)]);}
P[X1].add(a[X1][Y1]);
P[X2].add(a[X2][Y2]);
}
else
{
int x=read(),y=read();
if(cnt==0)
printf("%d\n",a[x][y]);
else
{
for(int i=1;i<=n;i++)
Buf[i]=P[i].qry(y);
nth_element(Buf+1,Buf+x,Buf+n+1);
printf("%d\n",Buf[x]);
}
}
}
}
//#define fp_on
signed main()
{
#ifdef fp_on
freopen("62.in","r",stdin);
freopen("mygr.out","w",stdout);
#endif
n=read();m=read();q=read();
init(a,buf);
if(m<=n)
solve1();
else
solve2();
}