1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 200008 5 using namespace std; 6 int a[M],n,b[M],d,t,h,len; 7 char ch[10]; 8 int main() 9 {10     scanf("%d%d",&n,&d);11     for(int i=1;i<=n;i++)12       {13         int a1;14         scanf("%s%d",ch,&a1);15         if(ch[0]=='A')16           {17             len++;18             a1+=t;19             a1%=d;20             for(;h&&a[h]<=a1;h--);21             a[++h]=a1;22             b[h]=len;23           }24         else25           {26             int a2=lower_bound(b+1,b+h+1,len-a1+1)-b;27             t=a[a2];28             printf("%d\n",t);29           }30       }31     return 0;32 }
       
      
     

用单调队列，如果加入一个数，它前面比他小的就没有价值了，然后开一个数组存位置，找时找最早出现在范围内的队内的数。