【BZOJ1012】最大数

  裸的ST。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200010;
 
void readchar(char &ch) {while ((ch=getchar())==' ' || ch=='\n');}
 
int f[maxn][20];
int n,m,d,t;
 
void Insert(int x)
{
    f[n][0]=x%d;
    int k=0,k2=1;
    while (n-k2>0) f[n][k+1]=max(f[n][k],f[n-k2][k]),k++,k2<<=1;
}
 
int Query(int x)
{
    int res=0,p=n,k=0,k2=1;
    while (x-k2>=0) k++,k2<<=1;k--,k2>>=1;
    while (x)
    {
        while (x-k2<0) k--,k2>>=1;
        res=max(res,f[p][k]);
        p-=k2;x-=k2;
    }
    return res%d;
}
 
int main()
{
    scanf("%d%d",&m,&d);
    while (m--)
    {
        char ctr;int x;
        readchar(ctr);
        scanf("%d",&x);
        if (ctr=='A') n++,Insert(x+t);
        else printf("%d\n",t=Query(x));
    }
}