Codeforces Global Round 2 : D. Frets On Fire

これも実装が軽くて助かったね。
https://codeforces.com/contest/1119/problem/D

問題

N本の弦を持つウクレレがある。
標準では、ここに(10^18+1)個のフレットがあり、端から高さ0,1,2,...,10^18の音がなる。
ただしi本目の弦はA[j]だけずれた高さ、すなわちA[j]～(A[j]+10^18)の高さの音が鳴るように調整されている。

以下のクエリに答えよ。

• 各弦、L番～R番のフレットを抑えて音を鳴らしたとき、現れる音の高さは何通りか。

解法

位置が異なる(R-L+1)の長さの区間が、N個あるとき、和となる区間の長さを求める問題となる。

まず弦をA[j]でソートし、次に隣接要素との差分を取ってこれまたソートしておこう。
クエリにおける長さの区間がWの場合、隣接要素との差分がW以下となる部分は連結して1個の要素になる。
事前に差分をソートしておけば、先頭のいくつかは全体で連結し、残りは全く連結しない状態になる。
あとは累積和など取っておけば区間の総長を高速に求められる。

int N,Q;
ll S[101010];
vector<ll> D,DS;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	sort(S,S+N);
	FOR(i,N-1) D.push_back(S[i+1]-S[i]);
	sort(ALL(D));
	DS.push_back(0);
	FORR(d,D) DS.push_back(DS.back()+d);
	
	
	cin>>Q;
	while(Q--) {
		ll L,R,W;
		cin>>L>>R;
		W=R-L+1;
		
		x=lower_bound(ALL(D),W)-D.begin();
		ll ret=(N-1-x)*W+W+DS[x];
		cout<<ret<<" ";
	}
	cout<<endl;
}

まとめ

シンプルな問題設定。これはDiv1Bぐらいにちょうどいいね。