Codeforces Round #826 (Div. 3) F 线段树 + STL

2022-10-17 13:43| 发布者: qfwoshiyu| 查看: 135| 评论: 13

摘要: 原文链接：F. Multi-Colored Segments 线段树 + STL题意：给定n个区间的线段以及线段的颜色，求距离线段该线段最近的和当前线段颜色不同的距离。分析：我觉得div3应该不会考硬核数据结构，因此在考试的时候一直在想 ...

原文链接：

F. Multi-Colored Segments 线段树 + STL

题意：

给定n个[l, r]区间的线段以及线段的颜色，求距离线段该线段最近的和当前线段颜色不同的距离。

分析：

我觉得div3应该不会考硬核数据结构，因此在考试的时候一直在想怎么偷鸡，显然偷鸡是不对的，学了数据结构就得会用，因此补题的时候果断线段树。

先不考虑颜色，我们该怎么做呢？

我们考虑一棵开一棵权值线段树。对于一个线段，我们区间加，这样可以方便判断区间是否重合，对于有重合的线段直接把ans[id]赋值为0，这是线段树部分。

对于不重合的部分，我们用两个set：L, R来存所有线段的左端点和右端点。对于最近的左端点，只需要找R.lower_bound(l), 对于最近的右端点，需要找-- L.lower_bound(r) 。这都是套路做法。

但是如果考虑颜色的话，怎么办到呢？

我们可以考虑带修改。首先我们每次离线查询答案的时候，一次性把一种颜色查完。比如1号颜色有x种线段，我们先在set和线段树中删掉1号颜色所有的线段信息，然后查询即可。因为set也要删除，但是set因为自动去重的特性，这样直接删除就错了，因此我们要用不去重的multiset。

思路就到这，其他都是代码上的细节问题。

1 拒绝离散化：我们发现颜色的下标很大，因此我们不能直接按照下标建树，离散化又很麻烦，所以我们直接上动态开点线段树区间加的板子。线段树动态开点在经典例题里讲过，就不多说啦。

2 每次查询答案分为3步：删除原有信息，查询答案，恢复原有信息。这样每一个线段最多被删1次，时间复杂度是nlogn。

3 数组和stl解释：L和R表示multiset用于存储线段的左端点和右端点。ans数组存储答案。segs存储所有线段的信息，color[i]是vector容器存储每一种颜色对应的线段的序号。还要注意多组数据，线段树还要初始化。

时间复杂度：O(n)

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;
const int N = 2e5 + 10, INF = 2e9 + 10;
int n, m, node_idx, root, ans[N];
struct Seg {
int l, r, c, id;
} segs[N];
vector<int> color[N];
struct Node {
int l, r;
int sum, add;
} tr[N << 6];

void pushup(int u) {
tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

void pushdown(int u, int l, int r) {
if(!tr[u].l) tr[u].l = ++ node_idx;
if(!tr[u].r) tr[u].r = ++ node_idx;
auto &root = tr[u], &left = tr[tr[u].l], &right = tr[tr[u].r];
int mid = l + r >> 1;
if(root.add) {
left.sum += (mid - l + 1) * root.add;
right.sum += (r - mid) * root.add;
left.add += root.add, right.add += root.add;
root.add = 0;
}
}

void modify(int &u, int l, int r, int x, int y, int v) {
if(!u) u = ++ node_idx;
if(x <= l && y >= r) {
int len = r - l + 1;
tr[u].sum += len * v;
tr[u].add += v;
return ;
}
pushdown(u, l, r);
int mid = l + r >> 1;
if(x <= mid) modify(tr[u].l, l, mid, x, y, v);
if(y > mid) modify(tr[u].r, mid + 1, r, x, y, v);
pushup(u);
}

int query(int u, int l, int r, int x, int y) {
if(!u) return 0;
if(l > r) return 0;
if(y < l || x > r) return 0;
if(x <= l && y >= r) return tr[u].sum;
pushdown(u, l, r);
int mid = l + r >> 1, res = 0;
if(x <= mid) res += query(tr[u].l, l, mid, x, y);
if(y > mid) res += query(tr[u].r, mid + 1, r, x, y);
return res;
}

void solve() {
cin >> n;
multiset<int> L, R;
for(int i = 1; i <= n ; i ++ ) color[i].clear();
for(int i = 1; i <= node_idx ; i ++ ) tr[i].sum = tr[i].add = tr[i].l = tr[i].r = 0;
node_idx = 0, root = 0;
for(int i = 1;i <= n; i ++ ) {
auto &[l, r, c, id] = segs[i];
cin >> l >> r >> c;
ans[i] = INF, id = i;
color[c].push_back(i);
L.insert(l), R.insert(r);
modify(root, 1, INF, l, r, 1);
}

for(int i = 1; i <= n ; i ++ ) {
for(auto it : color[i]) {
auto &[l, r, c, id] = segs[it];
L.erase(L.lower_bound(l));
R.erase(R.lower_bound(r));
modify(root, 1, INF, l, r, -1);
}

for(auto it : color[i]) {
auto &[l, r, c, id] = segs[it];
int res = query(1, 1, INF, l, r);
if(res) {
ans[id] = 0;
continue;
}
auto it1 = L.lower_bound(r), it2 = R.lower_bound(l);
if(it1 != L.end()) ans[id] = min(ans[id], max(0, *it1 - r));
if(it2 != R.begin()) ans[id] = min(ans[id], max(0, l - *--it2));
}

for(auto it : color[i]) {
auto &[l, r, c, id] = segs[it];
L.insert(l);
R.insert(r);
modify(root, 1, INF, l, r, 1);
}
}
for(int i = 1; i <= n ; i ++ ) cout << ans[i] << " "; cout << endl;
}

signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
return 0;
}

打赏鼓励一下！

打赏