KOPC12G - K12-Bored of Suffixes and Prefixes
You are given a matrix of size NxN containing only upper case alphabets .You have to perform two kinds of operations:
Replace operation is to replace a row or column of the matrix with the given string.
Count Operation returns the count of each alphabet in the required region.
The operations are given as
0 x y str -> Replace y th row with string str, if x=0 or update yth column with string str (top to bottom), if x=1
1 x1 y1 x2 y2 -> Count the number of each alphabets in the rectangular region of the matrix where (x1,y1) is top-left point of the rectangle and (x2,y2) is the bottom-right point of the rectangle.
For every Count operation output the value of (1*number of A's + 2*number of B's + ...... 26*number of Z's).
The first line of the input file contains T which denotes the number of test cases.
The first line of each test case contains two integers N and q where N denotes size of the matrix and q denotes the number of queries. This is followed by NxN alphabetic matrix. The matrix is followed by q lines of queries, in the above given format.
0<=x1<N, 0<=x2<N, 0<=y1<N, 0<=y2<N
Warning: Huge I/O
Print the output for each query line by line.
Input: 1 4 3 ABCD ABCD ABCD ABCD 1 0 0 3 3 0 0 2 PQRS 1 0 2 3 3 Output: 40 58
Theoretically O(N*Q) could be optimal, if number updates is at least comparable with the number of queries. Then the test case size is O(N*N + N*Q) (in bytes).
O(NQlogN) also will pass!Last edit: 2012-03-12 12:44:40
~ adieus ~:
O(NQ) will pass !