Codeforces #169 Div2. C. Little Girl and Maximum Sum

さてDiv2 C、だんだん難しくなってきた。
http://codeforces.com/contest/276/problem/C

問題

整数の配列Aと、クエリが与えられる。
クエリの中身は配列の位置を表す２つの整数値L,Rで、A[L]～A[R]の和を返す。
ただし、これだけではつまらないのでこの問題に改変を加える。
各クエリの合計が最大となるように元の配列Aを並べ替え、その時のクエリの合計の最大値を答える。

解法

配列中の各要素が何回カウントされるかを求め、多い順に大きな数値を割り当てればよい。
なお、配列Aの要素は2*10^5、クエリも2*10^5あるので愚直にカウントするとTLEする。
よって、要素のカウント数にimos法を使うと良い。

int N,Q;
vector<ll> V,Ns;
int num[200002];

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	N=GETi();
	Q=GETi();
	V.resize(N);
	FOR(i,N) V[i]=GETi();
	sort(V.begin(),V.end());
	FOR(i,Q) {
		x=GETi()-1;
		y=GETi();
		num[x]++;
		num[y]--;
	}
	t=0;
	FOR(i,N) Ns.push_back(t+=num[i]);
	sort(Ns.begin(),Ns.end());
	t=0;
	FOR(i,N) t += V[i]*Ns[i];
	cout << t << endl;
	
	return;
}

まとめ

CFはクエリを大量に消化する問題が多いけど、この問題はちょっと変わったタイプの問題だな。