[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;
}

https://atcoder.jp/contests/abc231/submissions/27851005