Codeforces #179 Div1. A. Greg and Array

さてCF179。この回はCが割と簡単だったようで、初めてA,B,Cと３問本番に解けた。
ただ順位はそこそこだったけどね。
http://codeforces.com/contest/295/problem/A

問題

N個の配列A[0]～A[N-1]が与えられる。
また、M種類の処理が与えられる。i番目の処理は３つの数字L[i]、R[i]、D[i]からなり、この処理はA[L[i]]～A[R[i]]の値をD[i]ずつ加算する。
さらに、K種類のクエリが与えられる。j番目のクエリは２つの数字X[j]、Y[j]からなり、このクエリはX[j]～Y[j]番の処理を１回ずつ行う。

これらのクエリを行った後の配列Aの値を答えよ。

解法

imos法を２回行えばよい。
まず、K種類のクエリをimos法で処理して、各処理の実行回数を求める。
さらに、処理の実行回数を元にA[i]に加算される値を再度imos法で処理する。

ll A[100002];
ll L[100002],R[100002],D[100002];
ll NUM[100002];
ll AD[100002];

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	
	GET3(&N,&M,&K);
	FOR(i,N) A[i]=GETi();
	FOR(i,M) {
		L[i]=GETi()-1;
		R[i]=GETi()-1;
		D[i]=GETi();
	}
	FOR(i,K) {
		x=GETi()-1;
		y=GETi()-1;
		NUM[x]++;
		NUM[y+1]--;
	}
	
	j=0;
	FOR(i,M) {
		j+=NUM[i];
		AD[L[i]] += D[i]*j;
		AD[R[i]+1] -= D[i]*j;
	}
	
	t=0;
	FOR(i,N) {
		t+=AD[i];
		if(i!=0) cout << " ";
		cout << (A[i]+t);
	}
	cout << endl;
	
	return;
}

まとめ

累積和の演習問題だね。