Даны 3 массива a, b, c длины n(n <= 1e6). Массивы a, b, c являются перестановками(числа от 1 до n, без повторений). Необходимо найти количество пар (i, j), условие которых является: a[i] > a[j], b[i] > b[j], c[i] > c[j].
Ссылка для сдачи задачи: https://ejoi2022-practice.eolymp.io/
Представь что есть n точек с координатам (a_i, b_i, c_i)
И посмотри что значит условие
это означает что
Если мы рассмотрим параллелепипиды с концами в (0,0,0) и (a_i, b_i, c_i), то тогда если условие выполняется, то параллелепид j, полностью содержится в параллелепипиде i
?
Задача относительно тяжкая, но зато очень полезная для развития понимания сканлайна и структур данных.
Сведем задачу к более простой. Для этого отсортируем все по например a[i]-тым (можно и по b[i] или c[i], но это же неудобно). Теперь если так подумать, то пройдясь по массиву, который отсорчен по возрастанию, для каждого i все возможные подходящие j точно будут на префиксе. То есть задача свелась к нахождению таких j < i, что b[j] < b[i] и c[j] < c[i].
Ещё раз изменим взгляд на задачу. Если представить j как точки с координатами (b[j], c[j]), то количество пар для i - это количество точек внутри прямоугольника с координатами верхней правой точки (b[i], c[i]). Теперь обратимся к структурам данных. Чтобы решать новую задачу нам просто нужно уметь делать:
Тогда будем проверять для i подходящие пары точек, а потом сразу же добавлять точку i в нашу структуру данных, чтобы следующие элементы рассмотрели ее точно так же, как она рассмотрела все предыдущие ей. Такой процесс сведения задачи, когда все сильно упрощается сортировкой событий называется сканлайн.
Воспользуемся деревом Фенвика. Но только не будем хранить его в виде обычного массива, а в виде массива ordered_set-ов. Что это такое? Не важно, но он имеет все функции сета, при этом ещё может ответить “сколько элементов в сете меньше x?” за O(log(n)). Будем добавлять на позицию b[i], как в обычном Фенвике число c[i], это выглядит примерно так:
void add(int i){
for(int pos = b[i]; pos <= n; pos += (pos & -pos))
f[pos].insert(c[i]);
}
Отлично, мы добавили число в Фенвик, но как узнать сумму на прямоугольнике? Ну, поскольку мы добавили для всего суффикса b[i] точку c[i], то достаточно просто сделать то же самое что и в обычном гете в Фенвике, только теперь ещё надо учитывать что нам подходят лишь точки, у которых координата c меньше c[i], что мы делаем с помощью вышеупомянутой функции ordered_set-а. Это выглядит так:
int get(int i){
int res = 0;
for(int pos = b[i]; pos > 0; pos -= (pos & -pos))
res += f[pos].order_of_key(c[i]);
return res;
}
Если неясно, то в конце код выглядит так:
// отсортировать массивы по a[i]
long long ans = 0;
for(int i = 1; i <= n; i++)
ans += get(i), add(i);
cout << ans;
Но, не все так просто, ведь этот код получит МЛ или ТЛ на последней подзадаче из-за того, что ordered_set в STL реализован немного небрежно. Дальше нужно действовать своими руками и делать константные оптимизации.
Нужно избавиться от константы. Заметим интересную вещь: по сути все операции добавления/запроса к ordered_set можно обрабатывать оффлайн. Для понимания задумаемся о том, что на высоком уровне делает Фенвик: он просто делит запросы на log(n) индексов, к каждому из которых нужно отдельно обратиться и узнать его вклад в его общую сумму. Тогда сделаем именно это. Вместо того чтобы обращаться к элементу в цикле из get/upd мы будем сохранять в него информацию о самом запросе который затронул его. Выглядит это как-то так:
// f - массив векторов пар, который хранит все запросы, которые затронули соответстующий индекс
// если первое число в паре - 0, значит это был запрос на обновление
// если первое число в паре - 1, значит это был запрос на сумму
void add(int i){
for(int pos = b[i]; pos <= n; pos += (pos & -pos))
f[pos].pb(mp(0, c[i]));
}
void get(int i){
for(int pos = b[i]; pos > 0; pos -= (pos & -pos))
f[pos].pb(mp(1, c[i]));
}
Тогда позже мы просто сможем пройтись по всем индексам, ответить на запросы внутри них с помощью глобального Фенвика вместо ordered_set, и соответсвенно получить более быстрое решение.
Однако, все опять же не так просто. Поскольку выходит, что мое решение - запих, то придется оптимизировать еще сильнее. Не буду сильно углубляться в детали, так как это сложные вещи, в которых я сам не разбираются на адекватном уровне, но если в дереве Фенвика оставить искусственные “дырки” (то есть позиции, которые никогда не будут затронуты запросами), то можно его значительно ускорить.
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define speed \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define precision \
cout.precision(30); \
cerr.precision(10);
#define ll long long
#define ld long double
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
int n, a[1000005], b[1000005], c[1000005], d[1000005], f[2000005];
ll res;
vector<int> q[2000005];
inline constexpr int hole(int k) { return k + (k >> 10); }
void upd(int x, int y = 1) {
for (; x <= n; x += (x & -x)) f[hole(x)] += y;
}
void dpu(int x, int y) {
for (; x <= n; x += (x & -x)) q[hole(x)].pb(-y);
}
void get(int x) {
for (; x > 0; x -= (x & -x)) res += f[hole(x)];
}
void get(int x, int y) {
for (; x > 0; x -= (x & -x)) q[hole(x)].pb(y);
}
bool cmp(int x, int y) { return a[x] < a[y]; }
int main() {
speed;
precision;
// code
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
d[i] = i;
}
sort(d + 1, d + n + 1, cmp);
for (int i = 1; i <= n; i++) {
get(b[d[i]] - 1, c[d[i]] - 1);
dpu(b[d[i]], c[d[i]]);
}
for (int i = 0; i <= n; i++) {
for (auto x : q[i]) (x < 0) ? upd(-x) : get(x);
for (auto x : q[i]) if (x < 0) upd(-x, -1);
}
cout << res;
// endl
#ifndef ONLINE_JUDGE
cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
под ordered_set ты имеешь в виду это?
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
Мне кажется что можно использовать тот факт что одному b_i соответствует только одно c_i
Я пытался пихать O(nlog^2n). Но это слишком долго
Да, я как-то забыл в 5 утра упомянуть что я имею ввиду
Плохо пытался, у меня вышло 
Оказалось что эта задача уже была на МУИТ OPEN.
Ну и авторское решение на эту задачу оказалось за O(n * log(n))
Пусть пара (i, j) и пара (j, i) будет одним и тем же, очевидно что только одна пара из этих двух может быть правильной.
Давай обозначать пару (i, j) маской из трех битов:
000 (a_i < a_j, b_i < b_j, c_i < c_j)
001 (a_i < a_j, b_i < b_j, c_i > c_j)
011 (a_i < a_j, b_i > b_j, c_i > c_j)
010 (a_i < a_j, b_i > b_j, c_i < c_j)
Если a_i > a_j прост поменяем местами i, j, тк мы сказали что это одно и тоже. Теперь давай делать некоторые действия и смотреть как это влияет на ответ.
Давайте делать так построим массив TEMP_{a_i} = b_i и посчитаем кол-во инверсий в нём, и отнимем это от ответа, тогда посмотрим сколько раз мы учли пары определённого вида в ответе:
000 0
001 0
011 -1
010 -1
Теперь сделаем массив TEMP_{b_i} = c_i и посчитаем кол-во инверсий в нём, и отнимем это от ответа и посмотрим сколько раз мы учли пары определённого вида в ответе:
000 0
001 -1
011 -1
010 -2
Теперь сделаем массив TEMP_{a_i} = c_i и посчитаем кол-во инверсий в нём, и отнимем это от ответа и посмотрим сколько раз мы учли пары определённого вида в ответе:
000 0
001 -2
011 -2
010 -2
Заметим что все неправильные пары мы посчитали два раза, теперь давай просто добавим к ответ у все возможные пары в массиве умноженные на два(т.е. (n * (n - 1))
000 2
001 0
011 0
010 0
Теперь поделим ответ на два и получится ответ который от нас требовали.
000 1
001 0
011 0
010 0
(Решение мне подсказал Темирлан Сатылханов спасибо ему!)
