Portal: Niu Ke

Title description:

Koishi has n Every girl has a degree of care a i and a level of enthusiasm b i，Xiaoshi wanted to give them a level of importance t i
 (An importance of 1 means the most important, and a lower importance means more important).
if a girl i She is more careful and enthusiastic than girls j Big, so girl i is more important than girls j The importance of the girl i Bimeizi j important.
The process is as follows:
Every time, find some girls from all the girls who are not important. For any one of these girls, it is necessary to ensure that there are no other girls
 Son is more important than her. Then mark their importance as 1 . Next time, I will find a few girls from the remaining girls who are not important
 girls, still meet the above conditions, and then mark their importance as 2, ..., repeat until all girls have their own importance
 Spend.
Because there are too many girls, Xiaoshi is too busy, please help him.
enter:
5
1 4
2 2
3 3
4 1
5 5
 output:
2
3
2
2
1

To be honest, when I saw this question at first glance, my idea was to perform topological sorting, because for the meaning of the question, we only need to strictly order the importance (strict order means that the degree of care and enthusiasm are greater than the other) The two sisters of the node are connected, and then run a topological sort. For any two points, if they are not in strict order or indirect order, the correctness of topological sorting can also be guaranteed.

But... this question n n n reached 1 e 5 1e5 1e5, so our topological sort is stuck at n 2 n^2 n2 is built on the side, rely on!!.

But the idea of ​​topological sorting is not useless, we can follow this idea. We found that we know that the ranking of a point in topological sorting is recursively derived from the previous points that are strictly larger than this point, that is Find the largest ranking of a point that is strictly larger than him, and then add one to this ranking. Then we have an idea at this time, we might as well sort the sequence from large to small according to the degree of care (that is, ai) , then for a point j j For j, a j aj aj must be smaller than the previous a i ai ai. At this time, if the previous point b i bi bi is greater than b j bj bj words, at this time i i i must be strictly greater than j j j. and in j j All the points after j will definitely not have a point strictly greater than j j j. So at this time our j j The ranking of j is all the previous b i bi bi is greater than b j bj The maximum value of the rank of the point of bj plus one.

Then our problem at this time becomes how to quickly find the ratio b j bj The largest ranking of points with large bj. At this point we can use the line segment tree for maintenance. For each point, we will b i bi Put the size of bi into our line segment tree, and use the line segment tree to maintain the maximum value of the interval

But because b i bi The maximum value of bi is reached 1 e 9 1e9 1e9, the line segment tree cannot be used directly for maintenance, so we need to perform discretization first (for specific discretization operations, please refer to the code)

The following is the specific code part:

#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);
	//discretization operation
	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;
}