bzoj1012: [JSOI2008]最大数maxnumber(貌似是道线段树喔)

1012: [JSOI2008]最大数maxnumber

题目：传送门

题解：

　　 发现自己空了一道水题...

　　 1~210000建线段树,其实就是一道裸题...

　　 单点修改+区间查询...1A~

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define qread(x)x=read();

 using namespace std;

 inline int read()

 {

     int f=,x=;char ch;

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return f*x;

 }

 struct node

 {

     int l,r,lc,rc,c;

 }tr[];int len;

 void bt(int l,int r)

 {

     len++;int now=len;

     tr[now].l=l;tr[now].r=r;tr[now].c=;

     tr[now].lc=tr[now].rc=-;

     if(l<r)

     {

         int mid=(l+r)/;

         tr[now].lc=len+;bt(l,mid);

         tr[now].rc=len+;bt(mid+,r);

     }

 }

 void change(int now,int x,int k)

 {

     if(tr[now].l==tr[now].r){tr[now].c=k;return ;}

     int lc=tr[now].lc,rc=tr[now].rc;

     int mid=(tr[now].l+tr[now].r)/;

     if(x<=mid)change(lc,x,k);

     else if(mid+<=x) change(rc,x,k);

     tr[now].c=max(tr[lc].c,tr[rc].c);

 }

 int findmax(int now,int l,int r)

 {

     if(l==tr[now].l && tr[now].r==r)return tr[now].c;

     int lc=tr[now].lc,rc=tr[now].rc;

     int mid=(tr[now].l+tr[now].r)/;

     if(r<=mid)return findmax(lc,l,r);

     else if(mid+<=l)return findmax(rc,l,r);

     else return max(findmax(lc,l,mid),findmax(rc,mid+,r));

 }

 int main()

 {

     int M,D,t=,ans,num;

     qread(M);qread(D);

     char c[];len=;

     bt(,);num=;

     for(int i=;i<=M;i++)

     {

         int x;

         scanf("%s",c);qread(x);

         if(c[]=='A')

             change(,++num,(x+t)%D);

         else

         {

             t=findmax(,num-x+,num);

             printf("%d\n",t);

         }

     }

     return ;

 }