[bzoj] 1012: [JSOI2008]最大数maxnumber

发表于   |   分类于   |  

题意

　　树状数组维护区间最值

传送门

分析

　　可以好好画画图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#define  lb(x) (x&(-x))
#define  maxn  200010LL
#define  max(x,y) ((x)>(y)?(x):(y))

int m , LAST = 0 , ansmod ;
int A[maxn] , C[maxn] = {0} , tot = 0 ;

inline int QueryMax(int L , int R) {
trueint ret = A[R] ;
truewhile (L <= R) {
truetrueif (A[R] > ret) ret = A[R] ;
truetruefor ( -- R ; R-L >= lb(R) ; R -= lb(R))
truetruetrueif (C[R] > ret) ret = C[R] ;
true}
truereturn ret ;
}

inline void Insert(int x) {
trueA[++tot] = (LAST+x)%ansmod ;
trueC[tot] = max(QueryMax(tot-lb(tot)+1 , tot-1) , A[tot]) ;
}

int cmd , x ;
int main() {
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(m) , read(ansmod) ;
truewhile (m -- ) {
truetruereads(cmd) , read(x) ;
truetrueif (cmd == 'A') Insert(x) ;
truetrueelse printf("%d\n", LAST=QueryMax(tot-x+1 , tot)) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章