JAG2018 Day2 D - Knapsack And Queries

問題ページ

ナップサック問題のように 重みが最大の価値 としたDPテーブルを更新することを考える．このDPテーブルに となるクッキーを追加する場合，chmax(dp[(i+w)%mod], dp[i]+v) となる．クッキーを追加する順番にかかわらずDPの結果は同じであり，この操作は結合的である．

ADD操作ならば最後の要素として追加，REMOVE操作ならば最初の要素を削除したい．この操作はSWAgを用いることで達成できる．

FIND操作では前半のstackのDP配列 と後半のstackのDP配列 をマージする必要がある． となるので， を固定したときの の区間maxが求められればよい．これはSWAgで達成でき，マージが となる．

制約が本質

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
class Crypto {  
public:      
    Crypto() {  
        sm = cnt = 0;  
        seed();  
    }  
  
    int decode(int z) {  
        z ^= next();  
        z ^= (next() << 8);  
        z ^= (next() << 16);  
        z ^= (next() << 22);  
        return z;  
    }  
  
    void query(long long z) {  
        const long long B = 425481007;  
        const long long MD = 1000000007;  
        cnt++;  
        sm = ((sm * B % MD + z) % MD + MD) % MD;  
        seed();  
    }  
private:   
    long long sm;  
    int cnt;  
  
    uint8_t data[256];  
    int I, J;  
  
    void swap_data(int i, int j) {  
        uint8_t tmp = data[i];  
        data[i] = data[j];  
        data[j] = tmp;      
    }  
  
    void seed() {  
        uint8_t key[8];  
        for (int i = 0; i < 4; i++) {  
            key[i] = (sm >> (i * 8));  
        }  
        for (int i = 0; i < 4; i++) {  
            key[i+4] = (cnt >> (i * 8));  
        }  
  
        for (int i = 0; i < 256; i++) {  
            data[i] = i;  
        }  
        I = J = 0;  
  
        int j = 0;  
        for (int i = 0; i < 256; i++) {  
            j = (j + data[i] + key[i%8]) % 256;  
            swap_data(i, j);  
        }  
    }  
  
    uint8_t next() {  
        I = (I+1) % 256;  
        J = (J + data[I]) % 256;  
        swap_data(I, J);  
        return data[(data[I] + data[J]) % 256];  
    }  
};  
  
template<class T, class S, class F>  
struct SWAG {  
    // using F = function<S(S,T)>;  
    F f; S id;  
    stack<T> lt, rt;  
    stack<S> ls, rs;  
    SWAG(F f, S d) : f(f), id(d) {  
        ls.push(id);  
        rs.push(id);  
    }  
    void push_back(T x) {   
        rt.push(x);  
        rs.push(f(rs.top(), x));  
    }  
    void pop_front() {  
        if(lt.empty()) {  
            while(rt.size()) {  
                T x = rt.top(); rt.pop(); rs.pop();  
                lt.push(x);  
                ls.push(f(ls.top(), x));  
            }  
        }  
        lt.pop();  
        ls.pop();  
    }  
    template<class Q>  
    void fold(Q q) { q(ls.top(), rs.top()); }  
};  
  
int main(void) {  
    int mod, q;  
    cin >> mod >> q;  
    Crypto c;  
  
    using S = array<ll, 512>;  
    auto f = [&](S a, PII b) {  
        S ret(a);  
        REP(i, mod) chmax(ret[(i+b.first)%mod], a[i]+b.second);  
        return ret;  
    };  
    S id;  
    id[0] = 0;  
    FOR(i, 1, 512) id[i] = -INF;  
    SWAG<PII, S, decltype(f)> swag(f, id);  
  
    REP(i, q) {  
        int t, w, v, l, r;  
        cin >> t >> w >> v >> l >> r;  
        t = c.decode(t);  
        w = c.decode(w) % mod;  
        v = c.decode(v);  
        l = c.decode(l);  
        r = c.decode(r) + 1;  
  
        if(t == 1) swag.push_back(PII(w, v));  
        else swag.pop_front();  
  
        auto query = [&](S a, S b) {  
            auto f2 = [](ll x1, ll x2){ return max(x1, x2); };  
            SWAG<ll, ll, decltype(f2)> rmq(f2, -INF);  
            FOR(i, l, r) rmq.push_back(a[i]);  
            ll ans = -1;  
            for(ll i=mod; i>0; --i) {  
                // b[i] と a[j] をマージする l<=(i+j)%mod<r  
                // b[i] を固定したときの max(a[j]) をSWAgで持っておくとマージが高速  
                auto g = [&](ll y1, ll y2){ chmax(ans, max(y1,y2)+b[i%mod]); };  
                rmq.fold(g);  
                rmq.push_back(a[(r+mod-i)%mod]);  
                rmq.pop_front();  
            }  
            c.query(ans);  
            cout << ans << "\n";  
        };  
        swag.fold(query);  
    }  
    cout << flush;  
  
    return 0;  
}