2020-2021:teams:legal_string:jxm2001:线段树分治
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/10/03 09:58] jxm2001 [习题四] |
2020-2021:teams:legal_string:jxm2001:线段树分治 [2020/10/03 11:38] (当前版本) jxm2001 [习题四] |
||
|---|---|---|---|
| 行 790: | 行 790: | ||
| dp[0][0]=0; | dp[0][0]=0; | ||
| solve(1,1); | solve(1,1); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | === 题解 2 === | ||
| + | |||
| + | 考虑建立两个栈维护队首修改操作和队尾修改操作。当加入元素时直接暴力背包转移，当删除元素时如果栈为空则均分重构栈。 | ||
| + | |||
| + | 根据势能分析法，易知重构的均摊时间复杂度为 $O(p)$。 | ||
| + | |||
| + | 对于查询操作，考虑先假定第一个栈提供特征值为 $0$，单调队列维护第二个栈 $[l,r]$ 范围最大值。 | ||
| + | |||
| + | 然后第一个栈遍历 $0\sim p-1$，同时单调队列维护第二个栈的区间最大值，单次询问时间复杂度 $O(p)$。 | ||
| + | |||
| + | 于是总时间复杂度 $O(pq)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e4+5,MAXP=505; | ||
| + | LL dp1[MAXN][MAXP],dp2[MAXN][MAXP]; | ||
| + | int p,lpos=MAXN+1,rpos=MAXN,mpos=MAXN,ltop,rtop; | ||
| + | pair<int,int> a[MAXN<<2]; | ||
| + | pair<int,LL> que[MAXN<<1]; | ||
| + | LL get_max(LL a,LL b,int v){ | ||
| + | if(a!=-1&&b!=-1) | ||
| + | return max(a,b+v); | ||
| + | else if(a!=-1) | ||
| + | return a; | ||
| + | else if(b!=-1) | ||
| + | return b+v; | ||
| + | else | ||
| + | return -1; | ||
| + | } | ||
| + | void cal(LL *dp1,LL *dp2,int w,int v){ | ||
| + | _for(i,0,p) | ||
| + | dp1[i]=get_max(dp2[i],dp2[(i+p-w)%p],v); | ||
| + | } | ||
| + | LL cal2(LL a,LL b){ | ||
| + | if(a!=-1&&b!=-1) | ||
| + | return a+b; | ||
| + | else | ||
| + | return -1; | ||
| + | } | ||
| + | void rebuild(){ | ||
| + | mpos=lpos+rpos>>1; | ||
| + | ltop=rtop=0; | ||
| + | for(int i=mpos;i>=lpos;i--){ | ||
| + | cal(dp1[ltop+1],dp1[ltop],a[i].first,a[i].second); | ||
| + | ltop++; | ||
| + | } | ||
| + | for(int i=mpos+1;i<=rpos;i++){ | ||
| + | cal(dp2[rtop+1],dp2[rtop],a[i].first,a[i].second); | ||
| + | rtop++; | ||
| + | } | ||
| + | } | ||
| + | LL query(int ql,int qr){ | ||
| + | if(qr<ql)qr+=p; | ||
| + | int front=0,tail=1,ml=qr-ql; | ||
| + | _for(i,ql,qr){ | ||
| + | while(front>=tail&&que[front].second<=dp2[rtop][i%p])front--; | ||
| + | que[++front]=make_pair(i,dp2[rtop][i%p]); | ||
| + | } | ||
| + | LL ans=-1; | ||
| + | _for(i,qr,qr+p){ | ||
| + | while(front>=tail&&i-que[tail].first>ml)tail++; | ||
| + | while(front>=tail&&que[front].second<=dp2[rtop][i%p])front--; | ||
| + | que[++front]=make_pair(i,dp2[rtop][i%p]); | ||
| + | ans=max(ans,cal2(dp1[ltop][(p-i+qr)%p],que[tail].second)); | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | char buf[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | p=read_int(); | ||
| + | mem(dp1[0],-1);dp1[0][0]=0; | ||
| + | mem(dp2[0],-1);dp2[0][0]=0; | ||
| + | _rep(i,1,n){ | ||
| + | scanf("%s",buf); | ||
| + | if(buf[0]=='I'){ | ||
| + | int w=read_int()%p,v=read_int(); | ||
| + | if(buf[1]=='F'){ | ||
| + | a[--lpos]=make_pair(w,v); | ||
| + | cal(dp1[ltop+1],dp1[ltop],a[lpos].first,a[lpos].second); | ||
| + | ltop++; | ||
| + | } | ||
| + | else{ | ||
| + | a[++rpos]=make_pair(w,v); | ||
| + | cal(dp2[rtop+1],dp2[rtop],a[rpos].first,a[rpos].second); | ||
| + | rtop++; | ||
| + | } | ||
| + | } | ||
| + | else if(buf[0]=='D'){ | ||
| + | if(ltop+rtop==1){ | ||
| + | ltop=rtop=0; | ||
| + | mpos=lpos+rpos>>1; | ||
| + | lpos=mpos+1,rpos=mpos; | ||
| + | } | ||
| + | else if(buf[1]=='F'){ | ||
| + | if(!ltop)rebuild(); | ||
| + | lpos++,ltop--; | ||
| + | } | ||
| + | else{ | ||
| + | if(!rtop)rebuild(); | ||
| + | rpos--,rtop--; | ||
| + | } | ||
| + | } | ||
| + | else{ | ||
| + | int ql=read_int(),qr=read_int(); | ||
| + | enter(query(ql,qr)); | ||
| + | } | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/线段树分治.1601690324.txt.gz · 最后更改: 2020/10/03 09:58 由 jxm2001
