题解

题意解析：给定长度分别为 $n,m$ 的两组点对 $[(A_i,B_i)],[(C_i,D_i)]$。你可以重排 $[(A_i,B_i)]$。请你判断是否存在一种方式，使得对于所有 $1\le i\le n$，$A_i\le C_i$ 且 $B_i\le D_i$。

---

首先按 $A_i$ 从大到小排序。这样对于 $i\le j$，$A_i\ge A_j$。然后分类讨论。

• 如果 $B_i\ge B_j$：显然 $i$ 怎么选都不影响后面的。
• 如果 $B_i\lt B_j$：我们可以画图，发现 $i$ 选最下方的点是不劣的。

所以我们可以按如下方式选取：

找到 $D_i\ge B_i$ 且 $C_i\ge A_i$ 且 $D_i$ 最小的点。

现在的问题就转化成如何找到这个点。

我们可以先离散化一下 $D_i$，然后开 $m$ 个集合，将 $D_i$ 相同的点都放到同一个集合里。

然后问题就是找到最小的 $D_i$，使得 $D_i\ge B_i$ 且它对应的集合内存在一个 $C_i\ge A_i$，找到删除这个集合的元素即可。

显然可以线段树二分。

namespace cjdst{
    class Segtree{
		std::vector <int> tr;
		std::vector <int> left, right;
		std::vector <std::multiset <int>> a;
		void push_up(int u){
			tr[u] = std::max(tr[u << 1], tr[u << 1 | 1]);
		}
		void build(int u, int l, int r){
			left[u] = l, right[u] = r;
			if(l == r){
                if(!a[l].empty()) tr[u] = *a[l].rbegin();
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
			push_up(u);
		}
		bool _query(int u, int l, int val){
			if(right[u] < l) return 0;
			if(tr[u] < val) return 0;
			if(left[u] == right[u]){
				a[left[u]].erase(a[left[u]].lower_bound(val));
				if(a[left[u]].empty()) tr[u] = 0;
				else tr[u] = *a[left[u]].rbegin();
				
				return 1;
			}
			if(_query(u << 1, l, val)){
				push_up(u);
				return 1;
			}
			if(_query(u << 1 | 1, l, val)){
				push_up(u);
				return 1;
			}
			return 0;
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <pii> a){
			this -> a.resize(n + 5);
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			for(int i = 1; i <= n; i++){
				this -> a[a[i].second].insert(a[i].first);
			}
			build(1, 1, n);
		}
		bool query(int l, int val){
			return _query(1, l, val);
		}
	};
    void solve(){
		int n, m;
		std::cin >> n >> m;
		std::vector <pii> a(n + 5), b(m + 5);
		std::vector <int> lisan{0};
		for(int i = 1; i <= n; i++) std::cin >> a[i].first;
		for(int i = 1; i <= n; i++) std::cin >> a[i].second;
		for(int i = 1; i <= m; i++) std::cin >> b[i].first;
		for(int i = 1; i <= m; i++) std::cin >> b[i].second, lisan.push_back(b[i].second);
		std::sort(lisan.begin(), lisan.end());
		for(int i = 1; i <= m; i++){
			b[i].second = lower_bound(lisan.begin(), lisan.end(), b[i].second) - lisan.begin();
		}
		
		std::sort(a.begin() + 1, a.begin() + n + 1, cmp1);
		Segtree tr(m, b);
		for(int i = 1; i <= n; i++){
			int cur = lower_bound(lisan.begin(), lisan.end(), a[i].second) - lisan.begin();
			if(!tr.query(cur, a[i].first)){
				std::cout << "No\n";
				return;
			}
		}
		std::cout << "Yes\n";
	}
}

时间复杂度：$O(Tm\log m)$。