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
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.