题目描述
here。
题解
首先，我们对所有区间离散化，删除一个区间时，我们暴力删除内部还存在的子区间。
如果没有区间包含是好做的，因为我们删除一个子区间时，将区间按照左端点排序，可发现包含这个子区间的区间是连续的一个区间。
现在考虑有区间包含怎么做。我们考虑维护出当前所有不包含别的区间的集合。因为若一个区间包含另一个区间，那么它一定在另一个区间之后删除，所以我们当前就不需要管它了。
我们找到当前要删除的区间后，我们就加入新的不包含别的区间的区间。有个暴力做法是主席树优化建图。不过还有别的做法，我们找到按照左端点排序的上一个区间 \([l_1,r_1]\) 和下一个区间 \([l_2,r_2]\)，则我们每次找到剩下区间 \([l',r']\)，满足 \(r'<r_2\)，于是显然满足 \(l'<l_2\)，并且是所有可行区间中 \(l'\) 最大的，若 \(l'>l_1\) 则结束。然后更新 \(l_2\leftarrow l',r_2\leftarrow r'\)。
容易发现，这样可以找到所有新的合法区间。因为新的合法区间需要满足只包含 \([l,r]\)，不包含别的区间，也就是不包含按左端点排序后与 \([l,r]\) 相邻的两个区间。
时间复杂度 \(O(n\log n)\)。
代码
记录。
#include <bits/stdc++.h>
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
const int N = 5e5 + 10;
pair <int, int> a[N], b[N];
int id[N], seg1[N << 2], t[N], seg2[N << 2], ss[N << 2], tmp[N], tot, tag[N << 2], maxn[N << 2];
void add(int x, int y) {
for (; x <= tot; x += x & -x) t[x] += y;
}
int query(int x) {
int ans = 0;
for (; x; x -= x & -x) ans += t[x];
return ans;
}
void pushup1(int num) {
if (seg1[ls] && (!seg1[rs] || a[seg1[ls]].second < a[seg1[rs]].second)) seg1[num] = seg1[ls];
else seg1[num] = seg1[rs];
}
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> tt[N << 2];
void modify1(int num, int l, int r, int x) {
if (l == r) {
tt[num].emplace(a[x].second, x);
seg1[num] = tt[num].top().second;
return;
} int mid = (l + r) >> 1;
if (mid >= a[x].first) modify1(li, x);
else modify1(ri, x);
pushup1(num);
}
void mmodify1(int num, int l, int r, int x) {
if (l == r) {
tt[num].pop();
seg1[num] = tt[num].size() ? tt[num].top().second : 0;
return;
} int mid = (l + r) >> 1;
if (mid >= a[x].first) mmodify1(li, x);
else mmodify1(ri, x);
pushup1(num);
}
int query1(int num, int l, int r, int x, int y) {
if (!seg1[num] || a[seg1[num]].second >= y) return -1;
if (l == r) return seg1[num];
int mid = (l + r) >> 1;
if (mid + 1 < x) {
int t = query1(ri, x, y);
if (~t) return t;
}
return query1(li, x, y);
}
void down(int num, int x) {
tag[num] += x;
seg2[num] += x;
}
void pushdown(int num) {
if (tag[num]) {
down(ls, tag[num]), down(rs, tag[num]);
tag[num] = 0;
}
}
void pushup2(int num) {
if ((seg2[ls] < seg2[rs]) || (seg2[ls] == seg2[rs] && id[ss[ls]] < id[ss[rs]])) {
seg2[num] = seg2[ls];
ss[num] = ss[ls];
} else {
seg2[num] = seg2[rs];
ss[num] = ss[rs];
}
maxn[num] = max(maxn[ls], maxn[rs]);
}
void modify2(int num, int l, int r, int x, int y) {
if (l == r) {
seg2[num] = y;
maxn[num] = a[x].second - 1;
if (y == 1e9) ss[num] = 0;
else ss[num] = x;
return;
}
pushdown(num);
int mid = (l + r) >> 1;
if (mid >= a[x].first) modify2(li, x, y);
else modify2(ri, x, y);
pushup2(num);
}
void change(int num, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) return down(num, x);
pushdown(num);
int mid = (l + r) >> 1;
if (mid >= L) change(li, L, R, x);
if (mid < R) change(ri, L, R, x);
pushup2(num);
}
int prv(int num, int l, int r, int x) {
if (!ss[num]) return -1;
if (l == r) return ss[num];
int mid = (l + r) >> 1;
if (mid + 1 < a[x].first) {
int t = prv(ri, x);
if (~t) return t;
}
return prv(li, x);
}
int nxt(int num, int l, int r, int x) {
if (!ss[num]) return -1;
if (l == r) return ss[num];
int mid = (l + r) >> 1;
if (mid > a[x].first) {
int t = nxt(li, x);
if (~t) return t;
}
return nxt(ri, x);
}
int query2(int num, int l, int r, int x) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (maxn[ls] >= x) return query2(li, x);
return query2(ri, x);
}
bool vis[N];
void zhk() {
tot = 0;
int n; read(n);
F(i, 1, n * 2) t[i] = 0, vis[i] = false;
F(i, 1, n * 8) {
seg2[i] = 1e9;
seg1[i] = tag[i] = ss[i] = maxn[i] = 0;
while (tt[i].size()) tt[i].pop();
}
F(i, 1, n) read(a[i].first), read(a[i].second), tmp[++tot] = a[i].first, tmp[++tot] = a[i].second, id[i] = i;
sort(tmp + 1, tmp + tot + 1);
tot = unique(tmp + 1, tmp + tot + 1) - tmp - 1;
F(i, 1, n) a[i].first = lower_bound(tmp + 1, tmp + tot + 1, a[i].first) - tmp, a[i].second = lower_bound(tmp + 1, tmp + tot + 1, a[i].second) - tmp;
sort(id + 1, id + n + 1, [&] (int x, int y) {
if (a[x].first == a[y].first) return a[x].second > a[y].second;
return a[x].first < a[y].first;
});
F(i, 1, n) b[i] = a[id[i]];
swap(a, b);
deque <int> q;
set <int> s;
F(i, 1, tot - 1) add(i, tmp[i + 1] - tmp[i]), s.insert(i);
F(i, 1, n) {
while (q.size() && a[q.back()].second >= a[i].second) q.pop_back();
q.push_back(i);
}
ms(vis, false);
for (int i: q) {
vis[i] = true;
modify2(1, 1, tot, i, tmp[a[i].second] - tmp[a[i].first]);
}
F(i, 1, n)
if (!vis[i]) modify1(1, 1, tot, i);
F(i, 1, n) {
int t = ss[1];
cout << id[t] << " ";
modify2(1, 1, tot, t, 1e9);
int p = a[t].first == 1 ? -1 : prv(1, 1, tot, t), q = a[t].first == tot ? -1 : nxt(1, 1, tot, t);
while (true) {
int t = query1(1, 1, tot, (~q) ? a[q].first : tot + 1, (~q) ? a[q].second : tot + 1);
if (t == -1) break;
if ((~p) && a[t].first <= a[p].first) break;
mmodify1(1, 1, tot, t);
modify2(1, 1, tot, t, query(a[t].second - 1) - query(a[t].first - 1));
q = t;
}
while (true) {
auto pos = s.lower_bound(a[t].first);
if (pos == s.end() || *pos >= a[t].second) break;
int x = *pos; s.erase(pos);
add(x, tmp[x] - tmp[x + 1]);
int pp = query2(1, 1, tot, x);
change(1, 1, tot, pp, x, tmp[x] - tmp[x + 1]);
}
}
cout << '\n';
}
signed main() {
// freopen("interesting.in", "r", stdin);
// freopen("interesting.out", "w", stdout);
int T, sid; read(T);
while (T--) zhk();
return 0;
}
- 大联盟 Interesting interesting 20230706 Endless大联盟interesting 20230706 endless interesting interesting codeforces 1551c story interesting experience ctf an interesting solution array 482b interesting formulas interesting codeforces function 1538f interesting interested 题解interesting array graph大联盟operation 20230706