QMAX3VN - Giá trị lớn nhất 3

Following the journey to explore the real power of special data stuctures, two adventurers pirate and duyhung123abc continued to find new challenges with new more and more complicated problems. But what they earned was unremarkable. Being tired and stucked, they decided to review the problems they had solved to see what they had had so far. Suddenly, a mysterious light came to their mind: "why not combine some of them into one !". And here, QMAX3VN was born, as natural as the way fire had come to humankind.

It is said that in a morning at a military camp. All soldiers were gathering in a line to prepare for morning excercises. But the problem was they did not get up simultaneously. The line was initially empty. After sometime, a soldier got up and ran hurrily to join the line. Also, each of them liked to stand near their friends so they would elbow themselves to some position of the current line. What a messy and unacceptable scene for a military camp! The soldiers knew what they had done and were ready to be punished. The strict commander decided to give them a lesson. Everytime he gave an order(x,y), all soldiers in the line had to say loudly the height of the highest man among those were standing from position x to position y. Orders were made continuously since the first soldier entered the line. Punishment was waiting for whom would carried out the order incorrectly. The yard was full of worry from young soldiers. They really needed help !

Input

The input contains several lines:

  • Line 1 : An integer n (1 ≤ n ≤ 100000): The number of events occuring in that morning.
  • Line 2 to line n+1: Each line is one of the following two events:
    • A x y : A soldier with height x had just entered the line and elbowed himself into the position between position y-1 and position y of the line (-109 ≤ x ≤ 109; 1 ≤ y ≤ k+1 , k denotes the number of soldiers in the line right before this soldier came).
    • Q x y : An order of the commander. Find the height of the highest man among those were standing from position x to position y of the line (1 ≤ x ≤ y ≤ k , k denotes the number of soldiers was currently in the line).

 

Output

The output contains several lines:

  • For each order of the commander, write in one line the number all soldiers had to say loudly.

 

Example

Input:
10
A 1 1
A 2 2
Q 1 2
A 3 1
A 4 3
Q 2 4
A 5 2
Q 2 3
A 6 3
Q 1 4

Output:
2
4
5
6


Được gửi lên bởi:khanhptnk
Ngày:2009-05-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:Sưu tầm

hide comments
2021-05-27 18:03:34
Tham khảo: https://vnspoj.github.io/problems/QMAX3VN
2019-11-24 08:36:52
Mất mấy đấm vì scanf char :((
Đã AC bằng Splay Tree: https://ideone.com/LItAaf

Last edit: 2019-11-24 09:14:47
2019-10-03 09:12:45
Bài này dùng Segment Tree + xử lí Offline là AC rồi :v
2018-12-28 12:14:39
dùng treap mà ko dùng scanf printf giống như đánh bạc vậy, lúc được lúc ko :))
2018-11-25 15:26:00
ac sau 16 lần random =))
2018-06-20 05:57:33
ca* cung ac !
2016-08-20 16:39:08
lấy code QMAX4 sang là AC mà :))
2014-11-15 09:09:35 Nguyễn Thành Chinh
QMAX4 Ac nhưng lại ko aC kiểu này. ZZZZ
2014-07-30 20:43:54 No One
lạy các thánh >< khó qá X(
2014-07-09 06:40:48 LOVE VNOI
Dùng code QMAX4 đã ac sang QMAX3VN thì tạch, time chặt thật :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.