Tom and Jerry love matrices

2.9

17 votes
Segment Trees, DFS, Advanced Data Structures, Data Structures, Pointer, Math
Problem

Tom and Jerry are playing with matrices. Jerry gifts Tom with a matrix of size M×N. The matrix element have a unique property that each cell of the matrix has value Ai,j=X+i+j. Since Tom loves challenges, Jerry will give Tom Q queries. Each of these queries can be of any of the following three types:

  1. R C1 C2: Delete the cells in the Row R starting from column C1 and ending at column C2 (1C1C2N,1RM) 
  2. C R1 R2: Delete the cells in column C starting from row R1 and ending at row R2 (1R1R2M,1CN).
  3. K: Take all the remaining elements in the array and sort the elements by their values. Now, return the Kth smallest element. If K is greater than the number of elements remaining, then print 1.(1K109)

You are required to print the output only in case of the queries of type 3. You must help Tom to solve the tasks and answer the queries given by Jerry.

Input format

  • The first line of input contains four integers, M, N, X, and Q (1N,M,X109,1Q5105). Here, Q is the number of queries and M and N are the dimensions of the matrix. 
  • The next Q lines contain queries of the type mentioned in the question. 
    • 1 A B C for queries of type 1
    • 2 A B C for queries of type 2
    • 3 A for queries of type 3

No two deleted sub rows or subcolumns will intersect, that is the segments queried to be deleted are disjoint.

Output format

For queries of type 3, print a single integer on a new line corresponding to the answer of that query as mentioned in the question.

Time Limit: 3
Memory Limit: 1024
Source Limit:
Explanation

12 is the smallest element when query 3 1 is made.

Editor Image

?