upper_boundとlower_boundを用いてABC77 C問題を解く

競技プログラミングの備忘録用
lower_boundとupper_boundを用いてABC77 C問題を解く
C - Snuke Festival

問題

今年もすぬけ祭の季節がやってきました。りんごさんは、まず手始めにすぬけ君召喚の儀式を執り行おうと思っています。 儀式には祭壇が必要で、祭壇は上部、中部、下部の$3$つのカテゴリーのパーツ$1$つずつからなります．祭壇の$3$カテゴリーのパーツがそれぞれ$N$個ずつあります。$i$個目の上部のパーツのサイズは$A_i$，$i$個目の中部のパーツのサイズは$B_i$、$i$個目の下部のパーツのサイズは$C_i$です。祭壇を作るにあたっては、中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません。逆に、この条件を満たす任意の$3$つのピースを組み合わせて祭壇を作ることができます。りんごさんが作ることのできる祭壇は何種類あるでしょうか。ただし、$2$つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち 少なくとも$1$つが異なることを言います。

制約

• $1≤N≤10^5$
• $1≤A_i≤10^9(1≤i≤N)$
• $1≤B_i≤10^9(1≤i≤N)$
• $1≤C_i≤10^9(1≤i≤N)$
• 入力は全て整数である

方針

この問題は$A_i<B_i<C_i$を満たす組み合わせの数を求めればよい．

全探索をすると$O(N^2)$となり間に合わない．そこで$B_i$を中心に考え，全ての$B_i$について，lower_boundとupper_boundを用いて$B_i>A_i$を満たす$A_i$の数と，$B_i<C_i$を満たす$C_i$の数を求めていくことで$O(NlogN)$で計算できる．

lower_boundとupper_boundの使用例

# include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> A={0,1,2,2,3,3,3,4,4,4,4};
    cout << lower_bound(A.begin(),A.end(),2)-A.begin() << endl; //2
    cout << upper_bound(A.begin(),A.end(),2)-A.begin() << endl; //4
    cout << A.end()-lower_bound(A.begin(),A.end(),2) << endl;   //9
    cout << A.end()-upper_bound(A.begin(),A.end(),2) << endl;   //7
}

lower_boundは指定したkey以上の値の一番左のイテレータを返却
upper_boundは指定したkeyより大きい一番左のイテレータを返却
注意点として使用する配列はソートしておく必要がある．

解法コード

# include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<ll> VLL;
typedef vector<PLL> VP;
const static int INF = 1000000000;
const static int MOD = 1000000007;
# define rep(i,n) for (ll i=0; i<(ll)(n); i++)
# define repd(i,n) for (ll i=n-1; i>=0; i--)
# define rept(i,m,n) for(ll i=m; i<n; i++)
# define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
# define all(x) (x).begin(), (x).end()
# define F first
# define S second
# define PF push_front
# define PB push_back
# define SORT(V) sort((V).begin(), (V).end())
# define RVERSE(V) reverse((V).begin(), (V).end())
# define paired make_pair
# define PRINT(V) for(auto v : (V)) cout << v << " "
int main()
{
    int N; cin >> N;
    VLL A(N),B(N),C(N);
    rep(i,N){
        cin >> A[i];
    }
    sort(all(A));
    rep(i,N){
        cin >> B[i];
    }   
    sort(all(B));
    rep(i,N){
        cin >> C[i];
    }
    sort(all(C));
    ll ans=0;
    rep(i,N){
        auto one=lower_bound(all(A),B[i]);
        auto three=upper_bound(all(C),B[i]);
        ans+=(one-A.begin())*(C.end()-three);
    }
    cout << ans << endl;
}