首页 > 代码库 > BZOJ 1012 题解

BZOJ 1012 题解

2024-08-16 16:50:25   222人阅读

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 8468  Solved: 3702
[Submit][Status][Discuss]

Description

　　现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L
个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加
上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取
模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个
数。

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来
M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

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

Sample Output

96
93
96

Solution 

 题目中要求边插入，边查询，于是想到用线段树.
技术分享
 1 /************************************************************** 2     Problem: 1012 3     User: shadowland 4     Language: C++ 5     Result: Accepted 6     Time:844 ms 7     Memory:24732 kb 8 ****************************************************************/ 9  10 #include "bits/stdc++.h"11  12 using namespace std ;13 const int maxN = 500100 ;14 const int INF = 2147483647 ;15 struct SegTree { int l , r , maxtr ; } ;16  17 SegTree tr[ maxN << 2 ] ;18  19 int pos , cnt , last ; 20  21 inline int gmax ( int x , int y ) { return x > y ? x : y ; }22 inline void Push_up ( const int i ) { tr[ i ].maxtr = gmax ( tr[ i << 1 | 1 ].maxtr , tr[ i << 1 ].maxtr ) ; }23  24 int INPUT ( ) {25         int x = 0 , f = 1 ; char ch = getchar ( ) ;26         while ( ch < ‘0‘ || ch > ‘9‘ ) { if ( ch == ‘-‘ ) f = -1 ; ch = getchar ( ) ; }27         while ( ch >= ‘0‘ && ch <= ‘9‘ ) { x = ( x << 1 ) + ( x << 3 ) + ch - ‘0‘ ; ch = getchar ( ) ;}28         return x * f ; 29 } 30  31  32 void Build_Tree ( const int x , const int y , const int i ) {33         tr[ i ].l = x ; tr[ i ].r = y ;34         tr[ i ].maxtr = -INF ;35         if ( x == y ) return ;36         else {37                 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;38                 Build_Tree ( x , mid , i << 1 ) ;39                 Build_Tree ( mid + 1 , y , i << 1 | 1 ) ;40                 Push_up ( i ) ;41         }42 }43  44 void Insert ( const int q , const int val , const int i ) {45         if ( tr[ i ].l == tr[ i ].r && tr[ i ].l == q ) {46                 tr[ i ].maxtr = val ;47                 return ;48         }49         else {50                 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;51                 if ( q > mid ) Insert ( q , val , i << 1 | 1 ) ;52                 else if ( q <= mid ) Insert ( q , val , i << 1 ) ;53                 Push_up ( i ) ; 54         }55 }56  57 int Query_Tree ( const int q , const int w , const int i ){58         if ( q <= tr[ i ].l && tr[ i ].r <= w ) {59                 return tr[ i ].maxtr ;60         }61         else {62                 int mid = ( tr[ i ].l + tr[ i ].r ) >> 1 ;63                 if ( q > mid ) return Query_Tree ( q , w , i << 1 | 1 ) ;64                 else if ( w <= mid ) return Query_Tree ( q , w , i << 1 ) ;65                 else {66                         return gmax ( Query_Tree ( q , w , i << 1 | 1 ) , Query_Tree ( q , w , i << 1 ) ) ;67                 }68         }69 }70  71 int main ( ) {72         int N = INPUT ( ) , MOD = INPUT ( ) ;73         Build_Tree ( 1 , N , 1 ) ;74         for ( int i=1 ; i<=N ; ++i ) {75                 char ch = getchar ( ) ;76                 if ( ch == ‘A‘ ) {77                         ++cnt ; 78                         int tmp = ( INPUT ( ) + last ) % MOD ;79                         Insert ( cnt , tmp , 1 ) ;80                 }81                 else if ( ch == ‘Q‘ ) {82                         last = Query_Tree ( cnt - INPUT ( ) + 1 , cnt , 1 ) ;83                         printf ( "%d\n" , last ) ;84                 }85         }86         return 0 ;87 }
View Code

2016-10-14 23:31:51

 (完)
 
 

BZOJ 1012 题解


联系
我们