首页 > > 程序设计 > C/C++ >

P1198 [JSOI2008]最大数

2018-06-17 22:37:46来源：未知阅读 ()

题目描述

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

1、查询操作。

语法：Q L

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

限制：L不超过当前数列的长度。

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

说明

[JSOI2008]

思路的话。

首先冲着最大值

建一颗空树

然后加入就是单点修改

查询就是插后面的m位。。。。

但是这题在洛谷上AC

在COGS上爆零

-.-

还有就是不能开读入优化

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define lglg long long int
 6 using namespace std;
 7 const int n=200001;
 8 lglg mod,m;
 9 struct node
10 {
11     lglg l,r,w;
12 }tree[n*4];
13 lglg num=1;
14 lglg last=0;
15 lglg ans=-1;
16 void updata(int k)
17 {
18     tree[k].w=max(tree[k*2].w,tree[k*2+1].w);
19 }
20 void build(int ll,int rr,int k)
21 {
22     tree[k].l=ll;tree[k].r=rr;
23     if(tree[k].l==tree[k].r)
24     {
25         tree[k].w=0;
26         return ;
27     }
28     int m=(ll+rr)/2;
29     build(ll,m,k*2);
30     build(m+1,rr,k*2+1);
31     updata(k);
32 }
33 int read(lglg &x)
34 {
35     int flag=0;
36     char c=getchar();x=0;
37     if(c=='-')flag=1;
38     while(c<'0'||c>'9')c=getchar();
39     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
40     return flag==1?x=-x:x;    
41 }
42 void point_add(int where,int p,int k)
43 {
44     if(tree[k].l==tree[k].r)
45     {
46         tree[k].w=p;
47         return ;
48     }
49     int m=(tree[k].l+tree[k].r)/2;
50     if(where<=m)
51         point_add(where,p,k*2);
52     else
53         point_add(where,p,k*2+1);
54     updata(k);    
55 }
56 void interval_ask(int ll,int rr,int k)
57 {
58     if(ll<=tree[k].l&&rr>=tree[k].r)
59     {
60         if(ans<tree[k].w)ans=tree[k].w;
61         return ;
62     }
63     int m=(tree[k].l+tree[k].r)/2;
64     if(ll<=m)
65         interval_ask(ll,rr,k*2);
66     if(rr>=m+1)
67         interval_ask(ll,rr,k*2+1);
68 }
69 int main()
70 {
71     //read(m);read(mod);
72     cin>>m>>mod;
73     build(1,n,1);
74     for(int i=1;i<=m;i++)
75     {
76         char c;
77         cin>>c;
78         if(c=='A')
79         {
80             lglg p;
81             //read(p);
82             cin>>p;
83             p=(p+last)%mod;
84             point_add(num++,p,1);
85         }
86         else
87         {
88             lglg p;
89             ans=-1;
90             //read(p);
91             cin>>p;
92             interval_ask(num-p,num-1,1);
93             last=ans%mod;
94             printf("%lld\n",ans);
95         }
96     }
97     return 0;
98 }