W jaki sposób użyć drzewa przedziałowego?

Question

Siemka, mam pewiem problem z zadaniem >LINK<. Nie wiem w jaki sposób użyć drzewa przedziałowego w tym zadaniu. Metoda iteracyjna nie daje rady, gdyż czas jest przekraczany i to znacząco (sędzia przyznaje tylko 5% za to zadanie).
Tutaj mój kod: >LINK<, a tutaj wyniki: >LINK<.

Jeśli chodzi o drzewa przedziałowe to je akurat umiem bardzo dobrze; umiem odczytywać min, max, sumę, iloczyn itd. na przedziałach, natomiast nie mogę wpaść na pomysł jak użyć drzewa przedziałowego w tym konkretnym zadaniu. Prosiłbym o wytłumaczenie (krótkie jeśli nie chcecie się rozpisywać) jak użyć tej struktury w tym problemie. Dzięki z góry za wszystkie komentarze i odpowiedzi :D

Answer 1

Możesz przejść od końca tablicy do początku. Jeśli na i-tej pozycji w tablicy znajduje się wartośc a_i to dodajesz na przedziale [3, a_i) liczbę 1. Teraz drzewo przedziałowe dla danego sufiksu, dla każdej wartości x pamięta ile jest wartości y > x w tym sufiksie. Czyli podczas tego przechodzenia od końca tablicy do początku dodajesz do wyniku sume z [a_i+1, max]

Comments

nie bardzo rozumiem twojego rozwiązania, tzn. zwizualizowałem sobie drzewo i dla wartości z testu przykładowego (tj. 1 3 4 3 7 3) wygląda ono mniej więcej tak (uste pola oznaczają wartość 0):

ale z twojego wywodu:

podczas tego przechodzenia od końca tablicy do początku dodajesz do wyniku sume z [a_i+1, max]

nie bardzo rozumiem co to znaczy max. Mógłbyś bardziej szczegółowo objaśnić o co chodzi w tym rozwiązaniu?

---

Chodzi o to, że jak iterujemy się po tablicy od końca i jesteśmy na wartości a_i to liczymy ile jest takich trójek (i, j, k), że i < j < k i a_i < a_j < a_k. Ale skoro drzewo przedziałowe pamięta dla każdej wartosci x ile jest takich y (które wystąpiły w tablicy na pozycjach i+1...n), że y > x to wystarczy policzyć sume na przedziale [a_i+1, MAX_INT] (MAX_INT mozna zastpąić innym górnym ograniczeniem na wartości a_i). Wtedy jakby utożsamiamy x z a_j oraz y z a_k

---

Ewentualnie innym sposobem (pewnie prostszym) na rozwiązanie tego zadania jest po prostu trzymanie 2 drzew przedziałowych, jedno które zlicza wartości na prefiksie i drugie które zlicza na sufiksie. Wtedy jak na pozycji i jest wartość a_i to liczysz ile jest mniejszych od a_i na prefiksie [0, i-1] i mnożysz z ilością większych na sufiksie [i+1, n]

---

zrobilem tak:

• przeskalowalem tablice, zeby wartosci byly [1, 1e6] w najgorszym przypadku
• zrobilem dwie tablice lew[] i pra[], gdzie lew[i] oznacza ile jest wartosci na lewo od indeksu i mniejszych od b[i] (b[i] to przeskalowane a[i]). pra[] analogicznie, tylko po prawo i wieksze

Calosc wyglada mniej wiecej tak i daje 100%. Dzieki za pomoc :D

#include <iostream>
#include <algorithm>

using namespace std;

struct Liczba {
	int war, idx;

	bool operator < (const Liczba &liczba) const {
		if (war == liczba.war)
			return (idx < liczba.idx);
		return (war < liczba.war);
	}
};

Liczba a[100001];
int n, q = 2, j = 1, b[100001];
int lew[100001], pra[100001];
int tree[300001];

void upd(int v) {
	v += q;
	while (v >= 1) {
		tree[v] ++;
		v = v >> 1;
	}
}

int sum(int l, int p) {
	l = l + q - 1;
	p += q + 1;

	int suma = 0;
	while (l / 2 != p / 2) {
		if (l % 2 == 0)
			suma += tree[l + 1];
		if (p % 2 == 1)
			suma += tree[p - 1];

		l /= 2;
		p /= 2;
	}
	return suma;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].war;
		a[i].idx = i;
	}

	sort(a + 1, a + n + 1);

	// SKALOWANIE
	b[a[1].idx] = j;
	for (int i = 2; i <= n; i ++) {
		if (a[i].war == a[i - 1].war)
			b[a[i].idx] = j;
		else
			b[a[i].idx] = ++j;
	}

	while (q < n)
		q = q << 1;
	q --;

	for (int i = 1; i <= n; i ++) {
		lew[i] = sum(1, b[i] - 1);
		upd(b[i]);
	}

	for (int i = 1; i <= q + j; i ++)
		tree[i] = 0;

	for (int i = n; i >= 1; i --) {
		pra[i] = sum(b[i] + 1, j);
		upd(b[i]);
	}

	long long wy = 0;
	for (int i = 1; i <= n; i ++)
		wy += (long long)lew[i] * pra[i];
	cout << wy;
}