能发现其实就是区间加查询区间最小值。
如果最小值 \(> 1\) 则这个区间可以删掉。
考虑离散化端点，先把区间表示为 \([l_i, r_i)\) 的形式，方便离散化端点。
这样子离散化出来的端点也是 \([x, y)\) 的形式。
对于区间加查询区间最小值，很容易用线段树维护。
时间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
const int maxn = 4e5 + 10;
int n, m;
int mn[maxn * 2], tag[maxn * 2];
#define mid ((l + r) >> 1)
#define id(l, r) (((l) + (r)) | ((l) != (r)))
inline void pushup(int l, int r) {mn[id(l, r)] = std::min(mn[id(l, mid)], mn[id(mid + 1, r)]);}
inline void upd(int l, int r, int v) {mn[id(l, r)] += v, tag[id(l, r)] += v;}
inline void pushdown(int l, int r) {int &v = tag[id(l, r)]; v && (upd(l, mid, v), upd(mid + 1, r, v), v = 0);}
inline void update(int x, int y, int l = 1, int r = m) {
if (x <= l && r <= y) return upd(l, r, 1), void();
pushdown(l, r);
x <= mid && (update(x, y, l, mid), 1), mid < y && (update(x, y, mid + 1, r), 1);
pushup(l, r);
}
inline int qry(int x, int y, int l = 1, int r = m) {
if (x <= l && r <= y) return mn[id(l, r)];
pushdown(l, r);
return std::min(x <= mid ? qry(x, y, l, mid) : n, mid < y ? qry(x, y, mid + 1, r) : n);
}
int W[maxn], l[maxn], r[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]), r[i]++;
for (int i = 1; i <= n; i++) W[++m] = l[i], W[++m] = r[i];
std::sort(W + 1, W + m + 1);
for (int i = 1; i <= n; i++) {
l[i] = std::lower_bound(W + 1, W + m + 1, l[i]) - W;
r[i] = std::lower_bound(W + 1, W + m + 1, r[i]) - W - 1;
}
for (int i = 1; i <= n; i++) update(l[i], r[i]);
for (int i = 1; i <= n; i++)
if (qry(l[i], r[i]) > 1) return printf("%d\n", i), 0;
puts("-1");
return 0;
}
还有一种更为简单的方式是考虑到只需要判断区间最小值是否 \(> 1\)。
对于每个点维护右端点满足这个点到右端点的区间最小值 \(> 1\) 且这个右端点是合法中最靠右的。
可以倒序维护。
复杂度瓶颈在离散化，时间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
const int maxn = 4e5 + 10;
int n, m;
int W[maxn], l[maxn], r[maxn];
int sum[maxn], R[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]), r[i]++;
for (int i = 1; i <= n; i++) W[++m] = l[i], W[++m] = r[i];
std::sort(W + 1, W + m + 1);
for (int i = 1; i <= n; i++) {
l[i] = std::lower_bound(W + 1, W + m + 1, l[i]) - W;
r[i] = std::lower_bound(W + 1, W + m + 1, r[i]) - W - 1;
sum[l[i]]++, sum[r[i] + 1]--;
}
for (int i = 1; i <= m; i++) sum[i] += sum[i - 1];
R[m + 1] = m;
for (int i = m; i; i--) R[i] = sum[i] > 1 ? R[i + 1] : (i - 1);
for (int i = 1; i <= n; i++)
if (R[l[i]] >= r[i]) return printf("%d\n", i), 0;
puts("-1");
return 0;
}