Why Did the Cow Cross the Road III

Solución 1

Fácil con el BIT 2D offline mencionado en el módulo.

Complejidad temporal: $\mathcal{O}(N\log^2N)$

Complejidad espacial: $\mathcal{O}(N\log N)$


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
tcT > using PR = pair<T, T>;
 
// pairs
#define mp make_pair
#define f first
#define s second
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
 
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto &a : x)
 
const int MOD = 1e9 + 7;  // 998244353;
const int MX = 2e5 + 5;
const ll INF = 1e18;  // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
	                         // USACO updates ...
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
 
ll cdiv(ll a, ll b) {
	return a / b + ((a ^ b) > 0 && a % b);
}  // divide a by b rounded up
ll fdiv(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}  // divide a by b rounded down
 
tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }  // set a = min(a,b)
tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
tcTU > T fstTrue(T lo, T hi, U f) {
	hi++;
	assert(lo <= hi);  // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
tcTU > T lstTrue(T lo, T hi, U f) {
	lo--;
	assert(lo <= hi);  // assuming f is decreasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo + 1) / 2;
		f(mid) ? lo = mid : hi = mid - 1;
	}
	return lo;
}
tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
	sort(all(v));
	v.erase(unique(all(v)), end(v));
}
tcTU > void erase(T &t, const U &u) {  // don't erase
	auto it = t.find(u);
	assert(it != end(t));
	t.erase(it);
}  // element that doesn't exist from (multi)set
 
// INPUT
#define tcTUU tcT, class... U
tcT > void re(complex<T> &c);
tcTU > void re(pair<T, U> &p);
tcT > void re(V<T> &v);
tcT, size_t SZ > void re(AR<T, SZ> &a);
 
tcT > void re(T &x) { cin >> x; }
void re(db &d) {
	str t;
	re(t);
	d = stod(t);
}
void re(ld &d) {
	str t;
	re(t);
	d = stold(t);
}
tcTUU > void re(T &t, U &...u) {
	re(t);
	re(u...);
}
 
tcT > void re(complex<T> &c) {
	T a, b;
	re(a, b);
	c = {a, b};
}
tcTU > void re(pair<T, U> &p) { re(p.f, p.s); }
tcT > void re(V<T> &x) { trav(a, x) re(a); }
tcT, size_t SZ > void re(AR<T, SZ> &x) { trav(a, x) re(a); }
tcT > void rv(int n, V<T> &x) {
	x.rsz(n);
	re(x);
}
 
// TO_STRING
#define ts to_string
str ts(char c) { return str(1, c); }
str ts(const char *s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
#ifdef LOCAL
	return b ? "true" : "false";
#else
	return ts((int)b);
#endif
}
tcT > str ts(complex<T> c) {
	stringstream ss;
	ss << c;
	return ss.str();
}
str ts(V<bool> v) {
	str res = "{";
	F0R(i, sz(v)) res += char('0' + v[i]);
	res += "}";
	return res;
}
template <size_t SZ> str ts(bitset<SZ> b) {
	str res = "";
	F0R(i, SZ) res += char('0' + b[i]);
	return res;
}
tcTU > str ts(pair<T, U> p);
tcT > str ts(T v) {  // containers with begin(), end()
#ifdef LOCAL
	bool fst = 1;
	str res = "{";
	for (const auto &x : v) {
		if (!fst) res += ", ";
		fst = 0;
		res += ts(x);
	}
	res += "}";
	return res;
#else
	bool fst = 1;
	str res = "";
	for (const auto &x : v) {
		if (!fst) res += " ";
		fst = 0;
		res += ts(x);
	}
	return res;
 
#endif
}
tcTU > str ts(pair<T, U> p) {
#ifdef LOCAL
	return "(" + ts(p.f) + ", " + ts(p.s) + ")";
#else
	return ts(p.f) + " " + ts(p.s);
#endif
}
 
// OUTPUT
tcT > void pr(T x) { cout << ts(x); }
tcTUU > void pr(const T &t, const U &...u) {
	pr(t);
	pr(u...);
}
void ps() { pr("\n"); }  // print w/ spaces
tcTUU > void ps(const T &t, const U &...u) {
	pr(t);
	if (sizeof...(u)) pr(" ");
	ps(u...);
}
 
// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU > void DBG(const T &t, const U &...u) {
	cerr << ts(t);
	if (sizeof...(u)) cerr << ", ";
	DBG(u...);
}
#ifdef LOCAL  // compile with -DLOCAL, chk -> fake assert
#define dbg(...)                                                                       \
	cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...)                                                                       \
	if (!(__VA_ARGS__))                                                                \
		cerr << "Line(" << __LINE__ << ") -> function(" << __FUNCTION__                \
		     << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n",                   \
		    exit(0);
#else
#define dbg(...) 0
#define chk(...) 0
#endif
 
void setPrec() { cout << fixed << setprecision(15); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
// FILE I/O
void setIn(str s) { freopen(s.c_str(), "r", stdin); }
void setOut(str s) { freopen(s.c_str(), "w", stdout); }
void setIO(str s = "") {
	unsyncIO();
	setPrec();
	// cin.exceptions(cin.failbit);
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for USACO
}
 
/**
 * Description: point update and rectangle sum with offline 2D BIT.
 * For each of the points to be updated, $x\in (0,SZ)$ and $y\neq 0$.
 * Time: O(N\log^2 N)
 * Memory: O(N\log N)
 * Source: Own
 * Verification:
 * https://dmoj.ca/problem/occ19g4
 * http://www.usaco.org/index.php?page=viewproblem2&cpid=722 (753 ms)
 * http://www.usaco.org/index.php?page=viewproblem2&cpid=601 (679 ms)
 */
 
template <class T, int SZ> struct OffBIT2D {
	bool mode = 0;  // mode = 1 -> initialized
	vpi todo;       // locations of updates to process
	int cnt[SZ], st[SZ];
	vi val;
	vector<T> bit;  // store all BITs in single vector
	void init() {
		assert(!mode);
		mode = 1;
		int lst[SZ];
		F0R(i, SZ) lst[i] = cnt[i] = 0;
		sort(all(todo), [](const pi &a, const pi &b) { return a.s < b.s; });
		trav(t, todo) for (int x = t.f; x < SZ; x += x & -x) if (lst[x] != t.s)
		    lst[x] = t.s,
		    cnt[x]++;
		int sum = 0;
		F0R(i, SZ) lst[i] = 0, st[i] = (sum += cnt[i]);
		val.rsz(sum);
		bit.rsz(sum);
		reverse(all(todo));
		trav(t, todo) for (int x = t.f; x < SZ; x += x & -x) if (lst[x] != t.s)
		    lst[x] = t.s,
		    val[--st[x]] = t.s;
	}
	int rank(int y, int l, int r) {
		return ub(begin(val) + l, begin(val) + r, y) - begin(val) - l;
	}
	void UPD(int x, int y, T t) {
		for (y = rank(y, st[x], st[x] + cnt[x]); y <= cnt[x]; y += y & -y)
			bit[st[x] + y - 1] += t;
	}
	void upd(int x, int y, T t) {
		if (!mode) todo.pb({x, y});
		else
			for (; x < SZ; x += x & -x) UPD(x, y, t);
	}
	int QUERY(int x, int y) {
		T res = 0;
		for (y = rank(y, st[x], st[x] + cnt[x]); y; y -= y & -y)
			res += bit[st[x] + y - 1];
		return res;
	}
	T query(int x, int y) {
		assert(mode);
		T res = 0;
		for (; x; x -= x & -x) res += QUERY(x, y);
		return res;
	}
	T query(int xl, int xr, int yl, int yr) {
		return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) +
		       query(xl - 1, yl - 1);
	}
};
 
OffBIT2D<int, 100005> OB;
int N, K;
 
int main() {
	setIO("friendcross");
	re(N, K);
	vpi pos(N + 1);
	FOR(i, 1, N + 1) {
		int x;
		re(x);
		pos[x].f = i;
	}
	FOR(i, 1, N + 1) {
		int x;
		re(x);
		pos[x].s = i;
	}
	FOR(i, 1, N + 1) OB.upd(pos[i].f, pos[i].s, 1);
	OB.init();
	ll ans = 0;
	int ind = 1;
	FOR(i, 1, N + 1) {
		while (ind < i - K) {
			OB.upd(pos[ind].f, pos[ind].s, 1);
			++ind;
		}
		ans += OB.query(pos[i].f, N) + OB.query(N, pos[i].s) -
		       2 * OB.query(pos[i].f, pos[i].s);
		// add unfriendly crossing pairs with cow i and some cow < i
	}
	ps(ans);
}

Solución 2

Usar un Árbol de Segmentos + BIT (online) como se menciona en la solución de Mowing the Field . Se llegará a los límites de tiempo / memoria a menos que se optimice de forma apropiada …

Complejidad temporal: $\mathcal{O}(N\log^2N)$

Complejidad espacial: $\mathcal{O}(N\log^2 N)$

Mi solución (de hace un tiempo):


#include <fstream>
#include <iostream>
 
using namespace std;
 
typedef pair<int, int> pi;
 
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define F0R(i, a) for (int i = 0; i < a; i++)
 
#define f first
#define s second
 
int N, K, nex;
pi x[100001];
pair<int, pi> segbit[20000000];
long long ans = 0;
 
int getnode(int in, int b) {
	if (b == 0) {
		if (!segbit[in].s.f) segbit[in].s.f = nex++;
		return segbit[in].s.f;
	}
	if (!segbit[in].s.s) segbit[in].s.s = nex++;
	return segbit[in].s.s;
}
 
void update(int in, int left, int right, int ind) {
	segbit[in].f++;
	if (left == ind && right == ind) return;
	int mid = (left + right) / 2;
	if (mid >= ind) update(getnode(in, 0), left, mid, ind);
	else update(getnode(in, 1), mid + 1, right, ind);
}
 
int query(int ind, int left, int right, int high) {
	if (right <= high) return segbit[ind].f;
	int mid = (left + right) / 2, z = 0;
	if (segbit[ind].s.f) z += query(segbit[ind].s.f, left, mid, high);
	if (segbit[ind].s.s && mid + 1 <= high)
		z += query(segbit[ind].s.s, mid + 1, right, high);
	return z;
}
 
void updb(int num, int pos) {
	while (num <= N) {
		update(num, 1, N, pos);
		num += (num & -num);
	}
}
 
void queryb(int mnum, int mpo, int mult) {
	while (mnum) {
		ans += mult * query(mnum, 1, N, mpo);
		mnum -= (mnum & -mnum);
	}
}
 
void init() {
	ifstream cin("friendcross.in");
	cin >> N >> K;
	nex = N + 1;
	F0R(i, N) {
		int a;
		cin >> a;
		x[a].f = i + 1;
	}
	F0R(i, N) {
		int b;
		cin >> b;
		x[b].s = i + 1;
	}
}
 
int main() {
	ofstream cout("friendcross.out");
	init();
	for (int i = N; i > 0; --i) {
		int j = i + K + 1;
		if (j > N) continue;
		updb(x[j].f, x[j].s);
		queryb(N, x[i].s, 1);
		queryb(x[i].f, N, 1);
		queryb(x[i].f, x[i].s, -2);
	}
	cout << ans;
}

Solución 3

Después de generar la secuencia apropiada de actualizaciones y consultas, se puede aplicar divide y vencerás como se describe en el módulo.

Solución 4

Consideremos una versión más fácil; supongamos que solo queremos contar el número de pares que se cruzan (ignorando si las vacas son amigas o no). Para calcular el número de pares que se cruzan, podemos agregar las vacas del camino 1 en reversa, mientras contamos el número de vacas que se agregan antes en el camino 2. Podemos usar un Árbol de Fenwick (BIT) para contar esto. Esto toma $\mathcal O(N)$ de espacio y $\mathcal O(N\log N)$ de tiempo.

Para contar el número de cruces no amistosos, en lugar de llevar la cuenta de cada nodo del BIT, mantenemos un conjunto ordenado que representa las razas de las vacas. Para una raza $b$ , consultamos el número de razas en el rango $[1, b-k-1]$ y $[b+k+1, n]$ . Podemos usar un árbol de estadísticas de orden (Order Statistic Tree) en C++ para representar las razas. Como cada actualización toma $\log N$ operaciones, asignaría $\log N$ nodos en cada actualización, lo que resulta en $\mathcal O(N\log N)$ de espacio y $\mathcal O(N\log^2 N)$ de tiempo.

C++

Pasa con 1957ms en el caso de prueba 13.


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void setIO(string s = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (s.size()) {
		freopen((s + ".in").c_str(), "r", stdin);
		freopen((s + ".out").c_str(), "w", stdout);
	}
}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int N = 1e5 + 5;
int n, k, a[N], b[N];
 
template <class T> struct BIT {
 
	struct Node {
		Tree<int> t;
		void ins(int val) { t.insert(val); }
		T get(int x) {
			int a = t.order_of_key(max(0, x - k));
			int b = t.size() - t.order_of_key(min(x + k + 1, n + 1));
			return a + b;
		}
	};
	vector<Node> a;
 
	BIT() {}
	BIT(int n) { a.resize(n + 1); }
 
	T qry(int pos, int x) {
		T res = 0;
		for (int i = pos; i; i -= i & (-i)) res += a[i].get(x);
		return res;
	}
	void upd(int pos, int val) {
		for (int i = pos; i <= n; i += i & (-i)) a[i].ins(val);
	}
};
BIT<ll> bit;
 
int main() {
	setIO("friendcross");
 
	ll ans = 0;
	int x;
	scanf("%d%d", &n, &k);
	bit = BIT<ll>(n);
	for (int i = n; i >= 1; i--) { scanf("%d", &a[i]); }
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		b[x] = i;
	}
	for (int i = 1; i <= n; i++) {
		x = a[i];
		ans += bit.qry(b[x], x);
		bit.upd(b[x], x);
	}
	printf("%lld\n", ans);
}