【解题思路】

　　强制在线/，没什么好说的。。复杂度O(mlog₂m)（线段树）或O(mlog₂²m)（树状数组）。

【参考代码】

（还naive的时候写的zkw真是翔。。）

1 #include
      
        2 #include
       
         3 #include
        
          4 #define REP(I,start,end) for(int I=start;I<=end;I++) 5 #define FNI -2147483647-1 6 using namespace std; 7 struct zkw_LineTree 8 { 9     int startPoint,savTree[600001];10     inline void Clear(int n)11     {12         startPoint=1;13         while(startPoint
         
          >=1;25         }26     }27     inline int Query(int left,int right)28     {29         int l=startPoint+left-1,r=startPoint+right-1,result=FNI;30         bool onRight=false,onLeft=false;31         while(l+1
          
           >=1;45             if(r&1)46             {47                 if(onLeft)48                     result=max(result,savTree[r-1]);49             }50             else51                 if(!onLeft)52                 {53                     onLeft=true;54                     result=max(result,savTree[r]);55                 }56             r>>=1;57         }58         if(!onRight)59             result=max(result,savTree[l]);60         if(!onLeft)61             result=max(result,savTree[r]);62         return result;63     }64 }LineTree;65 int n,Claris;66 int main()67 {68     scanf("%d%d",&n,&Claris);69     int len=0,ans=0;70     LineTree.Clear(n);71     while(n--)72     {73         char ch=getchar();74         while(ch!='A'&&ch!='Q')75             ch=getchar();76         int t;77         scanf("%d",&t);78         if(ch=='A')79             LineTree.Change(++len,(ans+t)%Claris);80         else81         {82             ans=LineTree.Query(len-t+1,len);83             printf("%d\n",ans);84         }85     }86     return 0;87 }