线段树做法

import java.io.*;

public class Main{

    static Node tr[];

    public static void main(String[]args) throws Exception{

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        String s[]=br.readLine().split(" ");

        int m=Integer.parseInt(s[0]),p=Integer.parseInt(s[1]);

        tr=new Node[m*4];

        int last=0,x=0,n=1;

        build_tree(1,1,m);

        while(m--!=0){

            s=br.readLine().split(" ");

            x = Integer.valueOf(s[1]);

            if("Q".equals(s[0])){

                last = query(1, n - x + 1, n);

                bw.write(last + "\n");

            }else{

                modify(1, n + 1, (last + x) % p);  //注意，这里根节点是1， 修改的数是从n + 1开始。

                n++;

            }

             bw.flush();

        }

    }

    static void build_tree(int u,int l,int r){

        tr[u]=new Node(l,r);

        if(l==r) return;

        int mid=l+r>>1;

        build_tree(u<<1,l,mid);

        build_tree(u<<1|1,mid+1,r);

    }

    static void modify(int u,int x,int c){

        if(tr[u].l==x&&tr[u].r==x){

            tr[u].v=c;

        }else{

            int mid=tr[u].l+tr[u].r>>1;

            if(x<=mid) modify(u<<1,x,c);

            else modify(u<<1|1,x,c);

            pushUp(u);

        }

    }

    static void pushUp(int u){

        tr[u].v=Math.max(tr[u<<1].v,tr[u<<1|1].v);

    }

    static int query(int u,int l,int r){

        if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;

        int mid=tr[u].l+tr[u].r>>1;

        int v=0;

        if(l<=mid) v=query(u<<1,l,r);

        if(r>mid) v=Math.max(v,query(u<<1|1,l,r));

        return v;

    }

}

class Node{

    int l,r,v;

    Node(int l,int r){

        this.l=l;

        this.r=r;

    }

}