题目描述
现在请求你维护一个数列，要求提供以下两种操作：
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
题解：
运用线段树的算法。
这道题看似长度是变化的，其实可以转化
直接将序列看做1~m的数列，将数一个一个加入，并记录当前位置就行了
首先建树，把所有的节点的值赋成min_int。用[i,j]表示该区间的最大值。
1）读入Q L操作。用len表示区间的大小，在len+1的位置放入（L+T)%D的值。
2）读入A n操作。输出区间[len-n+1,len]这个区间中的最大值，并把t的值进行更新。
此题还可以用二分和单调栈
1 #include2 #include 3 #include 4 using namespace std; 5 int M,D,t=0; 6 int size; 7 int a[200500]; 8 int num[200500]; 9 int main() 10 { 11 int Ln,len=0; 12 char QA[5]; 13 scanf("%d%d", &M, &D); 14 while(M--) 15 { 16 scanf("%s %d", QA, &Ln); 17 if(QA[0] == 'A')//查询操作 18 { 19 Ln=(Ln+t)%D; 20 num[++len]=Ln;//每次加入一个Ln,num数组长度++ 21 while(size&&num[a[size]]<=Ln) 22 size--;//单调栈操作 23 a[++size]=len; 24 } 25 else //插入操作 26 { 27 int pos=lower_bound(a+1,a+size+1,len-Ln+1)-a; //二分查找 28 t=num[a[pos]]; 29 cout< <
线段树
1 #include2 #include 3 #include 4 using namespace std; 5 int c[800001],ans; 6 void add(int rt,int l,int r,int p,int k) 7 { 8 if (l==r) 9 {10 c[rt]=k;11 return;12 }13 int mid=(l+r)>>1;14 if (p<=mid) add(rt<<1,l,mid,p,k);15 else add(rt<<1|1,mid+1,r,p,k);16 c[rt]=max(c[rt<<1],c[rt<<1|1]);17 }18 int query(int rt,int l,int r,int L,int R)19 {20 if (l>=L&&r<=R)21 {22 return c[rt];23 }24 int mid=(l+r)>>1,s=-2147283647;25 if (L<=mid) s=max(s,query(rt<<1,l,mid,L,R));26 if (R>mid) s=max(s,query(rt<<1|1,mid+1,r,L,R));27 return s;28 }29 void build(int rt,int l,int r)30 {31 c[rt]=-2147283647;32 if (l==r)return;33 int mid=(l+r)>>1;34 build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);35 }36 int main()37 { int n;38 char ch;39 int m,d,t,i,l;40 cin>>m>>d;41 t=0;42 int x=0;43 build(1,1,m);44 for (i=1;i<=m;i++)45 {46 cin>>ch;47 if (ch=='A')48 {49 scanf("%d",&n);50 n=(n+t)%d;51 x++;52 add(1,1,m,x,n);53 }54 else 55 {56 scanf("%d",&l);57 ans=query(1,1,m,x-l+1,x);58 t=ans;59 printf("%d\n",ans);60 }61 }62 }