题意:
小石有 n 个妹子,每个妹子都有一个细心程度 ai 和一个热心程度 bi,
小石想给她们一个重要程度 ti(重要程度为 1 表示最重要,重要程度越小表示越重要)。如果一个妹子 i 的细心程度和热心程度都比妹子 j 大,那么妹子 i 的重要程度要大于妹子 j 的重要程度,即妹子 i 比妹子 j 重要。
流程如下:
每次从所有没有重要程度的妹子中,找到若干妹子。对于这些妹子的任意一个,需要保证没有其他妹子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹子,依然符合上述条件,然后把她们的重要程度标为 2,……,重复直到所有妹子都有自己的重要程度。
由于妹子太多,小石忙不过来,请你帮帮他。
输入描述:
第一行输入一个正整数 n,表示妹子的数量。
接下来 n 行,每行两个正整数 ai,bi,描述每个妹子的细心程度和热心程度。
保证所有的 ai 两两不等,所有的 bi 两两不等。
输出描述:
共 n 行,第 i 行输出一个正整数 ti 表示第 i 个妹子的重要程度。
样例输入:
5
1 4
2 2
3 3
4 1
5 5
样例输出:
2
3
2
2
1
题解:
先按照a从大到小排序,对于第i个女生,她的rk[i] = max({rk[j]}) + 1 (b[j] > b[i])
其中max({rk[j]})是在现有的b[j]比b[i]大的女生中rk最大的那个值。
所以线段树维护最大值,b[i]为下标,rk[i]为值,线段树初始化为0,每次单点更新。由于b的范围大,需要首先离散化。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rd(a) scanf("%d", &a)
#define al(x) x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;
struct node1{
int l, r;
int v;
}tr[maxn << 2];
int n;
int d[maxn];
int rk[maxn];
struct node2{
int a, b, id;
}x[maxn];
bool cmp(node2 x, node2 y){
return x.a > y.a;
}
void pushup(int u){
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r){
tr[u] = {l, r};
if(l == r){
tr[u] = {l, r, 0};
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int x, int v){
if(tr[u].l == x && tr[u].r == x){
tr[u].v = v;
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r){
return tr[u].v;
}
int mid = tr[u].l + tr[u].r >> 1;
int ans = 0;
if(l <= mid) ans = query(u << 1, l, r);
if(r > mid) ans = max(ans, query(u << 1 | 1, l, r));
return ans;
}
int main(){
rd(n);
rap(i, 1, n){
rd(x[i].a), rd(x[i].b);
x[i].id = i;
d[i] = x[i].b;
}
sort(al(x), cmp);
sort(al(d));
int m = unique(al(d)) - (d + 1);
rap(i, 1, n){
x[i].b = lower_bound(d + 1, d + m + 1, x[i].b) - d;
}
build(1, 1, n);
rap(i, 1, n){
rk[x[i].id] = query(1, x[i].b, n) + 1;
update(1, x[i].b, rk[x[i].id]);
}
rap(i, 1, n){
printf("%d\n", rk[i]);
}
return 0;
}
文章评论