1012: [JSOI2008]最大数maxnumber
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 12655 Solved: 5462
[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
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
93
96
HINT
数据如下http://pan.baidu.com/s/1i4JxCH3
思路:维护一个递减的单调队列,查询的时候二分找到最前的合法下标,复杂度O(m*logm)。
1 #include <iostream> 2 #include <fstream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <cmath> 7 #include <string> 8 #include <cstring> 9 #include <algorithm> 10 #include <queue> 11 #include <stack> 12 #include <vector> 13 #include <set> 14 #include <map> 15 #include <list> 16 #include <iomanip> 17 #include <cctype> 18 #include <cassert> 19 #include <bitset> 20 #include <ctime> 21 22 using namespace std; 23 24 #define pau system("pause") 25 #define ll long long 26 #define pil pair<int, ll> 27 #define pb push_back 28 #define mp make_pair 29 #define clr(a, x) memset(a, x, sizeof(a)) 30 31 const double pi = acos(-1.0); 32 const int INF = 0x3f3f3f3f; 33 const int MOD = 1e9 + 7; 34 const double EPS = 1e-9; 35 36 /* 37 #include <ext/pb_ds/assoc_container.hpp> 38 #include <ext/pb_ds/tree_policy.hpp> 39 40 using namespace __gnu_pbds; 41 tree<pli, null_type, greater<pli>, rb_tree_tag, tree_order_statistics_node_update> T; 42 */ 43 44 int n, q, _index; 45 ll d, x, t; 46 char op; 47 pil p[200015]; 48 int main() { 49 scanf("%d%lld", &q, &d); 50 while (q--) { 51 scanf(" %c %lld", &op, &x); 52 if ('A' == op) { 53 ll y = (x + t) % d; 54 while (_index && p[_index].second <= y) { 55 --_index; 56 } 57 p[++_index] = pil(++n, y); 58 } else { 59 int s = 1, e = _index, mi, ans, f = n - x; 60 while (s <= e) { 61 mi = s + e >> 1; 62 if (p[mi].first > f) { 63 e = (ans = mi) - 1; 64 } else { 65 s = mi + 1; 66 } 67 } 68 t = p[ans].second; 69 printf("%lld ", t); 70 } 71 } 72 return 0; 73 }