EDPC-W Intervals - blogskol

W - Intervals

今回は1-indexedで考える
左から考えていくとした時、例えば、 $n=20$ として
$01101001001010000???$ の時100点
$10100010000010000???$ の時120点
といった具合にとる点数が確定している場合、上のパターンを答えとして採用することはありえない
なぜなら、残りの3文字により追加される点数はどちらも同じようになるから
具体的に考えると、18文字目を1にすることで新しく獲得する点数は

$\sum \{ a_i | 13 < l_i \leq 18 \leq r_i \}$

結局遷移は1が立ってる最も右端の場所のみから決まるので、
$dp[i]:i$ 番目が $1$ でそれ以降 $0$ の時の最大値としてやればいい

遷移は

$dp [k ] = \max_{0 \leq i< k} dp[i ] + \{ a_j | i< l_j \leq k \leq r_j \}$

$dp[i ] + \{ a_j | i< l_j \leq k \leq r_j \}$

を1つのNodeとして見れば動的な区間maxなのでセグ木を使いたくなる

$\{ a_j | i < l_j \leq k \leq r_j \}$

の挙動を考える
$k$ が大きくなると $l_j$ 側の制約は緩くなり、 $r_j$ 側の制約が厳しくなることが分かる
そこで、 $k$ が上がるたび、
$1.l_j$ 側の制約を新たに満たしたものを加算
$2.r_j$ 側の制約を新たに破るものを減算
してやればいい

まず1について、 $dp[k]$ を更新する直前に $l$ の制約を新たに満たすのは $l=k$ なので、 $\sum \{a_j|l_j=k\}$ を $[0,k)$ に加算する
次に2について、 $dp[k]$ を更新する直前に $r$ の制約を新たに破るのは $r=k-1$ なので、各 $\{r_j=k-1\}$ について、1の加算をリセットする
すなわち、 $[0,l_j)$ に $-a_j$ を加算する

区間加算と区間maxなので、遅延セグ木を使うことで解ける
遅延セグ木のコード載せると見づらいので省略
ACコードには当然載せてあるので気になる人はそっち見て

#include <bits/stdc++.h>  
using namespace std;  
  
using ll=long long;  
struct P{int l;ll a;};  
ll L[200001],ans;  
vector<P> R[200001];  
  
int main(){  
  int n,m;cin>>n>>m;  
  while(m--){  
    int l,r,a;cin>>l>>r>>a;  
    L[l]+=a;  
    R[r].push_back({l,a});  
  }  
  seg;  
  /*  
  update(l,r,a):[l,r)にaを加算  
  query(l,r):[l,r)の最大値  
  set_val(i,S):i番目にSを代入  
  が出来る遅延セグ木  
  */  
  seg.set_val(0,0);  
  for(int i=1;i<=n;i++){  
    seg.update(0,i,L[i]);  
    ll S=seg.query(0,i);  
    if(ans<S)ans=S;  
    seg.set_val(i,S);  
    for(P p:R[i])seg.update(0,p.l,-p.a);  
  }  
  cout<<ans<<endl;  
}

Submission #11367161 - Educational DP Contest