P10225 [COCI 2023/2024 #3] Milano C.le 题解

知识点

栈，贪心，树状数组。

题意分析

求最小的栈的数量使得出入栈能够合法。

思路分析

我们为了方便，其实可以先按照到达车站的顺序（入栈顺序）给火车重新编号。编号后，就十分简单了。

分析样例：

5
3 5 2 4 1
3 2 5 1 4

编号后，就变成了：

5
1 2 3 4 5
4 5 3 1 2

然后我们对 4 5 3 1 2 的出栈序列进行倒推，就又变成了一个入栈序列，且我们获得了很多的限制条件。

在倒推序列时，假设现在加入 \(i\)，它必须接在一个小于它且已经进入序列并作为栈顶的数后面，或者独立成栈。

实例：2 5 4 1 3 的出栈序列。

1. 入 3，先独立成栈；
2. 入 1，没有小于它的数，独立成栈；
3. 入 4，有两个小于它的栈顶，分别是 1 3。考虑贪心，尽量选大的那个，然后就可以为后面的留下小的。这里选 3；
4. 入 5，有两个小于它的栈顶，分别是 1 4。依照前文，这里选 4；
5. 入 3，有1个小于它的栈顶，是 1。注意到如果之前没有留下栈顶 1，这里就要再多成立一个栈了。

那么共成了两个栈，答案也就是 2。

我们找小于一个数的最大值，可以用树状数组倍增，时间复杂度 \(O(n\log_2{n})\)。

（记得在栈中加入一个数后，要把原本的栈顶删除。）

CODE

#include<bits/stdc++.h>
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=2e5+10;
int n,ans;
int a[N],b[N];
struct BIT{
#define lowbit(a) ((a)&-(a))
	int c[N];
	void Update(int x,int d){
		for(int i=x;i<=n;i+=lowbit(i))c[i]+=d;
	}
	int Query(int x){
		int res=0;
		for(int i=x;i;i^=lowbit(i))res+=c[i];
		return res;
	}
	int Bound(int x){
		int ans=0,sum=0;
		DOR(i,18,0)if(ans+(1<<i)<=n&&sum+c[ans+(1<<i)]<x)ans+=1<<i,sum+=c[ans];
		return ans+1;
	}
#undef lowbit
}B;
signed main(){
	cin>>n;
	FOR(i,1,n)cin>>a[i];
	FOR(i,1,n)cin>>b[a[i]];
	FOR(i,1,n)cout<<b[i]<<" ";cout<<endl;
	DOR(i,n,1){
		int ret=B.Query(b[i]);
		if(!ret)++ans;
		else B.Update(B.Bound(ret),-1);
		B.Update(b[i],1);
	}
	cout<<ans<<endl;
	return 0;
}