题目来源：Codeforces Round #826 (Div. 3) F
题目链接：F. Multi-Colored Segments
题意
给定\(n\)条有颜色的线段（\(l_i,r_i,c_i\)），对于每条线段，求：距离该线段最近，且颜色不同的线段的最短距离。
数据范围：\(2 \le n \le 2·10^5\)，\(\sum{n} \le 2·10^5\)，\(1 \le l_i,r_i \le 10^9\)，\(1 \le c_i \le n\).
思路：线段树
记要求的值为 \(ans_i\).
对于颜色不同的限制：可以每种颜色分别考虑，求一种颜色线段的\(ans\)时，可以将该颜色的所有线段先从总体中去掉，完成计算后，再重新添加回去，这样添加、删除操作的次数就是线性的。于是需要支持\(log\)级别的添加、删除操作的数据结构。
-
考虑线段互不相交的情况下的答案：
在计算线段\(i\)的答案时，记其左右端点为\(l_i,r_i\)，那么需要找到该线段左边最近的线段的右端点\(right\)，以及该线段右边最近的线段的左端点\(left\)，那么可以更新答案：\(ans_i = min(l_i - right,left - r_i)\).
快速找到这两个值，可以用两个multiset分别存储线段的左、右端点，再在上面二分查找。
-
考虑线段存在相交的情况下的答案：
当线段\(i\)存在与它相交的线段时，答案即为\(0\).
为了快速判断是否存在这样的线段，可以将所有线段的端点进行离散化后，写一棵支持区间加和区间和查询的线段树，添加一条线段时，在其区间里\(+1\)，删除时则为\(-1\)。
记线段\(i\)左右端点离散化后的值为\(L_i,R_i\)，那么只要\(\large \sum_{j=L_i}^{R_i} > 0\)，就说明存在与该线段相交的线段，答案更新为\(0\)，否则不更新答案。
时间复杂度：\(O(nlogn)\).
代码
#include <bits/stdc++.h>
#define endl '\n'
#define LL long long
using namespace std;
const int N = 200010;
const int INF = 0x3f3f3f3f;
struct segment {
int l, r, i;
};
int n, ans[N], tot;
vector<segment> seg[N]; // 存不同颜色的线段
multiset<int> L, R; // 存左、右端点
set<int> pos; // 存所有端点，便于离散化
map<int,int> id; // 端点离散化后的值
struct Node {
int l, r;
LL sum, add;
} tr[N << 3];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void eval(Node& t, int add)
{
t.sum += (t.r - t.l + 1LL) * add;
t.add += add;
}
void pushdown(int u)
{
if(!tr[u].add) return;
eval(tr[u << 1], tr[u].add);
eval(tr[u << 1 | 1], tr[u].add);
tr[u].add = 0;
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = { l, r, 0, 0 };
else {
tr[u] = { l, r, 0, 0 };
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int add)
{
if(tr[u].l >= l && tr[u].r <= r) eval(tr[u], add);
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, add);
if(r > mid) modify(u << 1 | 1, l, r, add);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
void init(int n)
{
tot = 0;
for(int i = 1; i <= n; i++) {
ans[i] = INF;
seg[i].clear(), seg[i].shrink_to_fit();
}
L.clear(), R.clear(), pos.clear(), id.clear();
}
void solve()
{
cin >> n;
init(n);
for(int i = 1; i <= n; i++) {
int l, r, col;
cin >> l >> r >> col;
seg[col].push_back( { l, r, i } );
L.insert(l), R.insert(r), pos.insert(l), pos.insert(r);
}
// 线段互不相交的情况
for(int col = 1; col <= n; col++) {
// 删掉颜色为col的线段
for(auto item : seg[col]) {
int l = item.l, r = item.r;
L.erase(L.find(l)), R.erase(R.find(r));
}
// 更新ans
for(auto item : seg[col]) {
int l = item.l, r = item.r, i = item.i;
// 与线段i不相交的左边最近线段
auto it1 = R.lower_bound(l);
if(it1 != R.begin()) {
ans[i] = min(ans[i], l - *prev(it1));
}
// 与线段i不相交的右边最近线段
auto it2 = L.upper_bound(r);
if(it2 != L.end()) {
ans[i] = min(ans[i], *it2 - r);
}
}
// 重新插入颜色为col的线段
for(auto item : seg[col]) {
L.insert(item.l), R.insert(item.r);
}
}
// 线段存在相交的情况
// 将线段的左右端点离散化
for(auto x : pos) {
id[x] = ++ tot;
}
// 线段树初始化
build(1, 1, tot);
for(int col = 1; col <= n; col++) {
for(auto item : seg[col]) {
modify(1, id[item.l], id[item.r], 1);
}
}
for(int col = 1; col <= n; col++) {
// 删掉颜色为col的线段
for(auto item : seg[col]) {
modify(1, id[item.l], id[item.r], -1);
}
// 更新ans
for(auto item : seg[col]) {
int L = id[item.l], R = id[item.r], i = item.i;
if(query(1, L, R) > 0) ans[i] = 0;
}
// 将颜色为col的线段重新加入到线段树中
for(auto item : seg[col]) {
modify(1, id[item.l], id[item.r], 1);
}
}
for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int test;
cin >> test;
while(test--) solve();
return 0;
}