1 #include <cstdio> 2 #include <iostream> 3  4 using namespace std; 5  6 int m, n, pos, ql, qr; 7 long long c[2000001], x, d, t; 8 char s; 9 10 void build(int o, int l, int r)11 {12     c[o] = -2147283647;13     if(l == r) return;14     int mid = (l + r) / 2;15     build(o * 2, l, mid);16     build(o * 2 + 1, mid + 1, r);17 }18 19 void update(int o, int l, int r)20 {21     if(l == r)22     {23         c[o] = x;24         return;25     }26     int mid = (l + r) / 2;27     if(pos <= mid) update(o * 2, l, mid);28     else update(o * 2 + 1, mid + 1, r);29     c[o] = max(c[o * 2], c[o * 2 + 1]);30 }31 32 int query(int o, int l, int r)33 {34     if(ql <= l && r <= qr) return c[o];35     int mid = (l + r) / 2, ans = -2147283647;36     if(ql <= mid) ans = max(ans, query(o * 2, l, mid));37     if(qr > mid) ans = max(ans, query(o * 2 + 1, mid + 1, r));38     return ans;39 }40 41 int main()42 {43     int i, j;44     scanf("%d%d", &m, &d);45     build(1, 1, m);46     for(i = 1; i <= m; i++)47     {48         scanf("%s%d", &s, &x);49         if(s == ‘A‘)50         {51             x = (x + t) % d;52             pos++;53             update(1, 1, m);54         }55         else56         {57             ql = pos - x + 1;58             qr = pos;59             t = query(1, 1, m);60             printf("%d\n", t);61         }62     }63     return 0;64 }

 1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib>10 # include <algorithm>11 # define MAXN 20000112 using namespace std;13 14 int m, d, t, len;15 int top, s[MAXN], a[MAXN];16 17 int main()18 {19     int i, j, x, y;20     char c[1];21     scanf("%d %d", &m, &d);22     while(m--)23     {24         scanf("%s %d", c, &x);25         if(c[0] == ‘A‘)26         {27             x = (x + t) % d;28             a[++len] = x;29             while(top && a[s[top]] <= x) top--;30             s[++top] = len;31         }32         else33         {34             y = lower_bound(s + 1, s + top + 1, len - x + 1) - s;35             printf("%d\n", t = a[s[y]]);36         }37     }38     return 0;39 }