01010...と10101...、...10101と...01010になるように変形して先頭と末尾からの累積和がっちゃんこじゃね?