题解：AT_abc424_f [ABC424F] Adding Chords

star_field · 2025-09-25 19:39:16 · 题解

AT_abc424_f

题目大意不过多赘述了。

首先可以在纸上画几个图，分成不交叉的情况和交叉的情况两种。

我们考虑把圆拆成一条链，发现：圆内没有交叉的，拆开后的线段要么无交集，要么一条线段被另一条完全包含；而圆内有交叉的，拆开后交叉的两条线段有交集但没有包含关系。

（图片顺序对应，多边形的边仅用于辅助）

对于拆开的链，我们可以用线段树维护，现在考虑如何判断是否为相交。

对于一条线段，如果它之内与它相交的线段的右端点的最大值大于此线段的右端点，或左端点最小值小于该线段左端点，则该两条线段在圆内相交。

我们可以维护一棵最大值线段树 t 和一棵最小值线段树 t2，其中 t 存每个点为起点的线段的右端点，t2 存每个点为终点的线段的左端点。

code

#include<bits/stdc++.h>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mid ((l+r)>>1)
#define il inline
using namespace std;
const ll N=1e6+5,INF=0x3f3f3f3f;
ll n,m,x,y,t[N<<2],t2[N<<2];
il void push_up1(ll x){
    t[x]=max(t[ls(x)],t[rs(x)]);
}
il void push_up2(ll x){
    t2[x]=min(t2[ls(x)],t2[rs(x)]);
}
il void build1(ll x,ll l,ll r){
    if(l==r){
        t[x]=0;
        return;
    }
    build1(ls(x),l,mid);
    build1(rs(x),mid+1,r);
    push_up1(x);
}
il void build2(ll x,ll l,ll r){
    if(l==r){
        t2[x]=INF;
        return;
    }
    build2(ls(x),l,mid);
    build2(rs(x),mid+1,r);
    push_up2(x);
}
il void update(ll x,ll s,ll l,ll r,ll p){
    if(l==r){
        t[x]=p;
        t2[x]=p;
        return;
    }
    if(s<=mid) update(ls(x),s,l,mid,p);
    else update(rs(x),s,mid+1,r,p);
    push_up1(x);
    push_up2(x);
}
il ll query1(ll x,ll L,ll R,ll l,ll r){
    if(L<=l&&R>=r){
        return t[x];
    }
    ll res=0;
    if(L<=mid) res=max(res,query1(ls(x),L,R,l,mid));
    if(R>mid) res=max(res,query1(rs(x),L,R,mid+1,r));
    return res;
}
il ll query2(ll x,ll L,ll R,ll l,ll r){
    if(L<=l&&R>=r){
        return t2[x];
    }
    ll res=INF;
    if(L<=mid) res=min(res,query2(ls(x),L,R,l,mid));
    if(R>mid) res=min(res,query2(rs(x),L,R,mid+1,r));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    build1(1,1,n);
    build2(1,1,n);
    while(m--){
        cin>>x>>y;
        if(x>y) swap(x,y);
        ll L=x+1, R=y-1;
        if(L<=R){
            ll mn=query2(1,L,R,1,n);
            ll mx=query1(1,L,R,1,n);
            if(mn<x||mx>y){
                cout<<"No\n";
            }else{
                cout<<"Yes\n";
                update(1,x,1,n,y);
                update(1,y,1,n,x);
            }
        }else{
            cout<<"Yes\n";
            update(1,x,1,n,y);
            update(1,y,1,n,x);
        }
    }
    return 0;
}