6906.Lines and Queries II

Time Limit: 1s Memory Limit: 512MB

Your task is to efficiently process the following types of queries:

Add a lineax+bthat is active in range[l,r]Find the maximum point in any active line at positionx

Input Format(From the terminal/stdin)

The first line has an integer $n$ : the number of queries.

The following $n$ lines describe the queries. The format of each line is either "1 $a$ $b$ $l$ $r$ " or "2 $x$ ".

  • $1 \le n \le 2 \cdot 10^5$
  • $-10^9 \le a,b \le 10^9$
  • $0 \le x \le 10^5$
  • $0 \le l \le r \le 10^5$

Output Format(To the terminal/stdout)

Print the answer for each query of type 2. If no line is active, print NO .

Sample Input

Copy 
6
1 1 2 1 3
2 3
2 4
1 0 4 1 5
2 3
2 4
 \n
 · · · · \n
 · \n
 · \n
 · · · · \n
 · \n
 · \n

Sample Output

Copy 
5
NO
5
4
 \n
  \n
 \n
 \n
Source: CSES, Geometry, 3430

Submit

请先 登录
 Submit
题解(0)
© 2025 FAQs