読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Mo's, Algorithm の検索結果:

第3回 ドワンゴからの挑戦状 本選 : B - ニワンゴくんの約数

…コストが小さいため、Mo's algorithmで解くことができる。なお、区間の増減の際複数の素因数に対し処理を行う必要があるので、Mo's algorithmを適用するだけだとまだちょっと重くTLEする。 Editorialでは、小さな素因数に対しては区間に対する素因数の指数の総和を前処理することで高速化している。 以下のコードではこのアプローチを取らず、同一の指数の複数回加減算をまとめたり、インラインアセンブラによる除算の高速化で無理やり通している。 int N,Q; l…

CSAcademy Round #13 : F. Interval Expected Max

…。 解法 平方分割でMo's Algorithmして解く。 区間の長さを1変えるとき、2要素の最大値の総和は以下のように変化する。区間を1伸ばし、値xが追加される場合、 xとx未満の要素が選ばれると考えると、x未満の要素の数だけ、2xが加算される。(2xは選び方が順不動なため) xとx以上の要素が選ばれると考えると、x以上の要素の数だけ、2*その要素が加算される。(2倍は選び方が順不動なため) 言い換えると、x以上の要素の総和の2倍が加算される。 自身が2回選ばれる場合、xが…

Codeforces ECR #006: F. Xors on Segments

…よ。 解法 想定解はMo's Algorithmなのだが…。 愚直にO(N^2)通りf(A[L],A[R])を列挙しても間に合ってしまうようだ。 int N,M; int A[50050],X[50500]; int L[50050],R[50500]; int XX[1010101]; int ma[50505]; int ret[50505]; void solve() { int i,j,k,l,r,x,y; string s; for(i=1;i<=1000000;i…

Codeforces #340 Div2. E. XOR and Favorite Number

…は定番のテクがある(Mo's Algorithmと呼ばれているらしい?)。クエリをfloor(L/√N)昇順でfloor(L/√N)が一致するものはR順に並べ替えよう。 すると1回のクエリあたり区間の左端Lを動かす量は平均O(√N)となることが期待できる。 また区間の右端は基本的に右に動かすだけで、前のクエリと比べfloor(L/√N)が異なるときだけ左に戻すので、左に戻す回数はO(√N)であることが期待できる。 よってLもRも動かす回数はO(N√N)程度動かせばよい。 in…