POJ 1201 Intervals 线段树

本文主要是介绍POJ 1201 Intervals 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目大意

给我们一些闭区间[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;
}