[JSOI2008]最大数maxnumber

 1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack>10 #include<queue>11 using namespace std;12 #define enter printf("\n")13 #define space printf(" ")14 #define Mem(a) memset(a, 0, sizeof(a))15 typedef long long ll;16 typedef double db;17 const int INF = 0x3f3f3f3f;18 const int eps = 1e-8;19 const int maxn = 2e5 + 5;20 inline ll read()21 {22 ????ll ans = 0;23 ????char ch = getchar(), last = ‘ ‘;24 ????while(!isdigit(ch)) {last = ch; ch = getchar();}25 ????while(isdigit(ch))26 ????{27 ????????ans = ans * 10 + ch - ‘0‘; ch = getchar();28 ????}29 ????if(last == ‘-‘) ans = -ans;30 ????return ans;31 }32 inline void write(ll x)33 {34 ????if(x < 0) x = -x, putchar(‘-‘);35 ????if(x >= 10) write(x / 10);36 ????putchar(x % 10 + ‘0‘);37 }38 39 int m, cnt = 0;40 ll mod;41 ll t = 0;42 43 int l[maxn << 2], r[maxn << 2];44 ll Max[maxn << 2];45 void build(int L, int R, int now)46 {47 ????l[now] = L; r[now] = R;48 ????if(L == R) return;49 ????int mid = (L + R) >> 1;50 ????build(L, mid, now << 1);51 ????build(mid + 1, R, now << 1 | 1);52 }53 void update(int id, ll d, int now)54 {55 ????if(l[now] == r[now]) {Max[now] = d; return;}56 ????int mid = (l[now] + r[now]) >> 1;57 ????if(id <= mid) update(id, d, now << 1);58 ????else update(id, d, now << 1 | 1);59 ????Max[now] = max(Max[now << 1], Max[now << 1 | 1]);60 }61 ll query(int L, int R, int now)62 {63 ????if(l[now] == L && r[now] == R) return Max[now];64 ????int mid = (l[now] + r[now]) >> 1;65 ????if(R <= mid) return query(L, R, now << 1);66 ????else if(L > mid) return query(L, R, now << 1 | 1);67 ????else return max(query(L, mid, now << 1), query(mid + 1, R, now << 1 | 1));68 }69 70 int main()71 {72 ????m = read(); mod = read();73 ????build(1, m, 1);74 ????for(int i = 1; i <= m; ++i)75 ????{76 ????????char c; cin >> c;77 ????????if(c == ‘A‘)78 ????????{79 ????????????ll n = read(); 80 ????????????update(++cnt, (n + t) % mod, 1);81 ????????}82 ????????else83 ????????{84 ????????????int L = read();85 ????????????t = query(cnt - L + 1, cnt, 1);86 ????????????write(t); enter;87 ????????}88 ????}89 ????return 0;90 }