Liveddd's Blog

愛にできることはまだあるかい

CF319E Ping-Pong

发表于 分类于
本文字数： 3.4k 阅读时长 ≈ 8 分钟

线段树应用。

不相交的区间不能互相到达，包含的区间只能从小区间向大区间走，相交但不包含的区间都可以走。我们考虑用并查集把所有的相交但不包含的区间合并起来，视为同一个连通块，合并后对应着一个等效区间 $[\min_{i\in S} l_i,\max_{i\in S} r_i]$。那么判定条件就是，是否为同一个连通块，或者等效区间是否存在包含关系（那么该连通块中必然存在一个区间包含当前区间）。

那么我们相当于每次需要找到所有与当前区间有交的区间。需要注意到题面给出的“所有区间长度单调递增”。我们利用线段树，把当前区间的端点与经过的区间合并，这样合并的区间必然与当前区间相交，再打上该节点的 tag 作为代表。再把区间中除了端点所有位置打上 tag 即可。

注意体面中给的条件是小于号而非小于等于号，可能需要一些细节。

Code
 
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);        
}
struct Interval
{
    int l,r;
    const Interval operator+(const Interval &t)const{return (Interval){min(l,t.l),max(r,t.r)};}
};
int n,m,tot;
int fa[N];
int op[N],x[N],y[N];
int c[N<<1];
Interval a[N],val[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return ;
    val[x]=val[x]+val[y],fa[y]=x;
}
struct Seg
{
    struct Node
    {
        int l,r;
        vector<int>tag;
    }tr[N<<2];
    void update(int x,int k){tr[x].tag.push_back(k);}
    void build(int x,int l,int r)
    {
        tr[x].l=l,tr[x].r=r;
        if(l==r)return ;
        int mid=l+r>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    }
    void get(int x,int pos,int k)
    {
        if(!tr[x].tag.empty())
        {
            for(auto i:tr[x].tag)merge(i,k);
            tr[x].tag.clear();
            update(x,k);
        }
        if(tr[x].l==tr[x].r)return ;
        int mid=tr[x].l+tr[x].r>>1;
        if(pos<=mid)get(x<<1,pos,k);
        else get(x<<1|1,pos,k);
    }
    void tag(int x,int l,int r,int k)
    {
        if(l<=tr[x].l&&r>=tr[x].r)return update(x,k);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)tag(x<<1,l,r,k);
        if(r>mid)tag(x<<1|1,l,r,k);
    }
}t;
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        read(op[i],x[i],y[i]);
        if(op[i]==1)c[++m]=x[i],c[++m]=y[i];
    }
    sort(c+1,c+1+m);
    m=unique(c+1,c+1+m)-c-1;
    t.build(1,1,m);
    for(int i=1;i<=n;i++)
    {
        if(op[i]==1)
        {
            x[i]=lower_bound(c+1,c+1+m,x[i])-c;
            y[i]=lower_bound(c+1,c+1+m,y[i])-c;
            tot++;
            fa[tot]=tot;
            val[tot]=a[tot]={x[i],y[i]};
            t.get(1,x[i],tot),t.get(1,y[i],tot);
            if(x[i]+1<=y[i]-1)t.tag(1,x[i]+1,y[i]-1,tot);
        }
        else
        {
            int u=find(x[i]),v=find(y[i]);
            if(u==v||(a[u].l>val[v].l&&a[u].r<=val[v].r)||(a[u].l>=val[v].l&&a[u].r<val[v].r))puts("YES");
            else puts("NO");
        }
    }
    return 0;
}