1 //{HEADS  2 #define FILE_IN_OUT  3 #define debug  4 #include <cstdio>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cmath>  8 #include <ctime>  9 #include <algorithm> 10 #include <iostream> 11 #include <fstream> 12 #include <vector> 13 #include <stack> 14 #include <queue> 15 #include <deque> 16 #include <map> 17 #include <set> 18 #include <bitset> 19 #include <complex> 20 #include <string> 21 #define REP(i, j) for (int i = 1; i <= j; ++i) 22 #define REPI(i, j, k) for (int i = j; i <= k; ++i) 23 #define REPD(i, j) for (int i = j; 0 < i; --i) 24 #define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i) 25 #define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i) 26 #define CLR(s) memset(s, 0, sizeof s) 27 #define SET(s, v) memset(s, v, sizeof s) 28 #define mp make_pair 29 #define pb push_back 30 #define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl 31 #define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endl 32 using namespace std; 33 #ifdef debug 34 #ifndef ONLINE_JUDGE 35     const int OUT_PUT_DEBUG_INFO = 1; 36 #endif 37 #endif 38 #ifdef ONLINE_JUDGE 39     const int OUT_PUT_DEBUG_INFO = 0; 40 #endif 41 #define DG if(OUT_PUT_DEBUG_INFO) 42 void FILE_INIT(string FILE_NAME) { 43 #ifdef FILE_IN_OUT 44 #ifndef ONLINE_JUDGE  45     freopen((FILE_NAME + ".in").c_str(), "r", stdin); 46     freopen((FILE_NAME + ".out").c_str(), "w", stdout); 47  48 #endif 49 #endif 50 } 51 typedef long long LL; 52 typedef double DB; 53 typedef pair<int, int> i_pair; 54 const int INF = 0x3f3f3f3f; 55 //} 56  57 const int maxn = 200000 + 10; 58  59 int m, d; 60  61 struct Things { 62     int pos, val; 63     Things() {} 64     Things(int pos, int val):pos(pos), val(val) {} 65     void print() { 66         printf("%d %d\n", pos, val); 67     } 68 }S[maxn]; 69 int tail = 0; 70 /*{ 获取字符*/ 71 char gchar() { 72     char ret = getchar(); 73     for(; ret == ‘\n‘ || ret == ‘\r‘ || ret == ‘ ‘; ret = getchar()); 74     return ret; 75 } 76 /*}*/ 77  78 int main() { 79     FILE_INIT("BZOJ1012"); 80  81     scanf("%d%d", &m, &d); 82     char ope; 83     int t, rec = 0, cnt = 0; 84     REP(i, m) { 85         ope = gchar(); 86         scanf("%d", &t); 87         if(ope == ‘A‘) { 88             S[++tail] = Things(++cnt, (rec + t) % d); 89             DG S[tail].print(); 90             for(; 1 < tail && S[tail - 1].val <= S[tail].val; S[tail - 1] = S[tail], --tail); 91             DG S[tail].print(); 92         } else { 93             int l = 1, r = tail; 94             DG printf("l = %d r = %d\n", l, r); 95             while(l < r) { 96                 int mid = (l + r) >> 1; 97                 if(cnt - S[mid].pos + 1 <= t) { 98                     r = mid; 99                 } else {100                     l = mid + 1;101                 }102             }103             rec = S[l].val;104             printf("%d\n", rec);105         }106     }107 108     return 0;109 }