HLG 1752 Page Rank （线段树）

链接： http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1752

Description

There are n webpages, each of which has its respective page rank. The content is constantly updated and page rank is also constantly changing. Can you immediately find the page with highest weight?

Note: We set the page numbers from 1 to n.

Input

There are multiple test cases, process to the end of file.

For each test case:

Line 1: This line contains an integer n, indicating the number of pages.

Line 2: This line contains n integer, pr1, pr2, pr3, ..., prn, representing the page rank of each page.

Line 3: This line contains an integer q, indicating the number of operations.

Line 4..q+3: Each line indicating an operation.

There are two operation formats:

C i pr : change ith page‘s page rank to pr.

Q : query a page with the highest page rank, output the page‘s number and its page rank.

Limits

1<=n<=100,000

1<=q<=200,000

0<=pr<=1,000,000,000

Output

For each case:

Each "Q" query outputs a line containing the page number and page rank of the page of the highest page rank. If there is more than one page which has the highest page rank, output the page with largest number.

After each test case, output a blank line.

Sample Input

5

30 9 0 20 5

6

C 1 19

C 3 22

C 3 4

Q

C 4 12

13 10 20 7 7

7

C 4 22

C 4 21

C 4 11

C 3 10

C 5 15

C 2 17

Sample Output

4 20

1 19

2 17

代码如下：