题解：P9790 [ROIR 2020] 海报 (Day 2)

· · 题解

题目传送门

思路

先考虑没有环怎么做，有一个显然的线性 DP，定义 f_{i,j} 代表选到了第 i 个点，结尾最多连续选了 j 个点的最大值，因为每次只修改一个点，考虑放到线段树上做。设 v_{u,i,j} 代表线段树上的节点 u，从左边连续选不超过 i 个，从右边连续选不超过 j 个，然后类似于朴素 DP，可以直接在线段树上合并左右儿子答案。

但是这样没有考虑环的情况，因此需要在合并线段树根节点左右儿子的时候特殊处理一下，让左儿子左边连续段长度和右儿子右边连续段长度合起来也不超过 4 即可。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=4e4+10;
int n,a[N],q;
#define pb push_back
#define mk make_pair
struct tree{
    int l,r,v[4][4];//v[i][j] 从左边连续不超过 i 个，右边连续不超过 j 个的最大值
    #define lson(u) (u<<1)
    #define rson(u) (u<<1|1)
}t[4*N];
inline void push_up(int u){
    for(int a=0;a<4;++a)
    for(int b=0;b<4;++b)
      t[u].v[a][b]=0;
    int llen=t[lson(u)].r-t[lson(u)].l+1,rlen=t[rson(u)].r-t[rson(u)].l+1;
    for(int a=0;a<4;++a)
    for(int b=0;b<4;++b)
    for(int i=0;i<4;++i)
    for(int j=0;i+j<4;++j){
      if(a>=llen&&j&&b>=rlen&&i){
        if((a+j<4)&&(b+i<4))t[u].v[a+j][b+i]=max(t[u].v[a+j][b+i],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
        continue;
      }
      if(a>=llen&&j){
        if(a+j<4)t[u].v[a+j][b]=max(t[u].v[a+j][b],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
        continue;
      }
      if(b>=rlen&&i){
        if(b+i<4)t[u].v[a][b+i]=max(t[u].v[a][b+i],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
        continue;
      }
      t[u].v[a][b]=max(t[u].v[a][b],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
    }
}
inline void build(int u,int l,int r){
    t[u].l=l;
    t[u].r=r;
    if(l==r){
      for(int i=1;i<4;++i)
      for(int j=1;j<4;++j)
        t[u].v[i][j]=a[l];
      return;
    }
    int mid=(l+r)>>1;
    build(lson(u),l,mid);
    build(rson(u),mid+1,r);
    push_up(u);
}
inline void update(int u,int x){
    if(t[u].l==t[u].r){
      for(int i=1;i<4;++i)
      for(int j=1;j<4;++j)
        t[u].v[i][j]=a[x];
      return;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(x<=mid)update(lson(u),x);
    else update(rson(u),x);
    push_up(u);
}
inline int getans(){
    if(n==1)return a[1];
    int ans=0;
    for(int a=0;a<4;++a)
    for(int b=0;a+b<4;++b)
    for(int i=0;i<4;++i)
    for(int j=0;i+j<4;++j)
      ans=max(ans,t[2].v[a][i]+t[3].v[j][b]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    build(1,1,n);
    cout<<getans()<<"\n";
    cin>>q;
    int x,c;
    while(q--){
      cin>>x>>c;
      a[x]=c;
      update(1,x);
      cout<<getans()<<"\n";
    }
    return 0;
}