[bzoj1012](JSOI2008)最大數maxnumber(Fenwick Tree)

Description

現在請求你維護一個數列，要求提供以下兩種操作： 1、 查詢操作。語法：Q L 功能：查詢當前數列中末尾L個數中的最大的數，并輸出這個數的值。限制：L不超過當前數列的長度。 2、 插入操作。語法：A n 功能：將n加上t，其中t是最近一次查詢操作的答案（如果還未執行過查詢操作，則t=0)，并將所得結果對一個固定的常數D取模，將所得答案插入到數列的 末尾。限制：n是非負整數并且在長整范圍內。注意：初始時數列是空的，沒有一個數。

Input

第一行兩個整數，M和D，其中M表示操作的個數(M <= 200,000)，D如上文中所述，滿足(0

Output

對于每一個查詢操作，你應該按照順序依次輸出結果，每個結果占一行。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96

分析

? ?? 由于區間min/max信息不可減，這里似乎不可能直接用樹狀數組實現。但我們發現，這里的插入和查詢都是在末尾進行的，如果我們把數組倒過來，每次在前面插入一個數，或者查詢一個前綴數組的最值，就只需要利用最值的可合并性質就可以實現了。

? ?? ——本來以為我這個做法爆掉了線段樹還可以排進前幾名來著……然而衡中的ztx同學卻發現這個數組的最值信息可以直接用一個單調數組（棧）維護，而查詢操作只要在數組上二分查找L就可以了……給跪了Orzorzorz

?

?1?/**************************************************************
?2?????Problem:?1012
?3?????User:?AsmDef
?4?????Language:?C++
?5?????Result:?Accepted
?6?????Time:364?ms
?7?????Memory:2836?kb
?8?****************************************************************/
?9??
10?//Asm_Def
11?#include?<iostream>
12?#include?<cctype>
13?#include?<cstdio>
14?#include?<vector>
15?#include?<algorithm>
16?#include?<cmath>
17?#include?<queue>
18?using?namespace?std;
19?template<typename?T>inline?void?getd(T?&x){
20?????char?c?=?getchar();
21?????bool?minus?=?0;
22?????while(!isdigit(c)?&&?c?!=?'-')c?=?getchar();
23?????if(c?==?'-')minus?=?1,?c?=?getchar();
24?????x?=?c?-?'0';
25?????while(isdigit(c?=?getchar()))x?=?x?*?10?+?c?-?'0';
26?????if(minus)x?=?-x;
27?}
28?/*======================================================*/
29?const?int?maxn?=?200002;
30?typedef?long?long?LL;
31?inline?int?lowbit(int?x){return?x?&?-x;}
32?struct?Fenwick{
33?????LL?A[maxn];
34?????int?iter;
35?????Fenwick():iter(maxn?-?1){}
36?????inline?void?insert(LL?x){
37?????????A[iter]?=?x;
38?????????int?i?=?iter?+?lowbit(iter);--iter;
39?????????while(i?<?maxn){
40?????????????if(x?>?A[i])A[i]?=?x;
41?????????????i?+=?lowbit(i);
42?????????}
43?????}
44?????inline?int?getmax(int?L){
45?????????int?i?=?iter?+?L,?ans?=?0;
46?????????while(i?>=?iter){
47?????????????if(ans?<?A[i])ans?=?A[i];
48?????????????i?^=?lowbit(i);
49?????????}
50?????????return?ans;
51?????}
52?}BIT;
53?int?main(){
54?????#if?defined?DEBUG
55?????freopen("test",?"r",?stdin);
56?????#else
57?????//freopen("bzoj_1012.in",?"r",?stdin);
58?????//freopen("bzoj_1012.out",?"w",?stdout);
59?????#endif
60?????LL?D,?x,?t?=?0;
61?????int?M,?opt;
62?????getd(M),?getd(D);
63?????while(M--){
64?????????while(!isalpha(opt?=?getchar()));
65?????????getd(x);
66?????????if(opt?==?'Q')
67?????????????printf("%d\n",?t?=?BIT.getmax(x));
68?????????else?BIT.insert((t?+?x)?%?D);
69?????}
70??????
71??????
72?????#if?defined?DEBUG
73?????cout?<<?endl?<<?(double)clock()/CLOCKS_PER_SEC?<<?endl;
74?????#endif
75?????return?0;
76?}

?