

Problem J. Rectangle Radar ScannerTime Limit: 20000/15000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 573 Accepted Submission(s): 172 Problem Description There are $n$ houses on the ground, labeled by $1$ to $n$. The $i$th house is located at $(i,y_i)$, and there is a spy transmitter with energy $w_i$ inside the $i$th house. Little Q has a rectangle radar scanner, which can find all the transmitters within the range $[xl,xr]\times[yl,yr]$. That means a transmitter located at $(x,y)$ can be found if $xl\leq x\leq xr$ and $yl\leq y\leq yr$. Your task is to achieve the scanner efficiently. Given $m$ queries $xl_i,xr_i,yl_i,yr_i$, for each query, please find all the transmitters within the range, then report the product of their energy and the maximum/minimum energy among them. To reduce the large input, we will use the following generator. The numbers $a_0,b_0,c_0,d_0,p,q,r$ and $MOD$ are given initially. The values $a_i,b_i,c_i,d_i,xl_i,xr_i,yl_i,yr_i$ are then produced as follows : \begin{eqnarray*} a_i&=&(p\times a_{i1}+q\times b_{i1}+r)\bmod MOD\\ b_i&=&(p\times b_{i1}+q\times a_{i1}+r)\bmod MOD\\ c_i&=&(p\times c_{i1}+q\times d_{i1}+r)\bmod MOD\\ d_i&=&(p\times d_{i1}+q\times c_{i1}+r)\bmod MOD\\ xl_i&=&\min(a_i\bmod n,b_i\bmod n)+1\\ xr_i&=&\max(a_i\bmod n,b_i\bmod n)+1\\ yl_i&=&\min(c_i\bmod n,d_i\bmod n)+1\\ yr_i&=&\max(c_i\bmod n,d_i\bmod n)+1 \end{eqnarray*} Input The first line of the input contains an integer $T(1\leq T\leq3)$, denoting the number of test cases. In each test case, there is an integer $n(1\leq n\leq 100000)$ in the first line, denoting the number of houses. In the next $n$ lines, each line contains $2$ integers $y_i,w_i(1\leq y_i\leq n,1\leq w_i\leq 10^9)$, describing a house. Then in the next line, there are $10$ integers $m,a_0,b_0,c_0,d_0,p,q,r,MOD,k$, describing the queries. It is guaranteed that $1\leq m\leq 10^6$ and $5\leq a_0,b_0,c_0,d_0,p,q,r,MOD,k\leq 10^9$. Output Since the output file may be very large, let's denote $prod_i$ as the product of of the $i$th query, $max_i$ as the maximum energy of the $i$th query, and denote $min_i$ as the minimum energy of the $i$th query. Note that when there are no avaliable transmitters, then $prod_i=max_i=min_i=0$. For each test case, you need to print a single line containing an integer $answer$, where : \begin{eqnarray*} answer&=&\sum_{i=1}^{m} ((prod_i\bmod k)\oplus max_i\oplus min_i) \end{eqnarray*} Note that ``$\oplus$'' denotes binary XOR operation. Sample Input
Sample Output
Source  
