D - New Year and Conference

题意：给两组线段，第一组叫做ai，第二组叫做bi，要求验证是否任意一对(i,j),i!=j，都有：要么ai与aj有交点且bi与bj有交点，要么都没有交点。

题解：比赛的时候想了个分治，但是没想清楚，而且细节没处理好，其实比赛最后一次提交的代码只需要改动10行就可以AC了。

把题目转化成验证：当ai与aj有交点时，bi与bj有交点；且当bi与bj有交点时，ai与aj有交点。已知这个条件与题目条件是等价的。

先离散化。

然后solve_a(int l,int r)表示离散化后ai的右端点坐标在[l,r]之间的所有线段是否满足题意。

根据分治的原理，先递归给两个子区间，假如其中一个子区间不满足，那么这整个区间也不满足。否则处理跨越中点的情况。

1. 把右子区间的所有aj的左端点插入树状数组，然后左子区间的ai的右端点在树状数组中询问，即可知道左子区间的右端点>=右子区间的所有左端点的信息，也就是跨越中点且ai与aj相交的线段的信息。

2. 此时，要求i与每一个相交的j都有交点，画个图可以直观看出，要求 \(b_i的右端点>=max\{b_j的左端点\}\) 且 \(b_i的左端点<=min\{b_j的右端点\}\) 。

复杂度：由于会递归至多logn层，而每层的复杂度是树状数组的复杂度nlogn，总的复杂度是类似CDQ分治的 \(O(nlog^2n)\) 。

但是我感觉由于区间的长度实际上并不是每次都那么长，所以未必有这么坏。而假如造数据把所有的点都堆在很近的一个区间，那么根据我的递归的方法，应该层数又变少了。总而言之最坏是 \(O(nlog^2n)\) 但是可以过。

发现没有人给这道题贴分治的标签，果然我这个是歪门邪道吗……

vector<int> id[200005];
int la[200005], ra[200005];
int ax[200005], axtop;
int lb[200005], rb[200005];
int bx[200005], bxtop;
 
int maxbit[200005];
int minbit[200005];
 
int c;
 
void maxbit_update(int p, int v) {
    for(int x = p; x <= c; x += x & -x)
        maxbit[x] = max(maxbit[x], v);
}
 
void minbit_update(int p, int v) {
    for(int x = p; x <= c; x += x & -x)
        minbit[x] = min(minbit[x], v);
}
 
void maxbit_clear(int p) {
    for(int x = p; x <= c; x += x & -x)
        maxbit[x] = -INF;
}
 
void minbit_clear(int p) {
    for(int x = p; x <= c; x += x & -x)
        minbit[x] = INF;
}
 
int maxbit_query(int p) {
    int res = -INF;
    for(int x = p; x; x -= x & -x)
        res = max(res, maxbit[x]);
    return res;
}
 
int minbit_query(int p) {
    int res = INF;
    for(int x = p; x; x -= x & -x)
        res = min(res, minbit[x]);
    return res;
}
 
bool solve_a(int l, int r) {
    if(l == r) {
        if(id[l].size() <= 1)
            return true;
        int maxl = 0, minr = INF;
        for(auto &i : id[l]) {
            maxl = max(maxl, lb[i]);
            minr = min(minr, rb[i]);
        }
        if(minr >= maxl)
            return true;
        return false;
    }
    int m = (l + r) >> 1;
    bool res = solve_a(l, m) && solve_a(m + 1, r);
    if(res == 0)
        return false;
    for(int p = m + 1; p <= r; ++p) {
        for(auto &i : id[p]) {
            maxbit_update(la[i], lb[i]);
            minbit_update(la[i], rb[i]);
        }
    }
    for(int p = l; p <= m; ++p) {
        for(auto &i : id[p]) {
            int maxans = maxbit_query(ra[i]);
            int minans = minbit_query(ra[i]);
            if(!(minans >= lb[i] && maxans <= rb[i])) {
//                printf("minr=%d maxl=%d\n",minans,maxans);
//                printf("FALSE ON p=%d [%d,%d]\n", p, l, r);
                return false;
            }
        }
    }
    for(int p = m + 1; p <= r; ++p) {
        for(auto &i : id[p]) {
            maxbit_clear(la[i]);
            minbit_clear(la[i]);
        }
    }
    return true;
}
 
bool solve_b(int l, int r) {
    if(l == r) {
        if(id[l].size() <= 1)
            return true;
        int maxl = 0, minr = INF;
        for(auto &i : id[l]) {
            maxl = max(maxl, la[i]);
            minr = min(minr, ra[i]);
        }
        if(minr >= maxl)
            return true;
        return false;
    }
    int m = (l + r) >> 1;
    bool res = solve_b(l, m) && solve_b(m + 1, r);
    if(res == 0)
        return false;
    for(int p = m + 1; p <= r; ++p) {
        for(auto &i : id[p]) {
            maxbit_update(lb[i], la[i]);
            minbit_update(lb[i], ra[i]);
        }
    }
    for(int p = l; p <= m; ++p) {
        for(auto &i : id[p]) {
            int maxans = maxbit_query(rb[i]);
            int minans = minbit_query(rb[i]);
            if(!(minans >= la[i] && maxans <= ra[i])) {
//                printf("minr=%d maxl=%d\n",minans,maxans);
//                printf("FALSE ON p=%d [%d,%d]\n", p, l, r);
                return false;
            }
        }
    }
    for(int p = m + 1; p <= r; ++p) {
        for(auto &i : id[p]) {
            maxbit_clear(lb[i]);
            minbit_clear(lb[i]);
        }
    }
    return true;
}
 
void test_case() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d", &la[i], &ra[i], &lb[i], &rb[i]);
        ax[++axtop] = la[i];
        ax[++axtop] = ra[i];
        bx[++bxtop] = lb[i];
        bx[++bxtop] = rb[i];
    }
    sort(ax + 1, ax + 1 + axtop);
    axtop = unique(ax + 1, ax + 1 + axtop) - (ax + 1);
    sort(bx + 1, bx + 1 + bxtop);
    bxtop = unique(bx + 1, bx + 1 + bxtop) - (bx + 1);
    for(int i = 1; i <= n; ++i) {
        la[i] = lower_bound(ax + 1, ax + 1 + axtop, la[i]) - ax;
        ra[i] = lower_bound(ax + 1, ax + 1 + axtop, ra[i]) - ax;
        lb[i] = lower_bound(bx + 1, bx + 1 + bxtop, lb[i]) - bx;
        rb[i] = lower_bound(bx + 1, bx + 1 + bxtop, rb[i]) - bx;
//        printf("i=%d\n", i);
//        printf("  [%d,%d] [%d,%d]\n", la[i], ra[i], lb[i], rb[i]);
        id[ra[i]].push_back(i);
    }
    c = axtop;
    memset(maxbit, -INF, sizeof(maxbit[0]) * (axtop + 1));
    memset(minbit, INF, sizeof(minbit[0]) * (axtop + 1));
    bool res = solve_a(1, axtop);
    if(res == 1) {
        for(int i = 1; i <= n; ++i)
            id[ra[i]].clear();
        for(int i = 1; i <= n; ++i)
            id[rb[i]].push_back(i);
        c = bxtop;
        memset(maxbit, -INF, sizeof(maxbit[0]) * (bxtop + 1));
        memset(minbit, INF, sizeof(minbit[0]) * (bxtop + 1));
        res = solve_b(1, bxtop);
    }
    if(res)
        puts("YES");
    else
        puts("NO");
}