2020 Multi-University Training Contest 5---- HDU--6824、Exam （2-sat，线段树优化建图）

题目链接

题面：

题意：
有 $n$n 门考试，每门考试有两个时间段可以进行 $[a,a+at],[b,b+bt]$[a,a+at],[b,b+bt]，每门考试必须选择其中的一个时间段进行，且两门考试的时间严格不相交。即 $[3,5],[5,7]$[3,5],[5,7]进行两门考试是不合法的。

问完成 $n$n 门考试的最短时间。

题解：

上面是官方题解：
我们把考试转换为 $2-sat$2−sat 问题（显然要转化为 $2-sat$2−sat）。
我们设考试 $i$i 选择 $[a,a+at]$[a,a+at] 时间段的变量为 $i$i，选择 $[b,b+bt]$[b,b+bt] 时间段的变量为 $i^{\prime }$i′。

但是题目要求输出完成所有考试的最小时间，而 $2-sat$2−sat 只能解决有解和无解的问题，那么很容易就能想到，我们可以把这个问题转化为判定性问题。即 二分完成所有考试的最小时间，然后和判定在当前最小时间下是否有解即可。

假设当前二分的值为 $mid$mid，如果 $a+at>mid$a+at>mid，那么说明考试 $i^{\prime }$i′ 是必选的，则 $i->i^{\prime }$i−>i′。
如果 $b+bt>mid$b+bt>mid，那么就说明考试 $i$i 是必选的，则 $i^{\prime }->i$i′−>i。

剩下的只需要将有冲突的考试场次连边即可。
如果 $[a_i,a_i+a{t}_i]$[ai​,ai​+ati​] 与 $[a_j,a_j+a{t}_j]$[aj​,aj​+atj​] 有交，则说明是冲突的，则 $i->j^{\prime },j->i^{\prime }$i−>j′,j−>i′。

如果 $[a_i,a_i+a{t}_i]$[ai​,ai​+ati​] 与 $[b_j,b_j+b{t}_j]$[bj​,bj​+btj​] 有交，则说明是冲突的，则 $i->j,j^{\prime }->i^{\prime }$i−>j,j′−>i′。

如果 $[b_i,b_i+b{t}_i]$[bi​,bi​+bti​] 与 $[a_j,a_j+a{t}_j]$[aj​,aj​+atj​] 有交，则说明是冲突的，则 $i^{\prime }->j^{\prime },j->i$i′−>j′,j−>i。

如果 $[b_i,b_i+b{t}_i]$[bi​,bi​+bti​] 与 $[b_j,b_j+b{t}_j]$[bj​,bj​+btj​] 有交，则说明是冲突的，则 $i^{\prime }->j,j^{\prime }->i$i′−>j,j′−>i。

对于答案，我们发现如果答案存在，那么最优的结束时间一定是在某一场比赛的结束。
即我们只需要记录下 $\{a+at,b+bt\}${a+at,b+bt} 这个集合，然后排序，在其里面二分即可。

现在新的问题来了。
虽然上述解法可以解决当前问题，但是时间复杂度为 $O\left(n^{2}logn\right)$O(n2logn)，空间复杂度为 $O\left(n^2\right)$O(n2)，是我们所不能接受的。

我们将 $[a,a+at],[b,b+bt]$[a,a+at],[b,b+bt] 都记为一个四元组 $(idn,idf,a,a+at)$(idn,idf,a,a+at)，其中 $idn$idn 选择当前区间的变量， $idf$idf选择另一区间的变量。
例如:
对于 $[a_i,a_i+a{t}_i]$[ai​,ai​+ati​] 记为 $(idn=i,idf=i+n,a_i,a_i+a{t}_i)$(idn=i,idf=i+n,ai​,ai​+ati​)
对于 $[b_i,b_i+b{t}_i]$[bi​,bi​+bti​] 记为 $(idn=i+n,idf=i,b_i,b_i+b{t}_i)$(idn=i+n,idf=i,bi​,bi​+bti​)

考虑对于某一场考试 $i$i，我们只需要考虑与其冲突的的考试 $j$j， $a_i\le a_j\le a_i+a{t}_i$ai​≤aj​≤ai​+ati​，那么起始就涵盖了所有的情况。

我们将所有的考试按照考试的开始时间排序，那么我们的 $a_i\le a_j\le a_i+a{t}_i$ai​≤aj​≤ai​+ati​，中的 $a_j$aj​ 一定是一段连续的区间。

也就是说，我们对于某一个点，考虑一个区间 ，类似于 $x->[l,r]$x−>[l,r]。
所以我们来考虑线段树优化建图。

我们枚举 $i\in [1,n\ast 2]$i∈[1,n∗2]，找到 $a_i\le a_j\le a_i+a{t}_i$ai​≤aj​≤ai​+ati​，假设区间为 $[l,r]$[l,r]，那么我们如果选择 $i$i，则不能选择区间 $[l,r]$[l,r] 中的任何一个点，所以我们从 $i\left(id{n}_i\right)$i(idni​) 向 $[l,r]$[l,r] 的每个点的 $idf$idf 连边。如果我们选择了 $[l,r]$[l,r] 区间中的任意一个点，那么不能选择 $i$i，那么我们从 $[l,r]$[l,r] 区间的每个点的 $idn$idn 向 $i^{\prime }\left(id{f}_i\right)$i′(idfi​) 连边。

所以：
我们的 $x->[l,r]$x−>[l,r] 线段树每个父亲向儿子节点连边，最终叶子节点向每个点的 $idf$idf 连边。
我们的 $[l,r]->x$[l,r]−>x 线段树每个儿子向父亲节点连边，每个点的 $idn$idn 向叶子节点连边。

这里我们的叶子节点不共用，而是每棵树的叶子节点都都有自己的编号之后再向 $idf$idf 和 $idn$idn 连边。因为 $idf$idf 和 $idn$idn 会出现编号相同但是在不同的叶子节点上的问题（即两个序列不一致）。

时间复杂度 $O\left(nlo{g}^{2}n\right)$O(nlog2n)，空间复杂度 $O\left(nlogn\right)$O(nlogn)

代码：

#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
//#define lc (cnt<<1)
//#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

int head[maxn<<3],ver[maxn<<5],nt[maxn<<5],tot=1;


void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

int n;
struct node
{
    int s,t;
    int idn,idf;
}a[maxn<<1];

bool cmp(const node &a,const node &b)
{
    return a.s<b.s;
}

struct tree
{
    int l,r,lc,rc;
}t[maxn<<3];
int rtin,rtout,cnt=0;

int build(int l,int r,bool flag)
{
    int p=++cnt;
    t[p].l=l,t[p].r=r;
    t[p].lc=t[p].rc=0;
    if(l==r)
    {
        flag?add(p,a[l].idf):add(a[l].idn,p);
        return p;
    }
    t[p].lc=build(l,tmid,flag);
    t[p].rc=build(tmid+1,r,flag);
    flag?add(p,t[p].lc):add(t[p].lc,p);
    flag?add(p,t[p].rc):add(t[p].rc,p);
    return p;
}

void  add(int x,int l,int r,int p,bool flag)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        flag?add(x,p):add(p,x);
        return ;
    }
    if(l<=t[t[p].lc].r) add(x,l,r,t[p].lc,flag);
    if(r>=t[t[p].rc].l) add(x,l,r,t[p].rc,flag);
}

int dfn[maxn<<3],low[maxn<<3],st[maxn<<3],c[maxn<<3];
int sum=0,top=0,index=0;
bool ha[maxn<<3];
void tarjan(int x)
{
    dfn[x]=low[x]=++sum;
    st[++top]=x,ha[x]=true;

    for(int i=head[x];i;i=nt[i])
    {
        if(!dfn[ver[i]])
        {
            tarjan(ver[i]);
            low[x]=min(low[x],low[ver[i]]);
        }
        else if(ha[ver[i]])
            low[x]=min(low[x],low[ver[i]]);
    }

    if(dfn[x]==low[x])
    {
        index++;
        int y;
        do
        {
            y=st[top--];
            ha[y]=false;
            c[y]=index;
        }while(x!=y);
    }
}

bool check(void)
{
    for(int i=1;i<=cnt;i++)
        dfn[i]=low[i]=ha[i]=c[i]=0;
    sum=top=index=0;
    for(int i=1;i<=cnt;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(c[i]==c[i+n]) return false;
    return true;
}

int d[maxn<<3],e[maxn<<3];

void init(int n)
{
    for(int i=1;i<=n;i++) head[i]=0,t[i].lc=t[i].rc=0;
    tot=1;
    rtin=rtout=cnt=0;

}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            ++cnt;
            scanf("%d%d",&a[cnt].s,&a[cnt].t);
            a[cnt].idn=i,a[cnt].idf=i+n;
            a[cnt].t+=a[cnt].s;
            ++cnt;
            scanf("%d%d",&a[cnt].s,&a[cnt].t);
            a[cnt].idn=i+n,a[cnt].idf=i;
            a[cnt].t+=a[cnt].s;
        }
        sort(a+1,a+n*2+1,cmp);
        rtin=build(1,n*2,true);
        rtout=build(1,n*2,false);

        for(int i=1;i<=n*2;i++)
            d[i]=a[i].s,e[i]=a[i].t;
        for(int i=1;i<=n*2;i++)
        {
            int pos=upper_bound(d+1,d+n*2+1,a[i].t)-d-1;
            if(pos<=i) continue;
            add(a[i].idn,i+1,pos,rtin,true);
            add(a[i].idf,i+1,pos,rtout,false);
        }

        int l=1,r=n*2;
        int pos=-1,mid;
        sort(e+1,e+n*2+1);
        while(l<=r)
        {
            mid=(l+r)>>1;
            for(int i=1;i<=n*2;i++)
            {
                if(a[i].t>e[mid])
                    add(a[i].idn,a[i].idf);
            }

            if(check()) pos=mid,r=mid-1;
            else l=mid+1;

            for(int i=1;i<=n*2;i++)
            {
                if(a[i].t>e[mid])
                    head[a[i].idn]=nt[head[a[i].idn]],tot--;
            }
        }
        printf("%d\n",pos==-1?-1:e[pos]);
        init(cnt);

    }
    return 0;
}