Katya and Segments Sets

题意翻译

## 题目描述 给你n个集合，集合中的元素是线段，每个线段用左右端点$[l,r],l\le r$描述。每个集合可以包含任意个线段（包括0个），允许存在相同的线段 有m个询问，每个询问形如$a,b,x,y$，问对于编号在$[a,b]$之间的集合，是不是每一个都包含一个满足$x\le l\le r\le y$的线段，是则输出"yes"，否则输出"no" 强制在线，处理完每个询问后立刻输出结果，然后才能读入下一个询问（具体见输出格式） ## 输入输出格式 ### 输入格式： 第一行包含3个整数$n,m,k(1\le n,m\le 10^5,1\le k\le 3×10^5)$分别是集合数、询问数、线段个数。 接下来$k$行每行3个整数$l,r,p(1\le l\le r\le 10^9,1\le p\le n)$表示一条线段，$l,r$为左右端点，$p$为它所属的集合 接下来$m$行每行四个整数$a,b,x,y(1\le a\le b\le n,1\le x\le y\le 10^9)$表示一个询问，$a,b,x,y$的含义如题目描述所示 ### 输出格式： 对每个询问输出"yes"或"no"，每个询问占一行 每次输出后需要刷新输出缓存，否则会TLE 方法如下： - C++: fflush(stdout)或cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他的自己查 ## 说明 第一个询问答案是no，因为第二个集合不包含一个在$[2,3]$之间的线段 对于第二个询问，第一个集合包含$[2,3]$，第二个集合包含$[2,4]$ 对于第三个询问，第一个集合包含$[2,3]$，第二个集合包含$[2,4]$，第三个集合包含$[2,5]$ 对于第四个询问，第二个集合不包含一个在$[3，6]$之间的线段 对于第五个询问，第二个集合包含$[2,4]$，第三个集合包含$[2,5]$，第四个集合包含$[7,9]$

题目描述

It is a very important day for Katya. She has a test in a programming class. As always, she was given an interesting problem that she solved very fast. Can you solve that problem? You are given $ n $ ordered segments sets. Each segment can be represented as a pair of two integers $ [l, r] $ where $ l\leq r $ . Each set can contain an arbitrary number of segments (even $ 0 $ ). It is possible that some segments are equal. You are also given $ m $ queries, each of them can be represented as four numbers: $ a, b, x, y $ . For each segment, find out whether it is true that each set $ p $ ( $ a\leq p\leq b $ ) contains at least one segment $ [l, r] $ that lies entirely on the segment $ [x, y] $ , that is $ x\leq l\leq r\leq y $ . Find out the answer to each query. Note that you need to solve this problem online. That is, you will get a new query only after you print the answer for the previous query.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ k $ $ (1\leq n,m\leq 10^5, 1\leq k\leq 3\cdot10^5) $ — the number of sets, queries, and segments respectively. Each of the next $ k $ lines contains three integers $ l $ , $ r $ , and $ p $ $ (1\leq l\leq r\leq 10^9, 1\leq p\leq n) $ — the limits of the segment and the index of a set, to which this segment belongs. Each of the next $ m $ lines contains four integers $ a, b, x, y $ $ (1\leq a\leq b\leq n, 1\leq x\leq y\leq 10^9) $ — the description of the query.

输出格式

For each query, print "yes" or "no" in a new line. Interaction After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages.

输入输出样例

输入样例 #1

5 5 9
3 6 3
1 3 1
2 4 2
1 2 3
4 6 5
2 5 3
7 9 4
2 3 1
4 10 4
1 2 2 3
1 2 2 4
1 3 1 5
2 3 3 6
2 4 2 9

输出样例 #1

no
yes
yes
no
yes

说明

For the first query, the answer is negative since the second set does not contain a segment that lies on the segment $ [2, 3] $ . In the second query, the first set contains $ [2, 3] $ , and the second set contains $ [2, 4] $ . In the third query, the first set contains $ [2, 3] $ , the second set contains $ [2, 4] $ , and the third set contains $ [2, 5] $ . In the fourth query, the second set does not contain a segment that lies on the segment $ [3, 6] $ . In the fifth query, the second set contains $ [2, 4] $ , the third set contains $ [2, 5] $ , and the fourth contains $ [7, 9] $ .