LOJ6515 「雅礼集训 2018 Day10」贪玩蓝月

Link
考虑用两个栈模拟双端队列，每次加进来一个元素就处理出新的背包数组。
查询的话不妨固定左边的栈的特征值，那么右边的栈可以取到的特征值是一个区间，单调队列维护即可（我写的ST表）。
删除的话直接把元素弹出栈就行了，不用管背包数组（当然memset一下也没有问题）。
可能会出现把一个栈删空了的情况，此时把另一个栈的一半放到这个栈里面来，暴力重构即可。
不难证明复杂度是均摊(O(np))的。

#include<cctype>
#include<cstdio>
#include<cstring>
#include<utility>
#include<algorithm>
using i64=long long;
using pi=std::pair<i64,i64>;
const int N=50007,M=507;const i64 inf=0x3f3f3f3f3f3f3f3f;
int p,top[2],lg[M];i64 f[2][N][M];pi stk[2][N];
int read(){int x;scanf("%d",&x);return x;}
void insert(int o,int n,pi x)
{
    stk[o][n]=x,memcpy(f[o][n],f[o][n-1],8*p);
    for(int k=0;k<p;++k) f[o][n][(k+x.first)%p]=std::max(f[o][n][(k+x.first)%p],f[o][n-1][k]+x.second);
}
void del(int o)
{
    if(top[o]) return --top[o],void();
    int mid=(top[!o]+1)/2;
    for(int i=1;i<=mid;++i) stk[o][mid-i+1]=stk[!o][i],stk[!o][i]=stk[!o][i+mid];
    top[o]=mid-1,top[!o]=mid-(top[!o]&1);
    for(int i=1;i<=top[o];++i) insert(o,i,stk[o][i]);
    for(int i=1;i<=top[!o];++i) insert(!o,i,stk[!o][i]);
}
i64 query(int l,int r)
{
    static i64 st[10][M];static auto ask=[](int l,int r){int k=lg[r-l+1];return std::max(st[k][l],st[k][r-(1<<k)+1]);};
    i64 ans=-inf;memcpy(st[0],f[0][top[0]],8*p);
    for(int j=1,k;k=1<<j,j<=lg[p];++j) for(int i=0;i+k<=p;++i) st[j][i]=std::max(st[j-1][i],st[j-1][i+k/2]);
    for(int i=0,L,R;i<p;++i) if(f[1][top[1]][i]>=0) L=(l-i+p)%p,R=(r-i+p)%p,ans=std::max(ans,f[1][top[1]][i]+(L<=R? ask(L,R):std::max(ask(0,R),ask(L,p-1))));
    return ans<0? -1:ans;
}
int main()
{
    read();int t=read(),x,y,o;p=read(),memset(f,-0x3f,sizeof f),f[0][0][0]=f[1][0][0]=0;
    for(int i=2;i<=p;++i) lg[i]=lg[i/2]+1;
    for(char str[5];t;--t)
    {
	scanf("%s",str),o=str[1]=='G';
	if(str[0]=='I') x=read(),y=read(),insert(o,++top[o],pi(x%p,y));
	if(str[0]=='D') del(o);
	if(str[0]=='Q') x=read(),y=read(),printf("%lld
",query(x,y));
    }
}