AT_abc338_e 题解

yyrwlj · 2024-01-28 09:48:34 · 题解

题意简述

有 n \times 2 个点顺次排成一圈，有 n 条线段不重不漏的连接了这些点，给出这 n 条线段连接的两个点编号，问是否有线段相交。

思路

设某条线段连接的两个点编号分别是 a 和 b（a < b），那么有其它线段和这条线段相交，当且仅当有其它线段的一个端点编号在区间 [a, b] 内，另一个不在。

考虑记录每个点对应的另一个点是什么，然后线段树维护区间最值查询。

Code

#include <iostream>
using namespace std;
const int N = 200005;
pair<int, int> g[N];
int to[N << 1], w[N << 3][2];
void build(int u,int l,int r)
{
    if (l == r)
    {
        w[u][0] = w[u][1] = to[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    w[u][0] = min(w[u << 1][0], w[u << 1 | 1][0]);
    w[u][1] = max(w[u << 1][1], w[u << 1 | 1][1]);
}
int query(int u,int l,int r,int L,int R,int op)
{
    if (L <= l && r <= R)
        return w[u][op];
    int mid = (l + r) >> 1, ans = 0;
    if (op == 0)
    {
        ans = 1e9;
        if (L <= mid)
            ans = query(u << 1, l, mid, L, R, 0);
        if (mid < R)
            ans = min(ans, query(u << 1 | 1, mid + 1, r, L, R, 1));
    }
    else
    {
        if (L <= mid)
            ans = query(u << 1, l, mid, L, R, 1);
        if (mid < R)
            ans = max(ans, query(u << 1 | 1, mid + 1, r, L, R, 1));
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        g[i] = {a, b};
        to[a] = b;
        to[b] = a;
    }
    const int m = n * 2;
    build(1, 1, m);
    for (int k=1;k<=n;k++)
    {
        int a = g[k].first, b = g[k].second;
        if (a > b)
            swap(a, b);
        if (b - a == 1 || a == 1 && b == m)
            continue;
        int mn = query(1, 1, m, a + 1, b, 0);
        int mx = query(1, 1, m, a + 1, b, 1);
        if (mn < a || mx > b)
        {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}