刷题记录:牛客NC26253小石的妹子

传送门:牛客

题目描述:

小石有 n 个妹子，每个妹子都有一个细心程度 a i和一个热心程度 b i，小石想给她们一个重要程度 t i
 （重要程度为 1 表示最重要，重要程度越小表示越重要）。
如果一个妹子 i 的细心程度和热心程度都比妹子 j 大，那么妹子 i 的重要程度要大于妹子 j 的重要程度，即妹子 i 比妹子 j 重要。
流程如下：
每次从所有没有重要程度的妹子中，找到若干妹子。对于这些妹子的任意一个，需要保证没有其他妹
子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹
子，依然符合上述条件，然后把她们的重要程度标为 2，……，重复直到所有妹子都有自己的重要程
度。
由于妹子太多，小石忙不过来，请你帮帮他。
输入:
5
1 4
2 2
3 3
4 1
5 5
输出:
2
3
2
2
1

说实话第一眼看到这道题,我的想法是进行拓扑排序,因为对于题意来说,我们只要将重要程度严格有序(严格有序表示细心程度和热心程度都比另一个大)的两个妹子进行连边,然后跑一个拓扑排序即可.对于任意两个点如果没有成严格有序或者间接有序按照拓扑排序正确性也可以得到保证.

但是…这道题的$n$达到了$1e5$,所以我们的拓扑排序卡在了$n^2$建边上, 靠!!.

但是拓扑排序的想法并不是没用的,我们可以顺着这个想法来.我们发现我们知道,一个点的排名,在拓扑排序中是由之前比这个点严格大的点递推过来的,也就是找到一个比他严格大的点的最大的一个排名,然后由这个排名进行加一.那么我们此时就有一个想法了,我们不妨将数列按照细心程度(也就是ai)进行从大到小排序,那么对于一个点$j$来说,$aj$肯定小于前面$ai$.那么此时如果前面的点的$bi$大于$bj$的话,此时$i$肯定严格大于$j$.并且在$j$后面的所有点肯定不会存在一个点严格大于$j$.所以此时我们的$j$的排名就是前面所有$bi$大于$bj$的点的排名的最大值加一.

那么此时我们的问题就变成了如何快速找到比$bj$大的点的最大的排名.此时我们可以使用线段树进行维护,对于每一个点,我们都将其$bi$的大小放入我们的线段树中,用线段树来维护区间最大值即可

但是因为$bi$的最大值达到了$1e9$,无法直接使用线段树进行维护,所以我们需要先进行离散化(具体离散化操作可以参考代码)

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{
	int l,r,mx;
}tree[maxn*4];
struct Girl{
	int a,b,id;
}girl[maxn];
int n;
vector<int>v;
void build(int l,int r,int rt) {
	tree[rt].l=l;tree[rt].r=r;
	if(l==r) {
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
}
void update(int pos,int rt,int v) {
	if(tree[rt].l==pos&&tree[rt].r==pos) {
		tree[rt].mx=v;
		return ;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(pos<=mid) update(pos,ls,v);
	else update(pos,rs,v);
	tree[rt].mx=max(tree[ls].mx,tree[rs].mx);
}
int query(int l,int r,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		return tree[rt].mx;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) return query(l,r,ls);
	else if(l>mid) return query(l,r,rs);
	else return max(query(l,mid,ls),query(mid+1,r,rs));
}
bool cmp(Girl aa,Girl bb) {
	return aa.a>bb.a;
}
int ans[maxn];
int main() {
	n=read();
	for(int i=1;i<=n;i++) {
		girl[i].a=read();girl[i].b=read();girl[i].id=i;
		v.push_back(girl[i].b);
	}
	sort(girl+1,girl+n+1,cmp);
	//离散化操作
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int Size=v.size();
	build(1,Size,1);
	for(int i=1;i<=n;i++) {
		int get_id=lower_bound(v.begin(),v.end(),girl[i].b)-v.begin()+1;
		ans[girl[i].id]=query(get_id,Size,1)+1;
		update(get_id,1,ans[girl[i].id]);
	}
	for(int i=1;i<=n;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}