描述
给定一个正整数数列 a1,a2,a3,⋯,an ，每一个数都在 0～p–1 之间。可以对这列数进行两种操作：
添加操作：向序列后添加一个数，序列长度变成 n+1；
询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。
输入
第一行有两个正整数 m,p，意义如题目描述；
接下来 m 行，每一行表示一个操作。如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a)modp。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。
第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。
对于全部数据，1≤m≤2×105,1≤p≤2×109,0≤t<p。
输出
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。
样例输入
10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99
样例输出
97
97
97
60
60
97
提示
最后的序列是 97,14,60,96。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f; ll tree[N],b[N]; ll n,m,p,num,ans; char c[N]; void modify(int k,int l,int r,int x,ll c) { if(l==r && l==x) { tree[k] += c;return; //单点加 } int mid = (l + r) / 2; if(x <= mid) modify(k * 2,l,mid,x,c); else modify(k * 2 + 1,mid + 1,r,x,c); tree[k] = max(tree[k * 2],tree[k * 2 + 1]); //更新区间k最大值 } ll query(int k,int l,int r,int x,int y) { if(l >= x && r <= y)return tree[k]; //返回x,y区间记录的最大值 if(l > y || r < x)return 0; //能跳过前面两个return，说明当前的l,r和x,y有重叠子区间，但不是交集 int mid = (l + r) / 2; ll res = 0; if(x <= mid) res = max(res,query(k * 2,l,mid,x,y)); // l,mid和x,y有从x到mid的交集 if(y > mid) res = max(res,query(k * 2 + 1,mid + 1,r,x,y)); // mid + 1，r和x,y有mid + 1 到 y的交集 return res; } int main() { cin >> m >> p; for(int i = 1;i <= m;i++) { c[i] = getchar(); while(c[i]!='A' && c[i]!='Q')c[i] = getchar(); scanf("%lld",&b[i]); if(c[i]=='A')num++; } for(int i = 1;i <= m;i++) { if(c[i] == 'A') { n++; ll k = (ans + b[i]) % p; modify(1,1,num,n,k); } else { ans = query(1,1,num,n - b[i] + 1,n); //最后b[i]个元素的最大值，所以是从[n-b[i]+1,n]的区间 printf("%lld\n",ans); } } return 0; }