想到冗余就差不多了 单调队列

1 #include 
      
        2 const int N = 501000; 3 int q[N], loc[N], h, t, n, d, len; 4 inline void INSERT (int x) 5 { 6     while (h <= t && q[t] < x) t --; 7     q[++ t] = x;loc[t] = ++ len; 8 } 9 inline int QUERY (int x)10 {11     int st = 0, ed = t + 1, mid;12     while (st < ed - 1)13     {14         mid = st + ed >> 1;15         if (loc[mid] < x) st = mid;16         else ed = mid;17     }18     return q[st + 1];19 }20 int main ()21 {h = 1;22     scanf ("%d%d", &n, &d);char s[10];23     for (int i = 1, ans = 0, x; i <= n; i ++)24     {25         scanf ("%s%d", s, &x);26         if (s[0] == 'Q')27             printf ("%d\n", ans = QUERY (len - x + 1));28         if (s[0] == 'A')29             INSERT (((long long )x + ans) % d);30     }31     return 0;32 }