题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1012
题意:维护一个数列，开始时没有数值，之后会有两种操作，
Q L :查询数列末k位的最大值；
A n:上一次查询的结果加上n添加到数列的末尾；第一次添加时，认为t = 0;
Sample Input
5 100
A 96
Q 1
A 97
Q 1
Q 2
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
96
93
96
思路:保留输入的原值和用树状数组处理过的mx[i];其中mx[i]所管辖的范围就是lowbit(i)的值，即(i - lowbit(i),i];这样在之后查找时，每次先和原值比较，之后和比较比较的区间就是lowbit(i),但里面要两重循环来模拟整个比较的个数。如区间长度为10，比较的长度为 1,1,2,4,1,1.
#include<bits/stdc++.h>
using namespace std;
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define ok puts(" ok")
#define bug puts(" bug ")
#define INF 0x3f3f3f3f
#define esp 1e-8 typedef long long ll;
const int maxx=;
ll num[maxx],len=,mx[maxx];
int lowbit(int i){return i&(-i);}
void modify(int pos)//更改1~pos的max
{
mx[pos]=num[pos];
for(int j=;j<lowbit(pos);j<<=)
{
mx[pos]=max(mx[pos],mx[pos-j]);
}
}
int query(int l,int r)
{
ll ans=-INF;
//lowbit()会出现1 2 4,这里面出现的间隔，就需要要两层循环里避免中间值；
//并且lowbit的值代表的就是该值代表的数的个数；
while(l<=r)
{
ans=max(ans,num[r]);
for(--r;l+lowbit(r)<=r;r-=lowbit(r))
ans=max(ans,mx[r]);
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
ll m,mod;
scanf("%lld%lld",&m,&mod);
ll t=,x;char op[];
for(int i=;i<=m;i++)
{
scanf("%s%lld",op,&x);
if(op[]=='A')
{
num[++len]=(t+x)%mod;
modify(len);
}
else{
t=query(len-x+,len);
printf("%lld\n",t);
}
}
return ;
}