これはTLでヒントを見てしまったのですんなり。見てなくても何とか解けたかな。
http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c
問題
N要素の整数列A[i]と、正整数Mが与えられる。
以下のクエリ(L[i],R[i],D[i])に順次答えよ。
- 数列の区間A[L[i]...R[i]]それぞれにD[i]を加算する。
- その後、A[L[i]...R[i]]中にあるMの倍数の数を答える。
解法
平方分割で解く。
N要素の区間を、例えば連続するD個ごとの区間に区切ろう。
各区間rにおいて、Mで割った余りがq=0~(M-1)のそれぞれとなる要素の数B(r,q)と、区間r全体に加算された値の総和S(r)を保持する。
以後、個々の分割区間毎に処理する。
まず加算パートでは、加算範囲が分割区間全体を覆う場合、「区間全体に加算された値の総和」だけを更新すればよい。
そうではない場合、対応するA[i]だけ更新しよう。
D=√N程度に取れば、両方の処理はO(√N)で済む。
次にMの倍数を求める処理だが、クエリの範囲が分割区間全体を覆う場合、総和S(r)を加えてA[i]がMの倍数となる要素を答えればよいのでB(r,-S(r)%M)を答えればよい。
そうでない場合、対応するA[i]+S(r)のうちMの倍数となるものを数えよう。
int N,M,Q; int A[101010]; int T[101010]; int num[300][101010]; const int DIV=400; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>Q; FOR(i,N) { cin>>A[i]; A[i]%=M; num[i/DIV][A[i]]++; } while(Q--) { int L,R,D; cin>>L>>R>>D; L--;R--; int ret=0; while(L<=R && L%DIV) { num[L/DIV][A[L]]--; (A[L]+=D)%=M; num[L/DIV][A[L]]++; if((A[L]+T[L/DIV])%M==0) ret++; L++; } while(R>=L && R%DIV!=DIV-1) { num[R/DIV][A[R]]--; (A[R]+=D)%=M; num[R/DIV][A[R]]++; if((A[R]+T[R/DIV])%M==0) ret++; R--; } while(L<R) { (T[L/DIV]+=D)%=M; ret += num[L/DIV][(M-T[L/DIV])%M]; L+=DIV; } cout<<ret<<endl; } }
まとめ
平方分割の境界処理、最近こんな感じのをよく使う。