此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=1198
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
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：
5 100A 96Q 1A 97Q 1Q 2
输出样例#1：
969396
说明
[JSOI2008]
分析：
与裸的线段树相比，上了难度的一点是不知道线段树的具体大小，而且还要不断地插入新的节点。
对build函数做一点改动，其他的就是线段树模板了。
首先把r的值假定为可能的最大值，然后增加一个新的参数xx，表示当前插入的节点应在的位置。
而且在递归地build左右两边的时候，也要注意判断一下mid与xx的关系，否则后来的build就会把前面的值覆盖掉...
AC代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 ?7 const int MAXN = 200005; 8 ?9 inline void read(long long &x)10 {11 ????char ch = getchar(),c = ch;x = 0;12 ????while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar();13 ????while(ch >= ‘0‘ && ch <= ‘9‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar();14 ????if(c == ‘-‘) x = -x;15 }16 17 int t,n;18 long long MOD,m,x,sdata[MAXN<<1];19 char op;20 21 inline int max(int a,int b)22 {return a>b?a:b;}23 24 inline void update(int o)25 {26 ????sdata[o] = max(sdata[o<<1],sdata[o<<1|1]);27 }28 29 void build(int l,int r,int o,int xx)30 {31 ????if(l == r)32 ????{33 ????????sdata[o] = x;34 ????????return;35 ????}36 ????int mid = (l+r)>>1;37 ????if(xx <= mid) build(l,mid,o<<1,xx);38 ????else ?build(mid+1,r,o<<1|1,xx);39 ????update(o);40 }41 42 int ask(int l,int r,int o,int ll,int rr)43 {44 ????if(ll <= l && rr >= r)45 ????????return sdata[o];46 ????int mid = (l+r)>>1;47 ????int ans = 0;48 ????if(ll <= mid) ans = max(ans,ask(l,mid,o<<1,ll,rr));49 ????if(rr > mid) ans = max(ans,ask(mid+1,r,o<<1|1,ll,rr));50 ????return ans;51 }52 53 int main()54 {55 ????read(m),read(MOD);56 ????for(int i = 1;i <= m;++ i)57 ????{58 ????????op = getchar();59 ????????while(op < ‘A‘) op = getchar();60 ????????read(x);61 ????????if(op == ‘A‘)62 ????????{63 ????????????++ n;64 ????????????x = (x+t)%MOD;65 ????????????build(1,MAXN,1,n);66 ????????}67 ????????else68 ????????{69 ????????????if(n > 0)70 ????????????????t = ask(1,MAXN,1,n-x+1,n);71 ????????????printf("%d\n",t);72 ????????}73 ????}74 ????return 0;75 }洛谷 P1198 [JSOI2008]最大数 题解
原文地址：http://www.cnblogs.com/shingen/p/7526146.html