这同样也是从学长那里偷来的，姑且叫它扩展单调队列吧。

它支持维护一个数据结构，可以从末尾加删元素和开头加删元素（双端队列），同时维护其中所有元素的一个运算和（该运算得是满足结合律的运算，如果为 \(\max\) 就是我们平时看到的单调队列）。

具体的想法就是选择一个关键点，在关键点前的维护后缀和，在关键点后的维护前缀和，那么对于不使得关键点弹出的操作，我们都可以 \(O(1)\) 快速回答，但是如果弹出了关键点，我们就需要重构，我们考虑每次重构的时候将关键点放在当前段的中间，然后可以发现至少需要 \(O(n)\) 次操作，才会更新新的关键点，然后我们更新一次关键点的复杂度是 \(O(n)\) 的，所以均摊下来就是 \(O(1)\) 的。

牛啊。

D - Knapsack And Queries

应该是一道上面的算法的板子题。我们考虑做法就是暴力维护卷积运算的答案。

每次加一个的时候就是背包，但是考虑两个合并的时候如果暴力背包是错误的，这里考虑利用询问是一段区间的特性，我们对一边搞背包的时候，另一边考虑区间查询最值即可。

#include
using namespace std;
const int MOD=500,Q=1e5+5;
const long long INF=1e18;
int n,mod;
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];
    }
}c;
struct Object{int w,v;};
struct Bag{
    long long f[MOD];
    Bag(){f[0]=0;for(int i=1;i q;vector L,R;
    void init(){
        L.push_back(Bag()),R.push_back(Bag());
    }
    void rebuild(){
        L.clear(),R.clear();
        L.push_back(Bag()),R.push_back(Bag());
        int key=(int)q.size()/2;
        for(int i=key;i<(int)q.size();++i) R.push_back(R.back()*q[i]);
        for(int i=key-1;i>=0;--i) L.push_back(L.back()*q[i]);
    }
    void push_back(Object a){
        q.push_back(a),R.push_back(R.back()*a);
    }
    void pop_front(){
        q.pop_front(),L.pop_back();
        if(L.empty()||R.empty()) rebuild();
    }
    long long query(int l,int r){
        deque Q;long long res=-INF;
        for(int i=l;i<=r;++i){
            while(!Q.empty()&&R.back()[Q.back()]r-l) Q.pop_front();
            while(!Q.empty()&&R.back()[Q.back()%mod]>mod>>n,q.init();
	for(int i=1;i<=n;++i){
		int t,w,v,l,r;scanf("%d%d%d%d%d",&t,&w,&v,&l,&r);
		t=c.decode(t),w=c.decode(w),v=c.decode(v),l=c.decode(l),r=c.decode(r);
        // printf("%d %d %d %d %d\n",t,w,v,l,r);
        if(t==1) q.push_back((Object){w,v});else q.pop_front();
        long long res=q.query(l,r);res=res<0?-1:res;
        c.query(res),printf("%lld\n",res);
	}
    return 0;
}
/*
7
20
281614559 249378726 433981094 466775639 683612870
59536386 999828879 241246766 434670565 174365647
172060134 848462699 857413429 182122460 807914643
808426426 600772095 829463884 974102196 354283529
370037909 1024921880 664216868 194331103 140834169
917331875 242953442 205247688 335469789 1055568137
823475244 641321246 617915164 160300810 1073617378
892669150 939175632 904628449 606339993 1059849410
829170894 436718235 288920513 228195002 55212938
*/