题目大意

给定 kk 条线段，分成 nn 组，每组标号 1,2,3,…,n1,2,3,\dots,n，每次询问标号为 a,a+1,a+2,…,ba,a+1,a+2,\dots,b 的集合中，是否都有至少一条线段满足 x≤l≤r≤yx\le l\le r\le y，强制在线。

思路

居然还能用交互来强制在线。

看到这道题第一时间想到的是主席树，因为这道题在区间里询问一个区间问题。一开始，我想到的是按照线段所属集合从小到大排序后依次塞到主席树里面，但这样貌似只能解决询问集合里有多少条线段满足条件，并不能判断是否每个集合都包含一条满足要求的线段。

所以我们考虑转化问题。

思考如果只有一个集合怎么办，显然可以这样：先对于所有右端点小于等于 ii 的线段，求出它们最大的那个左端点 ll，记为 wiw_i，对于每一次询问，如果满足 x≤wyx\le w_y，则说明有至少一条满足要求的线段，如果 x>wyx>w_y，那么就没有。

证明一下这个方法的正确性，首先由于 wyw_y 表示的是右端点小于等于 yy 的线段中最大的左端点，所以这些线段的右端点 rr 很明显都是满足 r≤yr\le y 的。如果在这些线段中存在一条满足要求的线段，也就是说存在一个 ll 大于等于 xx，那么 wyw_y 显然一定是大于等于 ll 的，而如果不存在一条满足要求的线段，也就是说所有 ll 都小于 xx，那么 wyw_y 也就一定是小于 xx 的了。

接下来，我们考虑如何将这个方法推广到多个集合。

可以看出，上面提到的这个方法有点像前缀和，这启发我们用主席树来维护这一过程，具体来说，用主席树第 ii 个根的第 jj 个儿子表示集合 jj 中所有右端点小于等于 ii 的线段中左端点的最大值（也就是上面的 wiw_i），这样，对于每一次询问 a,b,x,ya,b,x,y，我们只需要看第 yy 棵线段树的 [a,b][a,b] 这个区间里的值是否全都大于等于 xx 就行了，但我们总不能把这些叶子节点全都遍历一次吧，所以我们可以维护这些 wyw_y 的最小值，如果这个最小值都是大于等于 xx 的，那一定所有集合里都包含一条满足要求的线段，如果这个最小值小于 xx，就说明至少存在一个集合，不存在一条满足要求的线段。

对了，由于右端点不一定是连续的，所以我们建树时可以用下标来代替，在询问时二分一下，找到对应的根就行了。

还有一点，如果在查询时访问到了一个不存在的节点，而它对应的区间又包含了一部分（或全部）要查询的区间，则说明被它包含的这部分区间里不存在一条右端点小于等于 yy 的线段，直接返回一个极小值就行了，在 pushup 的时候，如果一个节点只有左儿子或是只有右儿子，那也直接赋成一个极小值就行了，这样如果它被要查询的区间完全包含，返回的值才正确（道理同上）。

具体的还是看代码吧，我语文有点差，可能表述不太清楚。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10, inf = 0x3f3f3f3f;
struct Segment
{
	int l;
	int r;
	int p;
	bool operator < (Segment const & x) const
	{
		return r == x.r ? (l == x.l ? p < x.p : l < x.l) : r < x.r;
	}
};
struct SegTree
{
	int ls;
	int rs;
	int dat;
};
SegTree tree[N*30];
Segment q[N];
int n, m, k, tot, c[N], rt[N];
inline void push_up(int i)
{
	if(tree[i].ls && tree[i].rs)//这里要注意，只有同时有左右儿子时才取它们的较小值，否则都直接赋成 0
		tree[i].dat = min(tree[tree[i].ls].dat, tree[tree[i].rs].dat);
	else
		tree[i].dat = 0;
}
void update(int &i, int p, int l, int r, int x, int k)
{
	i = ++tot;
	tree[i] = tree[p];
	if(l == r)
	{
		tree[i].dat = max(tree[i].dat, k);
		return;
	}
	int mid = (l+r)>>1;
	if(x <= mid)
		update(tree[i].ls, tree[p].ls, l, mid, x, k);
	else
		update(tree[i].rs, tree[p].rs, mid+1, r, x, k);
	push_up(i);
}
int query(int i, int l, int r, int x, int y)
{
	if(!i)//上面讲过了，直接返回一个极小值
		return 0;
	if(x <= l && y >= r)
		return tree[i].dat;
	int mid = (l+r)>>1, ans = inf;
	if(x <= mid)
		ans = min(ans, query(tree[i].ls, l, mid, x, y));
	if(mid+1 <= y)
		ans = min(ans, query(tree[i].rs, mid+1, r, x, y));
	return ans;
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= k; i++)
	{
		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].p);
		c[i] = q[i].r;
	}
	sort(c+1, c+1+k);
	sort(q+1, q+1+k);
	for(int i = 1; i <= k; i++)
		update(rt[i], rt[i-1], 1, n, q[i].p, q[i].l);
	while(m--)
	{
		int a, b, x, y;
		scanf("%d%d%d%d", &a, &b, &x, &y);
		y = upper_bound(c+1, c+1+k, y)-c-1;
		if(y == 0)
			printf("no\n");
		else
			if(query(rt[y], 1, n, a, b) < x)
				printf("no\n");
			else
				printf("yes\n");
		fflush(stdout);
	}
	return 0;
}

关于y = upper_bound(c+1, c+1+k, y)-c-1;这一句，我看到有的大佬是手写的二分，这样子少了一个排序，常数会小一点（然而因为我懒所以就没写）。

反思

思维还不够开阔，没有想到转化问题，虽然都想到主席树上去了，但就是搞不出来，对这种数据结构的理解还不够深入，应当再多加练习才行。