問題概要
ユニークな通し番号を付けた虫たちを 個の塊に分ける。結果、 番目 ( 1-indexed ) の塊には 匹の虫がいて、その通し番号は( 0 番目の山にいる虫の数を便宜的に とおけば) である。
以下の形式のクエリを 件処理せよ。
- 整数 が与えられる。通し番号 をもつ虫がいる塊の番号を出力せよ。
解法
もしクエリの数が少なければ、塊を先頭から走査して答えを求めることができますが、それでは TLE します。より高速にクエリを処理する必要があります。
の累積和をとったものを とします。すなわち、 です。このとき、クエリ に対する答えは、 である最大の となります。 の値は に関して単調性をもつので、二分探索を適用することができます。こうすることで、前処理に 時間、全クエリを 時間で処理することができます。
コード
using VI = vector<int>; using VVI = vector<VI>; template < typename T = int > using VT = vector<T>; template < typename T > inline void input_n( VT< T > &out ) { copy_n( istream_iterator< T >( cin ), out.size(), out.begin() ); }; #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) (c).begin(), (c).end() int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n; cin >> n; VI as( n ); input_n( as ); int m; cin >> m; VI qs( m ); input_n( qs ); VI csum; partial_sum( ALL( as ), back_inserter( csum ) ); FOR( q, qs ) { cout << lower_bound( ALL( csum ), q ) - csum.begin() + 1 << endl; } return 0; }