Description

有 \(n\) 节课，没节课有两个时间段 \([l_1,r_1],[l_2,r_2]\)

每个时间点上只能上一节课，判断给定的时间安排是不是合法

\(n\le 3\times10^5\)

Solution

首先学习：前后缀优化建图（\(PA2010 Riddle\) 或 \(Codeforces\ 587D\)）

发现每个课程的选择其实就是一个 \(0/1\) 所以还是一个布尔方程

就是说如果两节课的某个时间段有冲突了，那就是 \(j\to i',i\to j'\)

然后考虑怎么建冲突的边：

（先离散化）

建一棵线段树，然后把课程压到 \(log\) 个区间里面

如果两个课程有冲突，那么等价于占用同一个节点或者两个节点有祖先儿子的关系

那么缩点，每个课程的时间下放的时候连到 \(\log\) 个区间里面

最后统一连边，这步需要前后缀优化建图的思想

\(in\) 中的向 \(out\) 中的连边

（感觉自己学了个假的前后缀优化建图呀……）

其实这里和上面说的两个题目不一样的是这个线段树上的要处理父亲和儿子的关系

然后大概写成这个样子：（总算花了好多时间弄懂了……）

Code

#include<bits/stdc++.h>
using namespace std;
#define reg register
namespace yspm{
    inline int read()
    {
        int res=0,f=1; char k;
        while(!isdigit(k=getchar())) if(k=='-') f=-1;
        while(isdigit(k)) res=res*10+k-'0',k=getchar();
        return res*f;
    }
    const int N=35e4+10;
    vector<int> g[N<<3],in[N<<2],out[N<<2];
    int mx,st[N<<3],top,tot,dfn[N<<3],low[N<<3],tim,scc[N<<3],n,m;
    int ls[N<<2],rs[N<<2],rt,id1[N<<2],pre[N<<2],nxt[N<<2],fa[N<<2],id2[N<<2];
    bool vis[N<<3];
    int b[N<<2],num;
    inline void build(int &p,int l,int r)
    {
        p=++mx; id1[p]=++mx; id2[p]=++mx; 
        in[p].clear(); out[p].clear(); ls[p]=rs[p]=0;
        if(l==r) return ;
        int mid=(l+r)>>1; 
        build(ls[p],l,mid); build(rs[p],mid+1,r);    
        fa[rs[p]]=fa[ls[p]]=p; 
        return ;
    }
    inline void tarjan(int x)
    {
        low[x]=dfn[x]=++tim; vis[x]=1; st[++top]=x; 
        int sz=g[x].size();
        for(reg int i=0;i<sz;++i) 
        {
            int t=g[x][i];
            if(!dfn[t]) tarjan(t),low[x]=min(low[x],low[t]);
            else if(vis[t]) low[x]=min(low[x],dfn[t]); 
        }
        if(low[x]==dfn[x])
        {    
            ++tot;
            do{
                vis[st[top]]=0; 
                scc[st[top]]=tot;
                top--;
            }while(st[top+1]!=x);
        }return;
    }
    inline void update(int p,int st,int ed,int l,int r,int i,int opt)
    {  
        if(l<=st&&ed<=r)
        {
            in[p].push_back(opt==1?i:i+n); 
            out[p].push_back(opt==1?i+n:i);
            return;
        } 
        int mid=(st+ed)>>1; 
        if(l<=mid) update(ls[p],st,mid,l,r,i,opt);
        if(r>mid) update(rs[p],mid+1,ed,l,r,i,opt);
        return ;    
    } 

    inline void add(int p,int l,int r)
    {
        int sz=out[p].size();
        for(reg int i=0;i<sz;++i)
        {
            ++mx; 
            if(!i&&fa[p]) g[id2[fa[p]]].push_back(mx); 
            if(i+1<sz) pre[out[p][i]]=mx+1,g[mx].push_back(mx+1);
            else pre[out[p][i]]=id2[p],g[mx].push_back(id2[p]);
            g[mx].push_back(out[p][i]);
        }
        for(reg int i=sz-1;i>=0;--i)
        {
            ++mx; 
            if(i==sz-1)
            {
                if(ls[p]) g[id1[ls[p]]].push_back(mx);
                if(rs[p]) g[id1[rs[p]]].push_back(mx);
            }
            if(i>0) nxt[out[p][i]]=mx+1,g[mx].push_back(mx+1);
            else nxt[out[p][i]]=id1[p],g[mx].push_back(id1[p]);
            g[mx].push_back(out[p][i]);
        }
        if(!sz)
        {
            if(fa[p]) g[id2[fa[p]]].push_back(id2[p]);
            if(ls[p]) g[id1[ls[p]]].push_back(id1[p]);
            if(rs[p]) g[id1[rs[p]]].push_back(id1[p]);
        }
        for(reg int i=0,tmp;i<sz;++i) 
        {
            tmp=in[p][i]>n?in[p][i]-n:in[p][i]+n;
            if(pre[tmp]) g[in[p][i]].push_back(pre[tmp]);
            if(nxt[tmp]) g[in[p][i]].push_back(nxt[tmp]);
        }  
        if(l==r) return ; 
        int mid=(l+r)>>1; 
        add(ls[p],l,mid); add(rs[p],mid+1,r); 
        return ;
    }
    inline void clear()
    {
        for(reg int i=1;i<=mx;++i) 
        {   
            g[i].clear(); dfn[i]=0;
            pre[i]=nxt[i]=id1[i]=id2[i]=0; 
        } top=tim=mx=num=tot=0;
        return;
    }
    struct cla{
        int l1,l2,r1,r2;
    }c[N];
    inline int get(int x){return lower_bound(b+1,b+num+1,x)-b;}
    inline void work()
    {
        clear(); n=read(); m=read(); mx=n<<1; num=0; 
        for(reg int i=1;i<=n;++i) 
        {
            c[i].l1=read(),c[i].r1=read(),c[i].l2=read(),c[i].r2=read();
            b[++num]=c[i].l1; b[++num]=c[i].r1; b[++num]=c[i].l2; b[++num]=c[i].r2;
        } sort(b+1,b+num+1); num=unique(b+1,b+num+1)-b-1; build(rt,1,num); 
        for(reg int i=1;i<=n;++i) 
        {
            c[i].l1=lower_bound(b+1,b+num+1,c[i].l1)-b;
            c[i].l2=lower_bound(b+1,b+num+1,c[i].l2)-b;
            c[i].r1=lower_bound(b+1,b+num+1,c[i].r1)-b;
            c[i].r2=lower_bound(b+1,b+num+1,c[i].r2)-b;
            update(rt,1,num,c[i].l1,c[i].r1,i,1);
            update(rt,1,num,c[i].l2,c[i].r2,i,2); 
        }
        add(rt,1,num);
        for(reg int i=1;i<=mx;++i) if(!dfn[i]) tarjan(i);
        for(reg int i=1;i<=n;++i) if(scc[i+n]==scc[i]) return puts("NO"),void(); 
        return puts("YES"),void();
    }
    signed main()
    {
        freopen("class.in","r",stdin);
        freopen("class.out","w",stdout);
        int T=read(); while(T--) work();
        return 0;
    }
}
signed main(){return yspm::main();}