F.Multi-Colored Segments
题意:
给定 \(n \left(n\leq2 * 10^5\right)\) 个有颜色的线段 \(\left[l, r, c\right]\left(1 \leq l, r \leq 10 ^ 9, 1 \leq c\leq n\right)\) .请计算对于每一个线段,与他颜色不同的线段的最短距离。
定义线段的距离为:如果两个线段相交(有重合的地方),则距离为 \(0\) 。否则为两个端点之间的最小差。例如上图中,线段3和线段5的距离为 \(5 – 2 = 3\) 。线段 \(1\) 和线段 \(2\) 相交,距离为 \(0\)
思路:
对于计算线段之间的距离,要先知道这个线段有没有被覆盖过,可以考虑给同种颜色的线段在他们所在的区间内打上一个标记。由于数据比较大,所以考虑离散化,并且按照颜色的种类进行离散化,这样可以保证我们所存下的左右边界不重不漏的将该种颜色包含进来。并且既然离散化了,可以考虑用线段树来给一个区间打标记,也就是做一个区间加法的操作,当这个区间的值大于 \(1\) 时,代表有不同种的线段重叠,当区间的值等于 \(1\) 的时候代表只有一个线段占据这个区间,当这个区间的值等于 \(0\) 时,代表这个区间没有线段覆盖。
int n;
std::cin >> n;
std::multiset<int> ls, rs; // 存储左端点,右端点
std::vector<std::array<int, 2>> range(n + 1); // 离散化后的左右边界
std::vector<std::vector<int>> idr(n + 1); // 存储颜色的种类
int cnt = 0;
int nums[4 * n + 1] {};
std::vector<std::array<int, 3>> seg(n + 1);
for (int i = 1; i <= n; i++) {
int l, r, c;
std::cin >> l >> r >> c;
seg[i] = {l, r, c};
range[i] = {l, r};
idr[c].push_back(i);
nums[++cnt] = l, nums[++cnt] = r;
ls.insert(l), rs.insert(r);
}
std::sort(nums + 1, nums + cnt + 1);
cnt = std::unique(nums + 1, nums + 1 + cnt) - nums - 1;
SegTree<Info, Tag> SGT(std::vector<Info> (cnt, Info(0, 1)));
std::vector<i64> ans(n + 1, 1E9);
for (int i = 1; i <= n; i++) {
range[i][0] = std::lower_bound(nums + 1, nums + 1 + cnt, range[i][0]) - nums;
range[i][1] = std::lower_bound(nums + 1, nums + 1 + cnt, range[i][1]) - nums;
SGT.modify(range[i][0], range[i][1], 1);
}
后面计算距离的时候,就是三步:将当前颜色的线段取出来;判断这个线段的区间内是否有线段覆盖,并计算左端点到左边最近一个有线段覆盖的区间和右端点到右边最近一个有线段覆盖的区间的距离;将线段重新加回去。
for (int i = 1; i <= n; i++) {
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
ls.erase(ls.lower_bound(ll));
rs.erase(rs.lower_bound(rr));
SGT.modify(cl, cr, -1);
}
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
if (SGT.query(cl, cr).sum) {
ans[id] = 0;
continue;
}
auto it = ls.lower_bound(ll);
if (it != ls.end()) {
ans[id] = std::min(ans[id], 1ll * std::max(0, *it - rr));
}
auto IT = rs.upper_bound(rr);
if (IT != rs.begin()) {
IT = std::prev(IT);
ans[id] = std::min(ans[id], 1ll * std::max(0, ll - *IT));
}
}
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
ls.insert(ll), rs.insert(rr);
SGT.modify(cl, cr, 1);
}
}
for (int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i == n];
完整代码:
struct Info{
i64 sum; int len;
Info() : sum(0), len(0) {}
Info(i64 sum, int len) : sum(sum), len(len) {}
};
using Tag = i64;
Info operator+(const Info &a, const Info &b){
return {a.sum + b.sum, a.len + b.len};
}
void apply(Info &x, Tag &a, Tag f){
x.sum += x.len * f;
a += f;
}
template<class Info, class Tag, class Merge = std::plus<Info>>
struct SegTree{
const int n;
const Merge merge;
std::vector<Info> info;
std::vector<Tag> tag;
SegTree(int n) : n(n), merge(Merge()), info((n << 2) + 1), tag((n << 2) + 1) {}
SegTree(std::vector<Info> init) : SegTree((int)init.size()){
std::function<void(int, int, int)> build = [&](int p, int l, int r){
if (l == r){
info[p] = init[l - 1];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p){
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void apply(int p, const Tag &v){
::apply(info[p], tag[p], v);
}
void push(int p){
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v){
if (l == r){
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x <= m){
modify(2 * p, l, m, x, v);
}
else{
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v){
modify(1, 1, n, p, v);
}
Info query(int p, int l, int r, int x, int y){
if (l > y || r < x){
return Info();
}
if (l >= x && r <= y){
return info[p];
}
int m = (l + r) / 2;
push(p);
return merge(query(2 * p, l, m, x, y), query(2 * p + 1, m + 1, r, x, y));
}
Info query(int l, int r){
return query(1, 1, n, l, r);
}
void modify(int p, int l, int r, int x, int y, const Tag &v){
if (l > y || r < x){
return;
}
if (l >= x && r <= y){
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
modify(2 * p, l, m, x, y, v);
modify(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
void modify(int l, int r, const Tag &v){
return modify(1, 1, n, l, r, v);
}
};
void solve() {
int n;
std::cin >> n;
std::multiset<int> ls, rs;
std::vector<std::array<int, 2>> range(n + 1);
std::vector<std::vector<int>> idr(n + 1);
int cnt = 0;
int nums[4 * n + 1] {};
std::vector<std::array<int, 3>> seg(n + 1);
for (int i = 1; i <= n; i++) {
int l, r, c;
std::cin >> l >> r >> c;
seg[i] = {l, r, c};
range[i] = {l, r};
idr[c].push_back(i);
nums[++cnt] = l, nums[++cnt] = r;
ls.insert(l), rs.insert(r);
}
std::sort(nums + 1, nums + cnt + 1);
cnt = std::unique(nums + 1, nums + 1 + cnt) - nums - 1;
SegTree<Info, Tag> SGT(std::vector<Info> (cnt, Info(0, 1)));
std::vector<i64> ans(n + 1, 1E9);
for (int i = 1; i <= n; i++) {
range[i][0] = std::lower_bound(nums + 1, nums + 1 + cnt, range[i][0]) - nums;
range[i][1] = std::lower_bound(nums + 1, nums + 1 + cnt, range[i][1]) - nums;
SGT.modify(range[i][0], range[i][1], 1);
}
for (int i = 1; i <= n; i++) {
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
ls.erase(ls.lower_bound(ll));
rs.erase(rs.lower_bound(rr));
SGT.modify(cl, cr, -1);
}
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
if (SGT.query(cl, cr).sum) {
ans[id] = 0;
continue;
}
auto it = ls.lower_bound(ll);
if (it != ls.end()) {
ans[id] = std::min(ans[id], 1ll * std::max(0, *it - rr));
}
auto IT = rs.upper_bound(rr);
if (IT != rs.begin()) {
IT = std::prev(IT);
ans[id] = std::min(ans[id], 1ll * std::max(0, ll - *IT));
}
}
for (auto& id : idr[i]) {
auto& [ll, rr, cc] = seg[id];
auto& [cl, cr] = range[id];
ls.insert(ll), rs.insert(rr);
SGT.modify(cl, cr, 1);
}
}
for (int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i == n];
}
原文地址:http://www.cnblogs.com/Haven-/p/16792902.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性