专栏文章

P12062 列队 题解

mmygr
P12062题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnigvz
此快照首次捕获于
2025/12/03 14:53
3 个月前
此快照最后确认于
2025/12/03 14:53
3 个月前
查看原文
来篇 O(qNlog⁡N+qN)O(q\sqrt{N}\log{\sqrt{N}} + q\sqrt{N}) 的不优秀题解。
首先有一个很关键的性质：按行排序与按列排序至多只会进行一次
考虑证明：若进行了第二次排序，则意味着按列排序后出现了一个位置，使得其右侧的值比当前位置更小。不妨对按行排序后相邻的两列考虑，此时若再进行列排序，则形成的相邻对的情况则是 两列元素从大到小排序后，大小排名相同 的元素相匹配，而对于左排列中每个元素而言，在右排列中大于其的元素的数量显然大于等于它的排名(左排列中比其大的元素都会贡献一个比其大的右排列元素)，所以不会产生左大于右的相邻对。
接下来就好办了，考虑维护这两次操作后的影响即可，观察到数据范围中有 N=n×m≤2×105N=n \times m \le 2 \times 10^5 ，很自然的想到根号分治。

情况一： m≤Nm \le \sqrt{N}

因为 mm 很小，所以考虑记录下每一行 行排序 后的结果，修改时直接暴力排序即可，而查询等价于询问行排序后，第 yy 列中第 xx 小的元素，考虑一个 O(1)O(1) 修改，O(n)O(\sqrt{n}) 查询的做法，我们对每一列用一个值域分块维护某值域区间内数的个数，修改则直接在对应位置和对应块上加减即可。
考虑查询，我们考虑 大步小步算法 的过程，具体的，我们从值域最小处开始向大跳跃，一开始先一个块一个块( +n+\sqrt n )的跳跃，直到当前的前缀和大于查询的排名，然后转为一格一格( +1+1 )的跳，这样就能做到 O(n)O(\sqrt n) 的查询。
于是我们就做到了 O(qNlog⁡N+qN)O(q\sqrt{N}\log{\sqrt{N}} + q\sqrt{N}) 的复杂度。

情况二： n<Nn < \sqrt{N}

考虑查询怎么做，我们可以枚举每一行求出他们的第 yy 小的元素，然后答案即为这些元素中第 xx 小的值( 使用 nth_element )。
而修改等价于对某行进行增删元素，要求能做到 O(m)O(\sqrt m) 修改 O(log⁡m)O(\log \sqrt m) 查询，考虑块状链表，但是块状链表的查询是 m\sqrt m 的，瓶颈在于外部链表的遍历，怎么优化呢？
在这里提出一种新的分块结构(雾)，我称之为 朝鲜块状链表 ，具体的，我们对外部的块使用数组进行维护，块内元素使用 vector 维护，查询时即可在外部的块使用二分查找，修改是平凡的，但是修改次数过多可能会导致块长不平衡，所以我们借用 朝鲜树 的思想，每进行 q\sqrt{q} 次询问则对整个块状链表进行重构，在 n,qn,q 同阶时则可以做到均摊 O(n)O(\sqrt{n}) 的修改。
于是我们就做到了 O(qNlog⁡N+qN)O(q\sqrt{N}\log{\sqrt{N}} + q\sqrt{N}) 的复杂度。

注意事项

注意当每一行都已经有序时，列排序则不会进行，所以需要进行特判，具体的可以记录一个 cnt 代表整个矩阵中 ai,j>ai,j+1a_{i,j}>a_{i,j+1} 的对的数量，若询问时有 cnt=0cnt=0 则直接输出 ax,ya_{x,y} 即可。
码丑，勿喷（
CPP
#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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...