题目
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
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： 复制
5 100
A 96
Q 1
A 97
Q 1
Q 2
输出样例#1： 复制
96
93
96
说明
[JSOI2008]
本题数据已加强
分析
做法挺多的：线段树，单调栈，分块，ST表
我只用了线段树与单调栈两种^_^
（才不是懒）
代码
线段树做法：
1 /*
2 ID： Mandy
3 language：c++
4 problem：luogu 1198
5 */
6 #include<bits/stdc++.h>
7
8 #define N 1002
9 #define M 200005
10 #define maxl 8446744073709551616
11 #define Max(x,y) (x)>(y)?(x):(y)
12 #define Min(x,y) (x)<(y)?(x):(y)
13 #define up(i,l,r) for(int i=l;i<=r;++i)
14 #define down(i,l,r) for(int i=r;i>=l;--i)
15
16 using namespace std;
17
18 const int maxm=262143;
19 long long m,mod,lenth,maxn[M<<2],last,dep=0;
20 bool vis[M<<2];
21
22 template<class T>inline void read(T &x)
23 {
24 x=0;bool flag=0;char ch=getchar();
25 while(ch<'0'||ch>'9') flag|=(ch=='-'),ch=getchar();
26 while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
27 if(flag) x=-x;
28 }
29
30 template<class T>void putch(const T x)
31 {
32 if(x>9) putch(x/10);
33 putchar(x%10|48);
34 }
35
36 template<class T>inline void put(const T x)
37 {
38 if(x<0) putchar('-'),putch(-x);
39 else putch(x);
40 }
41
42 void docu()
43 {
44 freopen("1198.in","r",stdin);
45 freopen("1198.out","w",stdout);
46 }
47
48 void readdata()
49 {
50 read(m);
51 read(mod);
52 }
53
54 long long ask(int k,int l,int r,int x,int y)
55 {
56 if(l>y||r<x) return -maxl;
57 if(l>=x&&r<=y) return maxn[k];
58 else
59 {
60 int mid=(l+r)>>1;
61 long long ans=ask(k<<1,l,mid,x,y);
62 long long ans1=ask((k<<1)+1,mid+1,r,x,y);
63 if(ans<ans1) ans=ans1;
64 return ans;
65 }
66 }
67
68 void modify(int pos,long long val)
69 {
70 int l=1,r=200000,k=1;
71
72 while(l!=r)
73 {
74 int mid=(l+r)>>1;
75 if(pos<=mid) r=mid,k<<=1;
76 else l=mid+1,k=(k<<1)+1;
77 }
78
79 maxn[k]=val;
80 k>>=1;
81 while(k>=1)
82 {
83 maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);
84 k>>=1;
85 }
86 }
87
88 void work()
89 {
90 up(i,1,m)
91 {
92 char judge=getchar();
93 while(judge!='A'&&judge!='Q') judge=getchar();
94 long long x; read(x);
95 if(judge=='Q')
96 {
97 if(lenth==0)
98 {
99 putchar('0');
100 putchar('\n');
101 continue;
102 }
103 dep=0;
104 last=ask(1,1,200000,lenth-(x-1),lenth)%mod;
105 printf("%lld\n",last);
106 }
107 else
108 {
109 ++lenth;
110 x=(x+last)%mod;
111 modify(lenth,x);
112 }
113
114 }
115 }
116
117 int main()
118 {
119 //docu();
120 readdata();
121 work();
122 return 0;
123 }
View Code
单调栈做法：
1 /*************************
2 User:Mandy.H.Y
3 Language:c++
4 Problem:luogu1198 JSOI2008 最大数
5 Algorithm:
6 *************************/
7 #include<bits/stdc++.h>
8 #define Max(x,y) ((x)>(y)?(x):(y))
9
10 using namespace std;
11
12 const int maxm = 2e5 + 5;
13
14 int m,d,tp,cnt;
15 int s1[maxm],s2[maxm];
16 //s1 中单调递减，进了大数后，前面的小数就没用了
17 //s2 中存下相应的位置
18 char *TT,*mo,but[(1 << 15) + 2];
19 #define getchar() ((TT == mo && (mo = ((TT = but) + fread(but,1,1 << 15,stdin)),TT == mo)) ? -1 : *TT++)
20 template<class T>inline void read(T &x){
21 x = 0;bool flag = 0;char ch = getchar();
22 while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
23 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
24 if(flag) x = -x;
25 }
26
27 template<class T>void putch(const T x){
28 if(x > 9) putch(x / 10);
29 putchar(x % 10 | 48);
30 }
31
32 template<class T>void put(const T x){
33 if(x < 0) putchar('-'),putch(-x);
34 else putch(x);
35 }
36
37 void file(){
38 freopen("1198.in","r",stdin);
39 // freopen("1198.out","w",stdout);
40 }
41
42 void readdata(){
43 read(m);read(d);
44 }
45
46 int erfen(int x){
47 int l = 0,r = tp - 1;
48 while(l < r){
49 int mid = (l + r) >> 1;
50 if(s2[mid] < x) l = mid + 1;//找第1个大于等于x的位置
51 else r = mid;
52 }
53 return s1[l];
54 }
55
56 void work(){
57 int t = 0;
58 for(int i = 1;i <= m; ++ i){
59 char c = getchar();
60 int l,n;
61 while(c != 'Q' && c != 'A') c = getchar();
62 if(c == 'Q'){
63 read(l);
64 int ans = erfen(cnt - l + 1);//找位置
65 put(ans);
66 puts("");
67 t = ans;
68 } else {
69 ++cnt;
70 read(n);
71 n = ((long long)n + t) % d;
72 while(tp > 0 && s1[tp - 1] <= n) tp--;
73 s1[tp++] = n;
74 s2[tp - 1] = cnt;
75 }
76 }
77 }
78
79 int main(){
80 // file();
81 readdata();
82 work();
83 return 0;
84 }
View Code