2018-02-08から1日間の記事一覧
各素数ごとに独立になっているので、それぞれ解いて解を掛け合わせればよい。 素数 p の出現回数が一番多くなる場所を決めると、全体で何回 p が出現するかを O(NlogN/p) 程度で計算でき、場所の個数は、Nなので、各素数ごとに、O(N^2logN/p) で計算できる。…
区間を 2 つ選んで符号を反転させることができるので、区間和の最小値が計算できれば、あとは簡単に計算できる。 これは、O(N) でやってよいので、配列が更新される度に最初から計算し直せば良い。(解いているときは何も考えずに、StarrySky Tree を貼ってし…