题目链接：https://codeforces.com/contest/1080/problem/F
题意：有k个线段所属在n个集合中，每次询问a b x y，问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内
题解：按照每个线段的有区间排序，然后按照右区间建立主席树，每个节点保存该位置的最右左区间，然后查询的时候即为对应所有位置的最右左区间的最小值，看是否大于x
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int N = 3e5 + 10; struct node1 { int l, r, id; bool operator <(const node1 &bb) const { return r < bb.r; } }a[N]; struct node { int l, r; int val; }tree[N * 22]; int n, m, k; int b[N], len; int root[N], tot; int update(int pre, int l, int r, int pos, int val) { int cur = ++tot; tree[cur] = tree[pre]; if(l == r) { // cout << l << " -- " << val << endl; tree[cur].val = max(tree[cur].val, val); return cur; } int mid = (l + r) >> 1; if(pos <= mid) tree[cur].l = update(tree[pre].l, l, mid, pos, val); else tree[cur].r = update(tree[pre].r, mid + 1, r, pos, val); tree[cur].val = min(tree[tree[cur].l].val, tree[tree[cur].r].val); return cur; } int query(int rt, int l, int r, int pl, int pr) { if(pl <= l && r <= pr) return tree[rt].val; int res = INF; int mid = (l + r) >> 1; if(pl <= mid) res = min(res, query(tree[rt].l, l, mid, pl, pr)); if(pr >= mid + 1) res = min(res, query(tree[rt].r, mid +1, r, pl, pr)); return res; } string s[2]; int main() { s[0] = "yes"; s[1] = "no"; scanf("%d %d %d", &n, &m, &k); for(int i = 1; i <= k; i++) { scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].id); b[i] = a[i].r; } sort(a + 1, a + 1 + k); sort(b + 1, b + 1 + k); for(int i = 1; i <= k; i++) { // cout << a[i].id << " " << a[i].l <<endl; root[i] = update(root[i - 1], 1, n, a[i].id, a[i].l); } len = k; int pos; int l, r, x, y; while(m--) { scanf("%d %d %d %d", &l, &r, &x, &y); pos = upper_bound(b + 1, b + 1 + len, y) - b; pos--; // cout << pos << endl; if(query(root[pos], 1, n, l, r) >= x) cout << "yes" << endl;; else cout << "no" << endl;; } return 0; }
