AGC079 o--x
A l(x) = min {a | lca[a, x) = a, a <= p(x) } という木を作ると答えが書ける 木を求める部分は、区間lcaを繰り返すとUFの経路圧縮のようなことになる
D D={2,..,2}のとき ans ⇔ N>=9(三角柱状のN=9の反例グラフを拡張)D={1,...,1}のとき ans ⇔ N>=6 それ以外はYesと予想 -> WA
井上裕太・河原林健一・宮下敦行・Bojan Mohar・Carsten Thomassen・Mikkel Thorupの論文“The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring”arxiv.org/abs/2603.24880が理論計算機科学のトップ会議FOCS2026のBest Paper Award受賞‼️おめでとう🎉🎉🎉
ARC231 xo---
A クエリ平方分割 d[x][y]と {x,y,c} を管理 flushがCHTでO(X(B + Y))、求値がO(B) O(N(X + Y))
B X = [0,A) + {1024}, Y = [0,B) + [1024,1024+C)
E 転倒数が偶数のものと奇数のものでペアを作る Bの値のmultiset固定で、複数の値があり得る最小の i に注目(無ければ転倒数偶数)
AGC078 -x-
A 判定はおかしな転倒ペアが無いかどうか 回数最小化は、各Bごとにその周りでできるCBA,CAB,BCAの回数の和の上界を定めるとそれが達成できると予想
B Y < X LISと同様に、長さ->(次の値への制約, 次の次の値への制約) のmin を管理 ->WA X,Yがiに依存しない定数であることを使うと予想
CF1120(Div.1) (oo)o----
A {0,1}^Nに対して、O(NlogN)個の区間についての「1が存在」「1が存在しない」という制約を満たすものを数える問題
B クエリ降順 forfeitを起こすiの集合Sを管理 一度Sから抜けたものは戻らない
C suffix maxはmaxとsecond maxのちょうど2種類 b ◦ pは存在するなら一意