题意分析

我们用\(f[i][j]\)表示当前到达第\(i\)个位置水位高度为\(j\)的答案

如果那么\(h[i]\)为\(i\)和\(i+1\)之间的支柱高度

那么如果\(j≤h[i]\)的话

\(f[i+1][0...h[i]]=max\{f[i][0...h[i]]\}\)

否则的话直接让\(f[i+1][j]=f[i][j]\)

发现第二种可以直接继承

第一种可以区间求\(max\)然后区间\(max\)覆盖

使用线段树维护

同时满足限制的话使用区间加

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 500008#define IL inline#define M 608611#define D double#define ull unsigned long long#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/int T,n,m,cnt,tot;int num[M],res[M],tre[M<<1],tag_cdy[M<<1],tag_wzy[M<<1];vector
                    
                      cdy[M],wzy[M];IL void down(int si){ if(!tag_cdy[si]&&!tag_wzy[si]) return; int d1=tag_cdy[si],d2=tag_wzy[si]; tag_cdy[si<<1]+=d1; tag_cdy[si<<1|1]+=d1; tag_wzy[si<<1]=max(tag_wzy[si<<1]+d1,d2); tag_wzy[si<<1|1]=max(tag_wzy[si<<1|1]+d1,d2); tre[si<<1]=max(tre[si<<1]+d1,d2); tre[si<<1|1]=max(tre[si<<1|1]+d1,d2); tag_cdy[si]=tag_wzy[si]=0;}IL void add(int si,int lenow,int rinow,int le,int ri,int d){ if(le>ri) return; if(lenow==le&&ri==rinow) { tre[si]+=d; tag_cdy[si]+=d; tag_wzy[si]+=d; return; } down(si); int mid=(lenow+rinow)>>1; if(ri<=mid) add(si<<1,lenow,mid,le,ri,d); else if(mid
                     
                      ri) return;// printf("now at TREE is %d %d (%d %d)\n",lenow,rinow,le,ri); if(lenow==le&&rinow==ri) { tre[si]=max(tre[si],d); tag_wzy[si]=max(tag_wzy[si],d); return; } down(si); int mid=(lenow+rinow)>>1; if(ri<=mid) update(si<<1,lenow,mid,le,ri,d); else if(mid
                      
                       ri) return -inf;// printf("now at TREE is %d %d (%d %d)\n",lenow,rinow,le,ri); if(lenow==le&&rinow==ri) return tre[si]; down(si); int mid=(lenow+rinow)>>1; if(ri<=mid) return qury(si<<1,lenow,mid,le,ri); else if(mid