A. Cubes Sorting すべての要素が異なり、逆順に並んでいるとき、バブルソートは最大で回の操作が必要になります。そうでないとき、それ未満で終わります。 void solve(){ int N; cin >> N; vector<ll> a(N); rep(i,N)cin >> a[i]; rep(i,N-1){ if(a[i] <= a[i+1</ll>…

atcoder.jp 区間を二次元座標とみなし、二次元累積和で。 一方、クエリ先読みして区間を終端ソートすると、終端が前の区間から順に確認していくことで問題を解くことができる。終端の順番を固定し、始端の分布をBITでもち、和をで得ることができ、計算量はと…

yukicoder.me 類題がこれとこれ。 coonevo.hatenablog.com coonevo.hatenablog.com 上記の類題と違うのは値の範囲が広いこと。こういうやつはクエリ先読みすると種類数が少ないから順序データに座標圧縮すればよい。あとはライブラリでやるだけ。 座圧のうま…

問題へのリンク 問題 グリッド上に人が人いる。南北東西どちらかの方向を向いている。 例えば、東を向いている人は、西にはいけないが、他はどの方向にも行ける。人の通りうる数が最大の座標を求めよ。 解法 軸ごとに独立に考えてよい。それぞれの最大座標が…