D. New Year and Conference（区间交，线段树）

题：https://codeforces.com/contest/1284/problem/D

题意：给定n个1对的时间断，我是这么理解的，甲去参加a时间段的讲座，乙去参加b时间段的讲座，然后若这n对中若能挑出这样一个子集段：甲能参加第 i 个时间段的讲座而乙不能。就输出“NO”（注意，甲乙参加讲座的时间段是给定的a时间段，和b时间段，并不是同一个时间段）

分析：枚举a时间段的时间交，然后讲对应的b时间段的时间交加到线段数上，俩者的时间交数一定要相同，因为这些b区间中两两之间也必须在某点交。

　　　可以理解为“要么都可以去，要么都不可以去”。

#include<bits/stdc++.h>

using namespace std;

const int M=4e5+;

typedef long long ll;

#define pb push_back

#define lson root<<1,l,midd

#define rson root<<1|1,midd+1,r

struct tree{

    int val,lazy;

}tr[M<<];

vector<int>l[M],r[M],lisan;

struct node{

    int l,r,id;

}a[M],b[M];

int n;

void build(int root,int l,int r){

    if(l==r){

        tr[root].val=tr[root].lazy=;

        return ;

    }

    int midd=(l+r)>>;

    build(lson);

    build(rson);

    tr[root].val=tr[root].lazy=;

}

void pushdown(int root){

    int x=tr[root].lazy;

    tr[root<<].val+=x;

    tr[root<<|].val+=x;

    tr[root<<].lazy+=x;

    tr[root<<|].lazy+=x;

    tr[root].lazy=;

}

void up(int root){

    tr[root].val=max(tr[root<<].val,tr[root<<|].val);

}

void update(int L,int R,int val,int root,int l,int r){

    if(L<=l&&r<=R){

        tr[root].val+=val;

        tr[root].lazy+=val;

        return ;

    }

    if(tr[root].lazy!=)

        pushdown(root);

    int midd=(l+r)>>;

    if(L<=midd)

        update(L,R,val,lson);

    if(R>midd)

        update(L,R,val,rson);

    up(root);

}

int query(int L,int R,int root,int l,int r){

    if(L<=l&&r<=R)

        return tr[root].val;

    if(tr[root].lazy!=)

        pushdown(root);

    int maxx=,midd=(l+r)>>;

    if(L<=midd)

        maxx=max(maxx,query(L,R,lson));

    if(R>midd)

        maxx=max(maxx,query(L,R,rson));

    up(root);

    return maxx;

}

bool solve(node *a,node *b){

    int len=lisan.size();

    build(,,len);

    for(int i=;i<=len;i++)

        l[i].clear(),r[i].clear();

    for(int i=;i<=n;i++){

        l[a[i].l].pb(i);

        r[a[i].r].pb(i);

    }

    int countt=;

    for(int i=;i<=len;i++){

        for(int j=;j<l[i].size();j++){

            int id=l[i][j];

            int L=b[id].l,R=b[id].r;

            ///把所有b加上，数量要和与b匹配的a在这个区间上相交的数目countt相同

            int mx=query(L,R,,,len);

            if(mx!=countt)

                return false;

            update(L,R,,,,len);

            countt++;

        }

        ///和上面部分合起来是处理区间交的过程

        for(int j=;j<r[i].size();j++){

            int id=r[i][j];

            int L=b[id].l,R=b[id].r;

            update(L,R,-,,,len);

            countt--;

        }

    }

    return true;

}

int main(){

    scanf("%d",&n);

    for(int x1,x2,y1,y2,i=;i<=n;i++){

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        lisan.pb(x1),lisan.pb(y1),lisan.pb(x2),lisan.pb(y2);

        a[i].l=x1,a[i].r=y1,a[i].id=i;

        b[i].l=x2,b[i].r=y2,b[i].id=i;

    }

    sort(lisan.begin(),lisan.end());

    lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());

    for(int i=;i<=n;i++){

        a[i].l=lower_bound(lisan.begin(),lisan.end(),a[i].l)-lisan.begin()+;

        a[i].r=lower_bound(lisan.begin(),lisan.end(),a[i].r)-lisan.begin()+;

        b[i].l=lower_bound(lisan.begin(),lisan.end(),b[i].l)-lisan.begin()+;

        b[i].r=lower_bound(lisan.begin(),lisan.end(),b[i].r)-lisan.begin()+;

    }

    if(solve(a,b)&&solve(b,a))

        puts("YES");

    else

        puts("NO");

    return ;

}