P1198 最大数

　　这是其实一道很简单的题（感觉是绿题），并不用线段树，ST表就可以。

　　但是和普通的ST表有差别，就是这个是逆向的ST表（其实也没啥差别）……

　　注意：

　　　　是1<<i，是1<<i，是1<<i ——> 重要的事说三遍！！！

　　悲伤……滴了好久……

　　代码：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int dp[200005][21],b[200005],m,tail,last,d;
void add_to(int p)
{
    dp[++tail][0]=p;
    for(int i=1;tail-(1<<i)+1>0;i++)
        dp[tail][i]=max(dp[tail][i-1],dp[tail-(1<<(i-1))][i-1]);
    b[tail]=log2(tail);
}
int query(int l)
{
    int k=b[tail-l+1];
    return max(dp[tail][k],dp[l-1+(1<<k)][k]);
} 
int main()
{
    scanf("%d%d",&m,&d);
    char s;
    for(int i=1;i<=m;i++)
    {
        int p;
        cin>>s;
        scanf("%d",&p);
        if(s=='A')
        {
            p=(p+last)%d;
            add_to(p);
        } 
        else
        {
            int ans=query(tail-p+1);
            last=ans;
            printf("%d
",ans);
        }
    }
    return 0;
}