#P18876. [2026多校联测]矩形

[2026多校联测]矩形

矩形

题目描述

我们给你 nn 个矩形,第 ii 个矩形的左下角坐标为 (xai,yai)(xa_i,ya_i),右上角坐标为 (xbi,ybi)(xb_i,yb_i)。

qq 次操作,操作有以下两种类型:

  • Q l r 代表求 [l,r][l,r] 号矩形是否两两有公共点。

  • C l r x y 代表将 [l,r][l,r] 号矩形 xx 坐标对应变化 xx,yy 坐标对应变化 yy。注意,不保证 x,yx,y 为正数。

输入格式

第一行两个数 n,qn,q。

后面 nn 行每行四个数,分别是 xai,yai,xbi,ybixa_i,ya_i,xb_i,yb_i。

接着 qq 行,每行描述一个操作。

输出格式

对于每组 Q 操作,如果两两有交点输出 Yes,否则输出No。

输入输出样例 #1

3 6
0 0 2 2
1 1 3 3
4 4 5 5
Q 1 2
Q 1 3
C 3 3 -3 -3
Q 1 3
C 2 2 10 0
Q 1 3
Yes
No
Yes
No

说明/提示

本题捆绑测试。

Subtask 特殊性质 分值
11 1≤n,q≤1001 \le n,q \le 100 55
22 1≤n,q≤30001 \le n,q \le 3000 2525
33 保证没有修改操作 2020
44 1≤n,q≤1051 \le n,q \le 10^5 3030
55 无特殊性质 2020

对于 100%100\% 的数据,$1 \le n,q \le 5 \times 10^5,-10^{10} \le xa_i,xb_i,ya_i,yb_i,x,y \le 10^{10}$。保证所有输入均为整数。

对于样例 2∼62 \sim 6

样例 2∼62 \sim 6 依次满足 Subtask 1∼51 \sim 5 的要求。 附加样例 2∼62\sim6 可在样例文件中下载。