Codeforces Round #672 (Div. 2) - C2. Pokémon Army (hard version)
解説
C1は
dp[i][j] := i番目まで見た時、次が+ならj=0 次が-ならj=1
みたいに定義したら解けます。
これの応用で[l, r]の区間で dp[j][k] := lが(+ or -)ではじまり、rが(+ or -)でおわる
見たいな風にするとセグ木にのります
C1は
dp[i][j] := i番目まで見た時、次が+ならj=0 次が-ならj=1
みたいに定義したら解けます。
これの応用で[l, r]の区間で dp[j][k] := lが(+ or -)ではじまり、rが(+ or -)でおわる
見たいな風にするとセグ木にのります