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

Tiếp tục hành trình khám phá sức mạnh của các cấu trúc dữ liệu đặc biệt, hai nhà thám hiểm pirateduyhung123abc lại lao vào những thử thách với những bài toán hóc búa mới. Nhưng những gì họ thu thập được chẳng là bao. Chán chường và bế tắc, họ quyết định lật giở những bài toán đã giải để xem lại những thành quả đã đạt được. Đột nhiên, một thứ ánh sáng lạ kì lóe lên trong đầu họ: "Tại sao không kết hợp một số bài toán lại với nhau !" . Và đây, QMAX3VN đã ra đời, tự nhiên như cái cách mà lửa đã đến với loài người.

Chuyện kể rằng vào một buổi sáng nọ trong một doanh trại quân đội, các quân nhân đang tập trung thành một hàng ngang để chuẩn bị tập thể dục buổi sáng. Nhưng vấn đề là không phải tất cả họ đều dậy cùng một lúc. Ban đầu, hàng ngang chẳng có người nào. Sau một lúc, lại có một anh chàng quân nhân hộc tốc chạy ra. Mỗi anh chàng lại thích đứng cạnh ai đó, nên cứ nhất quyết chen vào một vị trí nào đó trong hàng. Thật là một cảnh tượng hỗn độn và không thể chấp nhận. Mặt ai cũng cúi gằm xuống đất chuẩn bị chịu sự trừng phạt của viên chỉ huy. Viên chỉ huy, tuy nghiêm khắc nhưng cũng rất nhân hậu, đã đưa một trò chơi như sau để cho các anh chàng một bài học. Mỗi khi ông ta đưa ra một khẩu lệnh (x,y) thì lập tức các quân nhân phải chỉ vào người cao nhất trong các quân nhân đang đứng từ vị trí x đến vị trí y trong hàng. Khẩu lệnh sẽ được phát ra liên tục từ khi có một quân nhân bước vào hàng. Hình phạt đang chờ những người làm sai khẩu lệnh. Sân tập ướt đẫm những giọt mồ hồi lo lắng của các cậu lính trẻ. Họ đang cần sự giúp đỡ của bạn!

Input

Dữ liệu vào gồm nhiều dòng:

  • Dòng thứ 1 : Một số nguyên n (1 ≤ n ≤ 100000): Số sự kiện sẽ diễn ra trong buổi tập thể dục.
  • Dòng thứ 2 đến dòng thứ n+1: Mỗi dòng là một trong hai sự kiện:
    • A x y : Một quân nhân có chiều cao x vừa chen vào giữa vị trí thứ y-1 và y trong hàng (-109 ≤ x ≤ 109; 1 ≤ y ≤ k+1 , với k là số anh lính hiện có trong hàng).
    • Q x y : Khẩu lệnh của viên chỉ huy. Hãy tìm chiều cao của người cao nhất trong các quân nhân đang đứng từ vị trí thứ x đến vị trí thứ y trong hàng (1 ≤ x ≤ y ≤ k , với k là số anh lính hiện có trong hàng).

 

Output

Dữ liệu ra gồm nhiều dòng:

  • Với mỗi khẩu lệnh của viên chỉ huy, ghi trên một dòng chiều cao của người mà các quân nhân cần phải chỉ vào.

 

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
2014-06-04 01:50:56 Stupid Dog
Viết văn hay quá
2014-02-25 14:32:34 Nguyen Tien Trung Kien
Các bạn dùng cái gì để code vậy? Segment tree + xử lý offline hay là splay tree/AVL/...?
2013-11-11 05:18:03 a;slkfjasl;fkj


Last edit: 2014-01-19 12:54:24
2012-10-21 21:24:21 TNO
Ơ, chiều cao của quân nhân có thể là số âm :D
2009-05-08 17:12:07 Nguyễn Xuân Khánh
Cám ơn các anh đã đóng góp cho đề bài :)) . Mong tiếp tục nhân được sự góp ý về bộ test.

Last edit: 2009-05-08 17:15:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.