[ABC231] F - Jealous Two
[Q] https://atcoder.jp/contests/abc231/tasks/abc231_f
0. 座標圧縮して、pairでsortして、BITした。
1. takahashiプレゼントを選んだら、Aはそれ以下のものを、Bはそれ以上のものを選べば、aokiプレゼントが取れる。
2. takahashiプレゼントを探索すればいい。
3. どうやって効率化しよう？
Q.入力例1
N=3
50 100 150
1 3 2
0. takahashiの大きい順番にpairでsortする。
150 100 50
2 3 1
1. takahashiプレゼントを捜索する。
1) takahashi: index 0 を選ぶ場合
A[0] = 150
B[0] = 2
2人が嫉妬しないような、選べるプレゼントは、次の2つを満たすもの
(1) takahashiが嫉妬しないのは、A[0] = 150以下のプレゼント。A[0]~A[2]が選択肢
(2) aokiが嫉妬しないのは、B[0] = 2 以上のプレゼントなので、B[0]=2 と B[1]=3
(1)について、index i 以下すべてを選べる。
(2)について、B[i]以上の個数が選べる。
(1)を満たすためにsortした。
(2)は、BIT格納でいける。2つトラップが残っている。
Q. BITだと、0<= A <= 1e9 がきつい？
A. 座標圧縮する。
値は大小関係さえ維持されていれば問題なかった。
Q. 入力例3
N=10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8
0. 座標圧縮し、{A, -B} でsortする
1. -BをBに復元する。
7 6 5 5 4 3 3 2 1 1
4 4 2 2 1 2 4 1 3 4
-Bにしたのはあとで効いてくる。
2. BITで、あらかじめすべてのB[]を加算しておく。
BIT<400010> bits;
bits.sum(4) = 10 // 4以下のものは全部で10個
bits.sum(3) = 6 // 3以下のものは全部で6個
bits.sum(2) = 5
bits.sum(1) = 2
2. takahashiプレゼントを捜索する。
1) takahashi:A[0] = 7 の場合
aoki:B[0] = 4
aokiが取れるのは、
(1)takahashi の嫉妬しない index 0以上
(2)aoki の嫉妬しない B[0]=4 以上
bitsの全体から 3以下 を除けばいいので、
bits.sum(400005) - bits.sum(3) = 4 通り
ans += 4 // 4
・index 0 を候補から外す下処理
(1)の条件から、index 0 はもう取れないので、BIT から、B[0]の選択肢を除いておく。
bits.add(B[0], -1);
次の捜索。
2) takahashi:A[1] = 6 の場合
aoki: B[1] = 4 なので
ans += bits.sum(400005) - bits.sum(3) = 3通り // 7
・index 1 を候補から外す下処理
bits.add(B[1], -1);
次の捜索。
3) takahashi: A[2] = 5 について。
B[2] = 2
ans += bits.sum(400005) - bits.sum(B[2]) = 6 通り // 13
ここで、次のindex の値を見ると、
A[2] ＝A[3] = 5
B[2] = B[3] = 2
まったく同じ値がくる。
index 3の条件時に、index 2 の選択肢をとることも可能なので、
BITを除かず、連続数をメモしておく必要がある。
A[i] == A[i+1] && B[i] == B[i+1]
のときには、
bits.add(B[2], -1); をスキップし、 cnt = 2をメモしておく。
次の捜索。
4) takahashi: A[3] = 5
B[3] = 2
ans += bits.sum(400005) - bits.sum(B[2]) = 6 通り // 19
次のindex の値が異なるので、
・index 2,3 を候補から外す下処理
bits.add(B[3], -2); // cnt = 2 なので
cnt = 1 // 初期化
を実施。
また、Aの値が同じ場合、
A[] = 3 3
B[] = 2 4
Bを小さい値から処理すれば、Bが4以上を選ぶときに、2の値の有無は関係なくなるので、考慮を減らせる。
bits.add(2, -1)
をしたあとに、
bits.add(4, -1)
すれば、B=4以上を探すときに影響しない。
なので、-Bでsortした。
ans = 37実装
// 座標圧縮
template<typename T>
ll comp(vector<T> &A){ map<T, ll> mp; for(auto p: A) mp[p] = 0; ll sz = 0; for(auto &p: mp) p.second = ++sz; for(auto &a: A) a = mp[a]; return sz; }
int main(){
cincout();
ll N;
cin >> N;
vector<ll> A(N);
vector<ll> B(N);
vector<pll> P(N);
Bit<400010> bits;
rep(i, N) cin >> A[i];
rep(i, N) cin >> B[i];
comp(A);
comp(B);
rep(i, N) P[i] = {A[i], -B[i]}; // -Bでいれる
sort(all(P), greater<pll>());
rep(i, N){ // BITの初期入れ
bits.add(-P[i].second, +1);
}
ll ans=0;
ll cnt=1;
rep(i, N){
ll a=P[i].first;
ll b=-P[i].second; // これ以上のものを選ばないといけない
ll add = bits.rangesum(b-1, 400005);
ans += add;
if(i<N-1 && a==P[i+1].first && b==-P[i+1].second){
++cnt;
}
else{
bits.add(b, -cnt);
cnt=1;
}
}
cout << ans << endl;
}