跳到主要内容

Card Pile Query

· 阅读需 2 分钟

容易想到我们其实只需要更新修改两个点的相对位置就可以表示清楚一整段的变化

所以写一个链表，每次更新移动最后暴力寻找每堆上的数的个数即可

AC代码
Details
/*
类链表操作 
记录每个点的上面和下面是哪个，对于所有的堆去操作就行 
只有down是负数的说明是堆底，并标记着号码 
*/
#include<bits/stdc++.h>
using namespace std;
#define QAQ return 
#define QWQ return 0;
#define ll long long
#define pii pair< int,int >

const int N=3e5+10;

int up[N], down[N];
int start[N];

int main()
{
//	freopen( "txt.in","r",stdin );
//	freopen( "txt.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n, q;
	cin>>n>>q;
	for( int i=1;i<=n;i++ ) up[i]=0, down[i]=-i;
	for( int i=1, x, y;i<=q;i++ )
	{
		cin>>x>>y;
		//x放到y上面 
		if( down[x] >= 0 ) up[down[x]]=0;//防止下标乱飞 
		up[y]=x, down[x]=y;
	}
	for( int i=1;i<=n;i++ ) if( down[i] < 0 ) start[-down[i]]=i;
	for( int i=1;i<=n;i++ )
	{
		int ans=0, now=start[i];
		while( now ) ans++, now=up[now];
		cout<<ans<<" ";
	}
	QWQ;
}

时间复杂度：O(n)O(n)