以上から、範囲1を1秒で進むか、一番近い累積xorで同じ値のところから「幅-1」秒進むかの遷移の（貰う）DPで解ける。
「一番近い累積xorで同じ値」のindexをmap等で管理する。
NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）
F問題 Operations on a Matrix
状態が多くて脳が破壊された。
だいたいの情報は両端キューで管理して適宜pop_front()するとすこし楽になる。
まずタイプ1(l,r,x)のクエリによってj列目に足された合計はすぐ求まる。 これを「累積和」と呼ぶことにする(遅延セグ木、FwnwickTreeでimos法)。
タイプ2(i,x)が問題で、タイプ3が来たときに、これより前で最新のタイプ2の更新値だけが影響する。
タイプ3(i,j)が来た時に、「i行目のタイプ2での最後の更新値+現在の累積和[j]-最後のタイプ2が来た時点での累積和[j]」を計算できれば答えが求まる。
しかし愚直にやるとO(MQ)のメモリが必要になり無理。
うまく必要な情報だけを管理したい。
具体的にどうするか。
i行目で次のタイプ2のクエリがくるまでの間にあるi行目のタイプ3(i,j)について、両端キュー[i]に現在の累積和[j]を追加する。
i行目の最終更新値[i]=xに更新する。
（事前にi行ごとにタイプ2がくるタイミングを計算しておく（両端キューにいれておく））
（事前にi行ごとにタイプ3を両端キューにいれておく）
（（とくにi行目で最初のクエリ2の時）現在のタイプ2が来るまでの間に存在するタイプ3に対応する値を追加しないように注意）
a = 現在の累積和[j]
b= 両端キュー[i].pop_front() または 空なら0
c = 最終更新値[i]
として が求める答え。
（両端キュー[i].pop_front()がi行目で最後にタイプ2が来た時点での、現在のタイプ3に対応するj列目の累積
和になる）
両端キューにいれた値は適宜捨てていくことで、計算量を抑えることができる。
https://codeforces.com/contest/1674
難しいのは隣り合う2つの壁を壊すパターンだと思うが、3分探索で提出したらACした。
正当性があるのかはすこし疑問があるが参考まで。
片方の2で割る回数を、整数の3分探索で調べて、合計手数のminを求める。
調べる数を右左両方を試した。
停止しないのでループ回数を固定する。
トポロジカルソートして使う辺をDPで試す。
ある頂点Pにたどり着くときのスコアは、頂点Pに入ってくる辺のうちスコアの最大値＋1になる。（＋1は頂点Pが一つ足されるスコア）。
ただし、頂点Pに入ってくる辺が出てくる側の頂点Qについて、頂点Qの出自数が1の場合、この辺は使えないので除外する必要がある。
グラフを作るときに辺を逆にしたグラフを作っておいて、頂点Pに入ってくる辺の出発点の頂点Qを求められるようにした。
https://codeforces.com/contest/1668/problem/D
難しい。
公式解説のままです。
まず愚直なDPを考えるdp[i]=i番目まで決めた時のベストスコアとする。 このときAの累積和を求めておけば、j=0からi-1までためして、dp[i]= max(dp[j]+score(j,i)) となる。scoreは区間和の正負で符号が変わる部分列の長さ。
ここで実は部分和を試すのは無駄だとわかる。
なぜなら最適解として長さ2以上の部分和がマイナス部分があったとすると、その部分に含まれる項はすべて負数となるので、長さ1に分割してもスコアは変わらない。（ もし正の数が含まれるなら、全部を長さ1に分割するすることでスコアが良くなって矛盾する）
部分和が0の場合も似たようなことが言える。
よって、（愚直なDPの遷移を考えれば明らかに）DPの更新はスコアが最も良くなる部分からの遷移だけ考えれば良い。
max(score(j,i))は部分和がプラスのうち、max(dp[j]+(i-j)) となる。
k= dp[j]+(i-j)
iが邪魔なので移項して
k-i = dp[j]-j
つまり部分和がプラスのうち(dp[j]-j)の最大値が高速に求まれば良い。
セグ木が使える。
ただし、部分和は大きくなるので、累積和を座標圧縮してセグ木に乗せる必要がある。
解法
累積和をS[i]
dp[i] = i番目まで決めた時のベストスコア
セグ木をseg[sum]=x として 部分和sumがA[i]未満（A[i]-「0からjまでの部分和」がプラスを取得したい）のときのベストスコアを更新に使用する。
ベストスコアがないときは長さ1として追加する。
A[i]未満を候補にするのは、A[i]-sum < 0 つまり部分和がマイナスや0になるなら長さ1とするのが最適だから。
dp[i] = max(dp[i-1]+1 , seg[S[i]] + i )
セグ木の更新
seg[S[i]] = max(seg[S[i]], dp[i] - i )
実際はセグ木は座標圧縮が必要。
以上でAC。
（テストケース毎に出力したらTLEした）
https://codeforces.com/contest/1673/problem/C
問題特有の考察はできたけどDPが解けなかった。 分割数って有名問題らしいけど難しい。
制約から40000以下の回文数はすくなそう（M種類）となって、dp[N][M] = 和がNのとき最後に使ったのがM番目の回文数のときの場合の数としてDPすれば行けるかと思った。この場合遷移にもかかって、全体で
になって間に合わなかった。
この問題は分割数として有名問題みたい。
とはいえ難しい。
結論はdp[N][M] を和がNのときM番目以下の回文数を使う時の場合の数として、
dp[N][M] = dp[N-d][M] + dp[N][M-1]
（d=M番目の回文数）
となる。
なぜこれでうまくいくのか。 dp[i][j]を更新する時を考える。
j番目の回文数=d 以下をつかって和がiになる場合の数を求めたい。
dを使わない場合dp[i][j-1]なのは明らかで、これが式の右側。
（j-1番目以下の数をつかっているのでdは使用されていない）
dを少なくとも1回使う場合、d以下の回文数をつかって和が(i-d)になる場合の数になって、これが式の左側。
dp[i-d][j]はdを使っているかいないかを問わないことがポイント。
dp[i-d][j]がdを使っていなくても、i=i-d+d としてdを少なくとも一回は絶対つかう場合の数を考えていることに注意。
dを含まない場合と、dを少なくとも1つ使用する場合で全パターン網羅できることもポイント。
dpの初期化はdp[0][j]=1
j番目以下の回文数を使って、和が0のときの場合の数を1とする
以上を実装してAC。
言われてみればなるほど。
本番中は1を追加する場所を全部試すとMを追加する場所が高速に求まったりするのかな？という方向で考えてたけどちょっと外してた感。
まず、同じ値が並べばコストは0。 差が1ならコスト1なので、隣り合う値がaとbのときコストをb-aとすると、この間にaからbの値を順番に入れれば、コストはb-aのまま変わらない。
言い換えると、aとbの間に c または
を追加してもコストは変わらない。
よって入力Aの最小値と最大値を求めると、この最小値から最大値の間の値はコストを変化させずに、Aのどこかの間に入れることができる。
さらに、1から最小値、最大値からMの値は昇順または降順に任意の間にいれるのが最善となる。
そして上記の通りコストは変わらないので実質1とMをどこにいれるかという問題になる。
任意の場所(iとi+1の間）に1を追加することを考える。
このときにコストの変化は となる。
よって予めAのコストを求めてから、1を追加する場所を全部ためして最小値を取れば、1を追加する場所はで求めることができる。
同様にMを追加する場所を求めることができる。
問題は1とMを同じ場所に追加する時だが、上の方法で1とMを同じ場所に追加したときのコストの計算結果は、正しくコストを求めた時よりも絶対に大きくなるので、(答えとして最小値をとるので)そのまま処理をしてよい。
その上で、1とMを同じ場所に追加する場合は、任意の場所に「1 M」と追加するときと「M 1」と追加するときの両方を試して最小値をとれば求める答えになる。
ちょっとした注意点として、全部まとめて処理して最小値をとることは（たぶん）できないので処理をわけて丁寧にやる必要がある。
