题目链接
题意分析
我们考虑维护两个栈
分别支持左边的插入删除以及右边的插入删除
然后对于两两个栈的我们需要用背包求出最优答案
注意 删除时如果不够的话 我们需要从另一个栈中取出一半加入另一个栈中 注意保持顺序
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 568
#define IL inline
#define M 56010
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int T,n,p;
int lg[M],top[2];
ll dp[2][M][N],ST[M][20];
pair<int,int> sta[2][M];
char s[10];
IL void init()
{
memset(dp,-0x3f,sizeof dp);
dp[0][0][0]=dp[1][0][0]=0;
for(R int i=1;(1<<i)<=50000;i++) lg[1<<i]=i;
for(R int i=1;i<=50000;++i) if(!lg[i]) lg[i]=lg[i-1];
// for(R int i=1;i<=20;++i) printf("%d%c",lg[i],(i==20 ? '\n':' '));
}
IL void insert(int knd,int now,pair<int,int> at)
{
sta[knd][now]=at;
for(R int i=0;i<p;++i) dp[knd][now][i]=dp[knd][now-1][i];
for(R int i=0;i<p;++i)
dp[knd][now][(i+at.first)%p]=max(dp[knd][now][(i+at.first)%p],dp[knd][now-1][i]+at.second)
}//我们是用背包维护两个栈的最优答案
IL void del(int knd)
{
if(top[knd]) {--top[knd];return;}
int mid=(top[knd^1]+1)>>1;
for(R int i=1;i<=mid;++i) sta[knd][mid-i+1]=sta[knd^1][i],sta[knd^1][i]=sta[knd^1][i+mid];
top[knd]=mid-1;top[knd^1]=(top[knd^1]&1 ? mid-1:mid);
for(R int i=1;i<=top[knd];++i) insert(knd,i,sta[knd][i]);
for(R int i=1;i<=top[knd^1];++i) insert(knd^1,i,sta[knd^1][i]);
//存在一个栈直接删空的情况的话
//我们从另一个栈中取走一半 加入这个栈
//从而保证复杂度
//并且还是需要再次背包的
}
IL ll getmax(int le,int ri)
{
int lx=lg[ri-le+1];
return max(ST[le][lx],ST[ri-(1<<lx)+1][lx]);
}
IL ll qury(int le,int ri)
{
ll res=-inf;
for(R int i=0;i<p;++i) ST[i][0]=dp[0][top[0]][i];
for(R int j=1;(1<<j)<=p;++j)
for(R int i=0;i+(1<<j)<=p;++i)
ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
for(R int i=0;i<p;++i)
{
if(dp[1][top[1]][i]<0) continue;
int lx=(le-i+p)%p,rx=(ri-i+p)%p;
if(lx<=rx) res=max(res,dp[1][top[1]][i]+getmax(lx,rx));
else res=max(res,dp[1][top[1]][i]+max(getmax(0,rx),getmax(lx,p-1)));
}
//我们枚举一个栈的体积
//另一个栈的话 我们直接区间求最值就可以了
// printf("now %lld\n",res);
if(res==-inf) return -1;
else return res;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(T);read(n);read(p);init();
while(n--)
{
scanf("%s",s);
if(s[0]=='I')
{
int x,y;read(x);read(y);
insert(s[1]=='G',++top[s[1]=='G'],make_pair(x%p,y));
}
else if(s[0]=='D')
{
del(s[1]=='G');
}
else if(s[0]=='Q')
{
int le,ri;read(le);read(ri);
printf("%lld\n",qury(le,ri));
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}