题目描述
现在请求你维护一个数列，要求提供以下两种操作：
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 100A 96Q 1A 97Q 1Q 2
输出样例#1： 复制
969396
说明
[JSOI2008]
本题数据已加强
数据果然加强了，还得我爆int了……
我们知道m的上界其实就是线段树的叶子节点上界，首先建树，然后注意特判就行了……
AC代码如下：
#include<cstdio>#include<algorithm>#include<iostream>#define ll long longusing namespace std;const int N=200000;const ll INF=-2147283647;ll mx[N<<2+5],x,m,t,d,len;char a;void init(ll now,ll l,ll r){ ???if(l==r) {mx[now]=INF;return;} ???ll mid=(l+r)>>1; ???init(now<<1,l,mid); ???init(now<<1|1,mid+1,r); ???return; } void update(ll now,ll l,ll r,ll pos,ll date){ ???if(l==r) { ???????mx[now]=date;return; ???} ???ll mid=(l+r)>>1; ???if(pos<=mid) update(now<<1,l,mid,pos,date); ???else update(now<<1|1,mid+1,r,pos,date); ???mx[now]=max(mx[now<<1],mx[now<<1|1]); ???return;}ll q(ll now,ll l,ll r,ll ql,ll qr){ ???if(ql<=l&&r<=qr) return mx[now]; ???ll mid=(l+r)>>1; ???ll res=INF; ???if(ql<=mid) res=q(now<<1,l,mid,ql,qr); ???if(qr>mid) res=max(res,q(now<<1|1,mid+1,r,ql,qr)); ???return res;} int main(){ ???scanf("%lld%lld",&m,&d); ???init(1,1,N); ???for(ll i=1;i<=m;i++) ???{ ???????cin>>a;scanf("%lld",&x); ???????if(a==‘A‘) len++,update(1,1,N,len,(x+t)%d); ???????else { ????????????????if(x==0) t=0; ???????????????else ?t=q(1,1,N,len-x+1,len); ???????????????printf("%lld\n",t); ???????} ?????????????????} ???return 0;}P1198 [JSOI2008]最大数
原文地址：https://www.cnblogs.com/Alex-leaves/p/8452505.html