石家庄网站建设人员,请谁做网站比较放心,wordpress多合一seo包,手机旅游网站建设一、题目大意
给我们一些闭区间[ai , bi]#xff0c;其中 1 ai bi 50000#xff0c;让我们求出一个集合#xff0c;使得这个集合与 区间 [ai , bi]有 ci个共同元素#xff0c;对于所有的 1i n个区间而言。
二、解题思路
根据题目范围#xff0c…一、题目大意
给我们一些闭区间[ai , bi]其中 1 ai bi 50000让我们求出一个集合使得这个集合与 区间 [ai , bi]有 ci个共同元素对于所有的 1i 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 设置为5000750000以上则为废弃节点因为大于所有的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 pairint, 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;
}
四、运行情况
