【BZOJ1012】[JSOI2008]最大数值问题：ST表优化解决方案

Description

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

Input

第一行两个整数&＃xff0c;M和D&＃xff0c;其中M表示操作的个数(M <&＃61; 200,000)&＃xff0c;D如上文中所述&＃xff0c;满足(0

Output

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

Sample Input

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


Sample Output

969396


HINT

Source

bzoj大水题&＃xff0c;st表直接水过去。

代码&＃xff1a;

#include
#include
#include
#include
#include
using namespace std;
const int size&＃61;1000010;
int st[size][30];int main()
{
// freopen("1012.in","r",stdin);
// freopen("1012.out","w",stdout); int m,mod,n&＃61;0;scanf("%d%d",&m,&mod);int lastans&＃61;0;while(m--){char in[10];int a;scanf("%s%d",in,&a);switch(in[0]){case &＃39;A&＃39;:st[&＃43;&＃43;n][0]&＃61;(a&＃43;lastans)%mod;for(int i&＃61;1;i<&＃61;log2(n);i&＃43;&＃43;) st[n][i]&＃61;max(st[n][i-1],st[n-(1<<(i-1))][i-1]);/* for(int i&＃61;n;i>&＃61;1;i--){for(int j&＃61;0;j<&＃61;log2(n);j&＃43;&＃43;){printf("%d ",st[i][j]);}puts("");}*/break;case &＃39;Q&＃39;:a&＃61;n-a&＃43;1;int k&＃61;log2(n-a&＃43;1);lastans&＃61;max(st[n][k],st[a&＃43;(1<1][k]);printf("%d\n",lastans);break;}}return 0;
}