牛客小白月赛16 小石的妹子 二分 or 线段树

牛客小白月赛16

这个题目我AC之后看了一下别人的题解，基本上都是线段树，不过二分也可以。

这个题目很自然就肯定要对其中一个进行排序，排完序之后再处理另外一边，另一边记得离散化。

怎么处理呢，你仔细想想，找找规律就可以发现，其实我们就是在找递增子序列。

第一次找到的就是重要程度为1 的妹子，然后删除这些元素，继续第二次找，第二次找到的就是重要程度为二的妹子。

所以到每一个点，我们就只要根据它的大小来判断它应该放的位置（尽量靠前，并且小于这个数），然后更新这个位置，再返回这个位置，它所在的位置就是它的重要程度。

emmm  其实就是用一个数组，数组的每一个位置 i 存的就是到目前位置重要程度为 i 的最大值。

具体看代码吧。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e5 + ;

typedef long long ll;

int num[maxn];

map<ll, ll>mp;

struct node

{

    int l, r;

    int sum;

}tree[*maxn];

struct edge

{

    ll a, b, id, num, ans;

}ex[maxn];

bool cmp(edge a,edge b)

{

    return a.a > b.a;

}

bool cmp1(edge a,edge b)

{

    return a.b < b.b;

}

bool cmp2(edge a,edge b)

{

    return a.id < b.id;

}

int tot = ;

int ok(ll x)

{

    if (x > num[]) return ;

    if (x < num[tot])

    {

        tot++;

        return tot;

    }

    int l = , r = tot, ans = ;

    int mid = (l + r) >> ;

    while (l <= r) {

        int mid = (l + r) / ;

        if (num[mid]<x) ans = mid, r = mid - ;

        else l = mid + ;

    }

    return ans;

}

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        scanf("%lld%lld", &ex[i].a, &ex[i].b), ex[i].id = i;

    }

    sort(ex + , ex +  + n, cmp1);

    for (int i = ; i <= n; i++) mp[ex[i].b] = i;

    sort(ex + , ex +  + n, cmp);

    num[] = mp[ex[].b];

    ex[].ans = ;

    tot = ;

    for(int i=;i<=n;i++)

    {

        int f = ok(mp[ex[i].b]);

        // printf("%lld ex[%d]=%lld f=%d\n",mp[ex[i].b], i, ex[i].b, f);

        num[f] = mp[ex[i].b];

        ex[i].ans = f;

    }

    sort(ex + , ex +  + n, cmp2);

    for (int i = ; i <= n; i++) printf("%lld\n", ex[i].ans);

    return ;

}

二分

网上的线段树的方法我感觉和逆序对有点像，就是首先还是把 b 离散化，然后对 a 进行排序，

然后从 1 ~ n 遍历，如果对于每一个 b 首先判断 b ~ n 有没有值，其实就是有没有比 b 大的再前面放过了，有的话就去最大值，重要程度就是 最大值+1 （这个是因为存进去的就是最大值）

没有那么重要程度就是 1 ，然后再更新这个点 b 把 b 的重要程度放到线段树的 b 这个位置以便后面的查询。

这个很好写的。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <string>

#include <iostream>

#include <map>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 2e5 + ;

typedef long long ll;

map<ll, ll>mp;

struct node

{

    int l, r;

    int num;

}tree[*maxn];

struct edge

{

    ll a, b, id, num, ans;

}ex[maxn];

bool cmp(edge a,edge b)

{

    return a.a > b.a;

}

bool cmp1(edge a,edge b)

{

    return a.b < b.b;

}

bool cmp2(edge a,edge b)

{

    return a.id < b.id;

}

void build(int id, int l, int r) {

    tree[id].l = l;

    tree[id].r = r;

    if (l == r) {

        tree[id].num = ;

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

}

int query(int id, int x, int y) {

    int l = tree[id].l;

    int r = tree[id].r;

    if (x <= l && y >= r) {

        //    printf("id=%d sum=%d \n", id,tree[id].sum);

        return tree[id].num;

    }

    int ans = ;

    int mid = (l + r) >> ;

    if (x <= mid) ans = max(ans, query(id << , x, y));

    if (y > mid) ans = max(ans, query(id <<  | , x, y));

    //    printf("id=%d ans=%d l=%d r=%d x=%d y=%d \n", id, ans, l, r,x,y);

    return ans;

}

void push_up(int id) {

    tree[id].num = max(tree[id << ].num , tree[id <<  | ].num);

}

void update(int id, int x,int val) {

    int l = tree[id].l;

    int r = tree[id].r;

    if (l == r) {

        tree[id].num = val;

        return;

    }

    int mid = (l + r) >> ;

    if (x <= mid) update(id << , x,val);

    else update(id <<  | , x,val);

    push_up(id);

}

int main()

{

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        scanf("%lld%lld", &ex[i].a, &ex[i].b), ex[i].id = i;

    }

    sort(ex + , ex +  + n, cmp1);

    for (int i = ; i <= n; i++) mp[ex[i].b] = i;

    sort(ex + , ex +  + n, cmp);

    build(, , n);

    for(int i=;i<=n;i++)

    {

        int f = query(, mp[ex[i].b], n) + ;

        ex[i].ans = f;

        update(, mp[ex[i].b],f);

    }

    sort(ex + , ex +  + n, cmp2);

    for (int i = ; i <= n; i++) printf("%lld\n", ex[i].ans);

    return ;

}

逆序对 线段树

牛客小白月赛16 小石的妹子 二分 or 线段树的相关教程结束。