洛谷-1198

洛谷-1198

思路

这个！

辅助解释

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
// #define int long long
int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;
ll m, last, dp[maxn][20];
int n;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    cin >> m >> mod;
    char x;
    int xx;
    for (int u = 0;u < m;u++) {
        cin >> x >> xx;
        if (x == 'A') {
            dp[++n][0] = (xx + last) % mod;
            for (int i = 1;n - (1 << i) >= 0;i++) 
                dp[n][i] = max(dp[n][i - 1], dp[n - (1 << (i - 1))][i - 1]);    // 解释1
        }
        else {
            int k = log2(xx);
            last = max(dp[n][k], dp[n - xx + (1 << k) ][k]);    // 解释2
            cout << last << "\n";
        }
    }
}