AtCoderBeginnerContest231 F問題500点 「Jealous Two」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 2 \times 10^5
気持ち
Eが難しかったので、Fを解きました。
もうこのさい、セグ木でいい感じに解けないか?という強い希望をもって問題に取り組みます。
考察するとソート+セグ木+座圧で解けそうなのでその気持で望みます。
解法
ひとまず、問題文が分かりづらいので以下のように変数に置き換えてみます。
青木くんと高橋くんを区別せずに$ i, j さんとします。
また、$ iさんがもらったプレゼントを $ p_iと表します。
また、$ iさんが感じるプレゼント$ xに対する価値を$ v_i(x)と書くことにします。
すると、けんかにならない条件は以下のとおりです。
$ i について $ v_i(p_i) \geq v_i(p_j)
$ jについて $ v_j(p_j) \geq v_j(p_i)
この式は、自分がもらったプレゼントと相手がもらったプレゼントであれば、自分が実際にもらったプレゼントのほうがうれしい! ことを表しています。
自分が switch をもらって、相手が ps1 をもらったとき、自分のほうがうれしいという状態です
(ps1 のほうが欲しい場合もありますが...)
ここで、$ N種類のプレゼントの順序が関係ないためソートしたい気持ちになります。(ソートしていい場合はとりあえずソートする癖をつけます) まず、$ A_iの昇順でソートして考えることにします。(この時点で、$ A_x \leq A_y $ (x \leq y) となっており、それと一致するように$ Bもペアソートされます)
このとき、高橋くんが$ y番目のプレゼントをもらったとすると$ i <yを満たすプレゼントについて、高橋くんがうれしい という条件を満たします。
例えば、以下の画像だと $ y =3の$ A_3 = 14を高橋くんがもらったとすると、$ 1, 2のプレゼントを青木くんがもらったとしても高橋くんとしては構いません。(高橋くんは青木くんに嫉妬しません。)
https://gyazo.com/e646bd39f213b11c9bd483eff774ef62
よって、$ y番目のプレゼントを高橋くんがもらったとすると、$ y以下のインデックスのプレゼントを青木くんにあげても高橋くんは嫉妬しません。
これで高橋くんが嫉妬しないという条件はクリアです。
あとは、青木くんについて考えればいいです。
また、$ 1, 2, ..., y番目のアイテムについてだけ考えればいいです。($ y + 1以上をあげようとすると高橋くんが嫉妬してしまうためです。)
$ y番目が高橋くんに渡るときに、$ 1, 2, ..., yのうち青木くんへのプレゼントとして渡していいのは、$ B_y以上の価値があるアイテムでなければなりません。
なぜならば、$ B_y以下の価値のプレゼントを $ 1, 2, \dots, yから選んであげてしまうと、$ y番目の$ B_yを青木くんは欲しがってしまうためです。
よって、$ 1, 2, \dots, yのうち $ B_y以上のアイテムの個数が、高橋くんに$ y番目のアイテムを上げるときの条件を満たす個数になります。
$ A_iの昇順に関して、$ B_iをペアソートしておきます。
そして、$ B_iの値を$ i = 1 \to Nの順序で、セグ木に追加します。($ B_iの位置を+1します)
あとは、各$ iを追加したあと、$ B_iから$ MAXまでの総和が条件を満たす数になります。
https://gyazo.com/129a030e8b4277cd80bf3d6d432a6ae3
ただし、$ A_i は$ 10^9まであるためあらかじめ座圧しておく必要があります。 計算量
$ O(N \log N)
新たな学び
反省点
コード
code: go
template<typename T>
pair<map<T, int>, map<int, T>> MAPPING(const vector<T> v) {
map<T, int> zip;
map<int, T> unzip;
for (int i = 0; i < v.size(); i++) zip[vi] = i; for (int i = 0; i < v.size(); i++) unzipi = vi; return make_pair(zip, unzip);
}
template<typename T>
struct SegmentTree {
private:
using Func = function<T(T, T)>;
int n;
vector<T> node;
T init_v;
Func func;
public:
SegmentTree(vector<T> a, Func _func, T _init_v) {
int sz = a.size();
n = 1;
init_v = _init_v;
func = _func;
while (n < sz) n *= 2;
node.resize(2 * n, init_v);
}
void update(int pos, T v) {
int k = pos + n - 1;
while (k > 0) {
k = (k - 1) / 2;
}
}
T get(int pos) {
int k = pos + n - 1;
}
T query(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r < 0) r = n;
if (r <= a || b <= l) return init_v;
if (a <= l && r <= b)return nodek; T lv = query(a, b, k * 2 + 1, l, (l + r) / 2);
T rv = query(a, b, k * 2 + 2, (l + r) / 2, r);
return func(lv, rv);
}
};
template<typename T>
vector<T> COMPRESS(vector<T> v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v;
}
constexpr int MAX = 800000;
int main() {
int N;
cin >> N;
VI A(N), B(N);
cin >> A >> B;
auto C = COMPRESS(B);
auto mapping = MAPPING(C);
auto zip = mapping.first;
VPII idx(N);
REP(i, N) idxi = MP(Ai, i); SORT(idx);
SegmentTree<LL> tree(VLL(MAX + 1), [](const LL a, const LL b) {
return a + b;
}, 0LL);
LL ans = 0;
for (int i = 0, j = 0; i < N; i = j) {
while (j < N and idxi.first == idxj.first)j++; for (int k = i; k < j; k++) {
tree.update(p, 1);
}
for (int k = i; k < j; k++) {
ans += tree.query(p, MAX);
}
}
cout << ans << endl;
return 0;
}