【JSOI2008】最大数

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1、查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：L不超过当前数列的长度。(L>=0)

2、插入操作。

语法：A n

功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

限制：n是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入输出格式

输入格式：

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)

接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式：

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

96
93
96
我得回去好好学一下语法了， 连char类型都不会用.....

 1 //2018年2月25日20:29:20
 2 #include <iostream>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 200010;
 7 
 8 int m, mod;
 9 int inf; 
10 
11 int mx[N<<2], size[N<<2];
12 
13 void change(int k1){
14     mx[k1] = max(mx[k1*2], mx[k1*2+1]);
15 }
16 
17 void buildtree(int k1, int l, int r){
18     size[k1] = r-l+1;
19     if(l == r){
20         mx[l] = 0;
21         return;
22     }
23     int mid = l+r >> 1;
24     buildtree(k1*2, l, mid);
25     buildtree(k1*2+1, mid+1, r);
26     change(k1);
27 }
28 
29 void change(int k1, int l, int r, int p, int q){
30     if(l == r){
31         mx[k1] += q;
32         return; 
33     }
34     int mid = l+r >> 1;
35     if(mid >= p) change(k1<<1, l, mid, p, q);
36     else change(k1<<1|1, mid+1, r, p, q);
37     change(k1); 
38 }
39 
40 int find(int k1, int l, int r, int L, int R){
41     if(l>R || r<L) return 0;
42     if(l>=L && r<=R) return mx[k1];
43     int mid = l+r >> 1;
44     return max( find(k1<<1, l, mid, L, R), find(k1<<1|1, mid+1, r, L, R) );
45 }
46 
47 int main(){
48     scanf("%d%d", &m, &mod);
49     
50     buildtree(1, 1, N);
51     int pos = 1, x=0;
52     for(int i=1;i<=m;i++){
53         char op; int n;
54         cin >> op >> n;
55         //scanf("%c %d", &op, &n); //用这个为什么不行啊？？？？？？？？ 
56         if(op == 'A'){
57             change(1, 1, N, pos++, (n+x)%mod);
58         }else if(op == 'Q'){
59             x = find(1, 1, N, pos-n, pos-1);
60             printf("%d
", x);
61         }
62         
63     }
64     
65     
66     return 0;
67 }