传送门
题意:n(1e5)个讲座,可以在a地点[sa,ea]时间内进行,或在b地点[sb,eb]时间内进行,如果在某个集合s中讲座可以在一个地点顺利召开,在另一个地点不能顺利召开(时间冲突),则称集合s是地点敏感的,问是否存在地点敏感的集合.
集合s不是地点敏感的当且仅当任意两个讲座都是地点不敏感的.
将讲座分别按sa,ea排序,将sb和eb离散化,依据a地点时间,依次用树状数组求与每个讲座在b地点时间不冲突的讲座个数,判断是否相等.
#include<bits/stdc++.h>
using namespace std;const int N = 2e5 + 5;
struct Point
{int sa, ea, sb, eb;
};
Point p[N], q1[N], q2[N];
int c1[N], c2[N], q[N], t;
void add(int c[], int i)
{for (; i; i -= i & -i)++c[i];
}
int query(int c[], int i)
{int ans = 0;for (; i <= t; i += i & -i)ans += c[i];return ans;
}
int n;
bool check1()
{t = 0;for(int i=1;i<=n;i++) { q[++t] = p[i].sb; q[++t] = p[i].eb; }sort(q + 1, q + t + 1);t = unique(q + 1, q + t + 1) - q - 1;for(int i=1;i<=n;i++) { p[i].sb = lower_bound(q + 1, q + t + 1, p[i].sb) - q; p[i].eb = lower_bound(q + 1, q + t + 1, p[i].eb) - q; }for(int i=1;i<=n;i++) q1[i] = q2[i] = p[i];sort(q1 + 1, q1 + n + 1, [&](const Point& a, const Point& b) {return a.sa < b.sa; });sort(q2 + 1, q2 + n + 1, [&](const Point& a, const Point& b) {return a.ea < b.ea; });for(int i=1;i<=t;i++) c1[i] = c2[i] = 0;int j = n;for(int i=n;i>=1;i--){while (q1[j].sa > q2[i].ea){add(c1, q1[j].sb);add(c2, t - q1[j].eb + 1);--j;}if (query(c1, q2[i].eb + 1) + query(c2, t - (q2[i].sb - 1) + 1) != n - j)return 0;}return 1;
}
bool check()
{cin>>n;for(int i=1;i<=n;i++){scanf("%d%d%d%d",&p[i].sa,&p[i].ea,&p[i].sb,&p[i].eb);}if (!check1())return 0;for(int i=1;i<=n;i++){swap(p[i].sa, p[i].sb);swap(p[i].ea, p[i].eb);}return check1();
}int main()
{puts(check() ? "YES" : "NO");
}