みんなのプロコン本選 : C - 倍数クエリ

これは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;
	}
	
}

まとめ

平方分割の境界処理、最近こんな感じのをよく使う。