我的个人记载
  • About Me
不知名小站
Never Give Up
  1. 首页
  2. 数据结构
  3. 线段树
  4. 正文

小石的妹子

2020年07月09日 77点热度 0人点赞 0条评论

题意:
小石有 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;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 离散化 线段树
最后更新:2020年08月12日

框框

喜欢算法,喜欢编程。

打赏 点赞
< 上一篇

文章评论

取消回复

框框

喜欢算法,喜欢编程。

文章归档
  • 2020年10月
  • 2020年8月
  • 2020年7月
  • 2020年1月
  • 2019年11月
  • 2019年8月
  • 2019年7月
分类目录
  • 2008年哈尔滨区域赛
  • 2018焦作网络赛
  • Greater New York Region 2014
  • kuangbin并查集专题
  • Kuangbin数论专题
  • NZPC 2017
  • upc个人训练赛
  • 位运算
  • 博弈论
  • 多校训练
  • 搜索
  • 数据结构
  • 数论
  • 杭电多校训练第五场
  • 深入理解计算机基础/CSAPP
  • 算法模板
  • 线段树

COPYRIGHT © 2020 我的个人记载. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

苏ICP备19034952号-1