当前位置：首页 > article >正文

POJ 1201 Intervals 线段树

article 2024/9/21 14:48:17

一、题目大意

给我们一些闭区间[ai , bi]，其中 1 <= ai <= bi <= 50000，让我们求出一个集合，使得这个集合与区间 [ai , bi]有 ci个共同元素，对于所有的 1<=i <=n个区间而言。

二、解题思路

根据题目范围，我们可以对 1到50000的数字进行循环，然后每次循环中用线段树进行操作，O(n*logn)的复杂性时间上可行。

1、我们可以把所有的区间按照区间的起点进行排序，然后计算出每个区间的 bi - ci + 1，用线段树维护各个区间的 bi - ci + 1的最小值。

2、针对每次循环的数字 num，只需要用二分确定 ai 小于等于它的范围 R，然后从线段树中查询出其中最小的 bi - ci + 1，如果 bi - ci + 1 == num，代表这个数字需要被选择，答案加一，同时需要更新线段树上的[0 , R) 内所有的 bi - ci + 1 值为原来的值 + 1

3、每次循环 num后，判断 num 是否等于某个区间的 bi，如果等于，则将对应的 bi 在线段树上的节点的 bi - ci + 1 设置为50007（50000以上则为废弃节点，因为大于所有的num），然后循环向上更新父节点即可。

本题目的线段树需要实现以下两个功能。

1、查询 [0 , R)的 bi - ci + 1的最小值

2、更新[0, R)范围内所有的 bi - ci + 1

那么我们需要让线段树上保存两个值

1、[0, R)区间内集体加上的值(dat)

2、[0 , R)内去掉第1点剩余部分的最小值(rmq)。

这样对于查询操作时，只需要加上所有父节点及自己的 dat，和自身的rmq即可。

对于更新操作时，只需要更新自己的dat，

并递归所有父节点的 rmq[parent]=min(rmq[lch]+dat[lch],rmq[rch]+dat[rch])即可。

总结：每次利用RMQ求出 a1 <= num范围内的 bi - ci + 1的最小值，与num进行比较，即可知道这个数字是需要选择，接下来在树上废弃掉 bi <= num的节点即可不会被已经经过的区间影响，同时如果这个数字被选择，更新 a1 <= num的全部节点为原来的值+1，这样代表这些区间内都加入了一个有效元素，以为下次循环做铺垫。

三、代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
P sortByA[50007], sortByB[50007];
int rmq[131072], dat[131072], a[50009], b[50009], c[50009], n, _current, maxt, ans;
void input()
{
    scanf("%d", &n);
    maxt = 0, ans = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        maxt = max(maxt, b[i]);
        sortByA[i].first = a[i];
        sortByA[i].second = i;
    }
    sort(sortByA, sortByA + n);
    for (int i = 0; i < n; i++)
    {
        sortByB[i].first = b[sortByA[i].second];
        sortByB[i].second = i;
    }
    sort(sortByB, sortByB + n);
}
void build(int i, int l, int r)
{
    if (r - l == 1)
    {
        rmq[i] = b[sortByA[l].second] - c[sortByA[l].second] + 1;
    }
    else
    {
        int lch = i * 2 + 1;
        int rch = i * 2 + 2;
        build(lch, l, (l + r) / 2);
        build(rch, (l + r) / 2, r);
        rmq[i] = min(rmq[lch], rmq[rch]);
    }
}
int query(int _l, int _r, int i, int l, int r)
{
    if (_l >= r || _r <= l)
    {
        return 50007;
    }
    else if (l >= _l && r <= _r)
    {
        return rmq[i] + dat[i];
    }
    else
    {
        if (dat[i] > 50000)
        {
            return dat[i];
        }
        int lch = query(_l, _r, i * 2 + 1, l, (l + r) / 2);
        int rch = query(_l, _r, i * 2 + 2, (l + r) / 2, r);
        return min(lch, rch) + dat[i];
    }
}
void update(int _l, int _r, int i, int l, int r, int v)
{
    if (_l >= r || _r <= l)
    {
    }
    else if (l >= _l && r <= _r)
    {
        dat[i] += v;
        int j = i;
        while (j > 0)
        {
            j = (j - 1) / 2;
            rmq[j] = min(rmq[j * 2 + 1] + dat[j * 2 + 1], rmq[j * 2 + 2] + dat[j * 2 + 2]);
        }
    }
    else
    {
        update(_l, _r, i * 2 + 1, l, (l + r) / 2, v);
        update(_l, _r, i * 2 + 2, (l + r) / 2, r, v);
    }
}
void solveItem()
{
    int idx = upper_bound(sortByA, sortByA + n, P(_current, 0x3f3f3f3f)) - sortByA;
    if (idx <= 0)
    {
        return;
    }
    int mint = query(0, idx, 0, 0, n);
    if (mint == _current)
    {
        update(0, idx, 0, 0, n, 1);
        ans++;
    }
    int past = lower_bound(sortByB, sortByB + n, P(_current, -0x3f3f3f3f)) - sortByB;
    for (int j = past; j < n; j++)
    {
        if (sortByB[j].first != _current)
        {
            break;
        }
        update(sortByB[j].second, sortByB[j].second + 1, 0, 0, n, 50007);
    }
}
void solve()
{
    for (int i = 0; i <= maxt; i++)
    {
        _current = i;
        solveItem();
    }
}
int main()
{
    input();
    build(0, 0, n);
    solve();
    printf("%d\n", ans);
    return 0;
}