Дан массив из n целых чисел (n <= 1e6) [a0, a1, a2, ... an-1] (a[i] <= 1e9) и несколько запросов. В каждом запросе задано 2 целых чисел l и r (0 <= l <= r <= n-1), и нам нужно вернуть количество каждого отдельного целого числа в этом диапазоне (l и r включительно).
Я могу только придумать решение грубой силы для перебора всего диапазона для каждого запроса.
d={}
for i in range(l, r+1):
if arr[i] not in d:
d[arr[i]]=0
d[arr[i]]+=1
Например:
Array is [1, 1, 2, 3, 1, 2, 1]
Query 1: l=0, r=6, Output: 4, 2, 3 (4 for 4 1's, 2, for 2 2's and 1 for 1 3)
Query 2: l=3, r=5, Output: 1, 1, 1
Изменить. Я придумал что-то подобное, но все же его сложность довольно высока. Я думаю, из-за этой операции вставки.
const ll N = 1e6+5;
ll arr[N];
unordered_map< ll, ll > tree[4 * N];
int n, q;
void build (ll node = 1, ll start = 1, ll end = n) {
if (start == end) {
tree[node][arr[start]] = 1;
return;
}
ll mid = (start + end) / 2;
build (2 * node, start, mid);
build (2 * node + 1, mid + 1, end);
for (auto& p : tree[2 * node]) {
ll x = p.ff;
ll y = p.ss;
tree[node][x] += y;
}
for (auto& p : tree[2 * node + 1]) {
ll x = p.ff;
ll y = p.ss;
tree[node][x] += y;
}
}
vector< ll > query (ll node, ll l, ll r, ll start = 1, ll end = n) {
vector< ll > ans;
if (end < l or start > r) return ans;
if (start >= l and end <= r) {
for (auto p : tree[node]) {
ans.push_back (p.ss);
}
return ans;
}
ll mid = (start + end) / 2;
vector< ll > b = query (2 * node, l, r, start, mid);
ans.insert (ans.end (), b.begin (), b.end ());
b = query (2 * node + 1, l, r, mid + 1, end);
ans.insert (ans.end (), b.begin (), b.end ());
return ans;
}
