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

· · 题解

我居然独立做出了这题？这题真的不是紫的难度啊。

暑假集训第一场考试 T1，洛谷上过了但校测 TLE 了。

一种不用 ddp 的做法，感觉比 ddp 强。

朴素线段树做法。

考虑在线段树上每一个节点开 16 个答案统计。形如 ans_{l,r}，代表左边有 l 个被选的位置，右边的 r 个被选的位置的最优解。

合并两个块时，要考虑原先的状态是否合法、新的状态正确的 (l,r) 的值。还要在每一层剪枝。

查询时查询第 1 个块的答案即可，注意只能查 l+r<4 的部分。我是直接写的 void 类型的 query 查询函数。

视 n,q 同阶，理论时间复杂度为 O(n\log n)，但因为它在枚举 l,r 时带了 4^4=256 的常数，所以可能还没有有些 O(n\sqrt n) 和 O(n\log^2n) 的做法跑得快。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar(); 
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n'); 
}
struct node{
    int l,r;    //代表这里的区间 
    int ans[4][4];  //ans[x][y]  代表选取这里导致的左边有 x 个点 右边有 y 个点 总和不能大于 3  
}tree[2*114514];
int n,q;
int a[20*2025]; //40050 
void pushup(int id){
    int l=tree[id].l,r=tree[id].r; 
    int l1=tree[id*2].l,r1=tree[id*2].r;
    int l2=tree[id*2+1].l,r2=tree[id*2+1].r;
    for(int i=0;i<=3;i++){
        for(int j=0;j<=3;j++){
            tree[id].ans[i][j]=0;   //这种情况先初始化  
        }
    } 
    //接下来就是 [l1,l2] 和 [r1,r2] 的区间合并 
    //注意一种新的思路：一开始不考虑若干人走在一起的情况 等到询问时统一处理 
//  for(int i=0;i<=min(3,r1-l1+1);i++){
//      for(int j=0;j<=min(3,r2-l2+1);j++){
//          //仅需考虑中间两个 
//      }
//  } 
    for(int i=0;i<=min(3ll,r1-l1+1);i++){
        for(int j=0;j<=min(3ll,r1-l1+1);j++){
            //有一个地方必须剪枝：[i,j] 代表的区间不合法 
            if((i+j>(r1-l1+1))&&(i+j)<2*(r1-l1+1)){
//              if(id==2)   cout<<i<<' '<<j<<' ',cout<<"谭总的世界-031"<<endl;
                continue;   //这种情况区间不合法 直接忽略   
            }   
            if(i==(r1-l1+1)&&j==0){
//              if(id==2)   cout<<"谭总的世界-032"<<endl;
                continue;
            }
            if(j==(r1-l1+1)&&i==0){
//              if(id==2)   cout<<"谭总的世界-033"<<endl; 
                continue;   //剔除所有的不合法情况  
            }
            for(int i1=0;i1<=min(3ll,r2-l2+1);i1++){
                if(j+i1>=4) continue;   //这种情况忽略考虑  
                for(int j1=0;j1<=min(3ll,r2-l2+1);j1++){
                    if((i1+j1)>(r2-l2+1)&&(i1+j1)<2*(r2-l2+1))  continue;   //这也是不合法的区间 忽略  
                    //接下来转移到的地方称为 [L,R] 注意改成了大写 
                    if(i1==(r2-l2+1)&&j1==0)    continue;
                    if(j1==(r2-l2+1)&&i1==0)    continue;   //这些情况都不合法 
                    int L=0,R=0;    //初值实际上没有任何意义 只是一种摆设 
                    if(i==(r1-l1+1)&&j==(r1-l1+1)){
                        //代表这里左边是满的 
                        L=i+i1; //这就是左边的情况  
                    } 
                    else    L=i;
                    if(L>=4)    continue;   //也没有意义   
                    if(i1==(r2-l2+1)&&j1==(r2-l2+1)){
                        R=j+j1;
                    }
                    else    R=j1;   //最右侧的点 
                    tree[id].ans[L][R]=max(tree[id].ans[L][R],tree[id*2].ans[i][j]+tree[id*2+1].ans[i1][j1]);
                    //这是真正有用的转移的部分！  
                }
            }
        }
    }
} 
void build(int id,int l,int r){
    tree[id].l=l,tree[id].r=r;
    if(l==r){
        tree[id].ans[0][0]=0;
        tree[id].ans[1][1]=a[l];    //代表这里的取值系数  
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid),build(id*2+1,mid+1,r);
    pushup(id);
}
void modify(int id,int x,int y){
    int l=tree[id].l,r=tree[id].r;
    if(l==r){
        tree[id].ans[0][0]=0;
        tree[id].ans[1][1]=y;   //直接处理成这样 
        return; 
    }
    int mid=l+r>>1;
    if(x<=mid)  modify(id*2,x,y);
    else    modify(id*2+1,x,y);
    pushup(id);
}
void query(){
    //全部都在 tree[1] 上询问 
    int include13=0;    //代表最终答案  
    for(int i=0;i<=3;i++){
        for(int j=0;j<=3;j++){
            if(i+j>=4)  continue;   //只考虑较小情况下的答案 
            include13=max(include13,tree[1].ans[i][j]); 
//          cout<<'#'<<i<<' '<<j<<' '<<tree[1].ans[i][j]<<endl;
        } 
    } 
    write2(include13);  //代表输出目前的解  
    return;
} 
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
//  cout<<'#'<<tree[4].ans[2][2]<<endl;
//  cout<<'#'<<tree[5].ans[1][1]<<endl;
//  cout<<'#'<<tree[2].ans[3][3]<<endl;
    query();    //把 query 处理成这种 void 函数 也是很妙的  
    q=read();
    while(q--){
        int x=read(),y=read();
        modify(1,x,y);
        query();
    } 
    putchar('\n');
    return 0;
}//全世界 好像只有我疲惫

考试写完这题啥都写不动了，最终就等着 100+0+12+0=112 的结尾。结果在学校 OJ 上 TLE 了，考试毁了……