前言

考完 CSP，估分 J 97，S 87。
在红岭吃午餐的时候，qx 跟我说他今晚不打 ABC，结果他偷偷背着我打了，还进了前 1000 名，已经上 1000 分了。orz orz
幸好我也打了，名次刚好比他高 9 个，也上 1000 分。还剩 10 分钟已经看出来 F 是线段树了，但觉得太耗时间了想着用 set 偷懒，没写出来。
abc.webp
To 线段树:
  看到你我很激动，我已经很久没遇到你了。但我又没时间了……
To yl​:
  不怪你，下次我们再相遇吧，这次离别只是为了更好的重逢，等我再遇到你时希望你已经是一个合格的OIer了。见字如面。
​
​线段树，除了你还有哪个数据结构愿意陪我吵，陪我闹，陪我伤心陪我笑……我已经没有朋友了……

题目大意

一个圆上有 $N$ 个间隔相等的点，$Q$ 次询问，每次询问要求你画出端点为 $A$ 和 $B$ 的弦，如果和之前画出的弦相交则输出 No 并不画。
保证每个 $A$ 和 $B$ 都不相等。

思路分析

不知道为什么，一眼线段树。
先来看官方给的图。
eg
已有 $(1,5)$ 这条弦，我们该如何判断当前这条弦不会跟其相交呢？
不妨令 $A < B$，可以看到弦把圆分成了 $2$ 部分，如果新的弦和这条弦相交的话，必定是从一个部分到另一个部分。那我们可以顺时针来看，让弦 $(A,B)$ 对应区间 $[A,B]$，如果区间内有点和区间外的点有连线，那么就相交了。
形式化的，由于弦的端点各不相同：

  • 如果区间 $[A,B]$ 内有点的对应端点是小于 $A$ 或大于 $B$ 的，那么这条弦就和之前的弦相交。
  • 否则的话，我们就连上 $A,B$，$A$ 对应 $B$，$B$ 对应 $A$。

那有单点修改，区间查询，我们该如何维护这个对应端点呢？
线段树。维护区间的最小值和最大值。甚至不用写懒惰标记

  • 单点修改：把 $A$ 点的值改成 $B$，$B$ 点的值改成 $A$
  • 区间查询：获取 $[A,B]$ 内的最小值、最大值，并判断是否小于 $A$ 或大于 $B$

细节在代码注释里了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define int long long
#define ls o<<1
#define rs o<<1|1
using namespace std;
const int N=1e6+5,inf=1e9;
int n,q;
struct node{
    int mn,mx;
    node operator +(const node &w)const{return {min(mn,w.mn),max(mx,w.mx)};}
}tr[N<<2];
void pushup(int o){tr[o]=tr[ls]+tr[rs];}
void build(int o,int l,int r){
    if(l==r){
        tr[o]={l,l};//一开始让端点对应自己
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(o);
}
void updmn(int o,int l,int r,int pos,int x){//改最小
    if(l==r){
        tr[o].mn=min(tr[o].mn,x);
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) updmn(ls,l,mid,pos,x);
    else updmn(rs,mid+1,r,pos,x);
    pushup(o);
}
void updmx(int o,int l,int r,int pos,int x){//改最大
    if(l==r){
        tr[o].mx=max(tr[o].mx,x);
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) updmx(ls,l,mid,pos,x);
    else updmx(rs,mid+1,r,pos,x);
    pushup(o);
}
node query(int o,int l,int r,int L,int R){//模板查询
    if(l>=L&&r<=R) return tr[o];
    int mid=l+r>>1;
    node res={inf,-inf}; 
    if(L<=mid) res=res+query(ls,l,mid,L,R);
    if(R>mid) res=res+query(rs,mid+1,r,L,R);
    return res;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b); 
        node k=query(1,1,n,a,b);
        if(k.mn<a||k.mx>b) cout<<"No\n";
        else{
            cout<<"Yes\n";
            updmn(1,1,n,b,a);
            updmx(1,1,n,a,b);
        }
    } 
    return 0;
}