Проблема состоит в том, чтобы посчитать количество значений меньше значения после индекса. Вот код, но я не могу понять, как двоичное индексированное дерево было использовано для этого?
#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
#define MOD 1000000007
#define MAXN 10
using namespace std;
typedef pair<int, int> ii;
int BIT[MAXN+1];
int a[MAXN+1];
vector< ii > temp;
int countSmallerRight[MAXN+1];
int read(int idx) {
int sum = 0;
while (idx > 0) {
sum += BIT[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(int idx, int val) {
while (idx <= MAXN) {
BIT[idx] += val;
idx += (idx & -idx);
}
}
int main(int argc, const char * argv[])
{
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &a[i]);
temp.push_back(ii(a[i], i));
}
sort(temp.begin(), temp.end());
countSmallerRight[temp[0].second] = 0;
update(1, 1);
update(temp[0].second, -1);
for (int i = 1; i < N; i++) {
countSmallerRight[temp[i].second] = read(temp[i].second);
update(1, 1);
update(temp[i].second, -1);
}
for (int i = 1; i <= N; i++) {
printf("%d,", countSmallerRight[i]);
}putchar('\n');return 0;}
Было бы полезно, если бы кто-то мог объяснить рабочий принцип кода.
понять БИТ этот это одна из лучших ссылок.
TC дает полное объяснение функций, которые вы использовали, но остальная часть — логика того, как его использовать.
Для базового понимания:
Задание: есть n куч, и в каждой куче изначально есть 1 камень, затем мы добавляем камни от u к v… найдите, сколько камней в данной куче.
решение с ответом на каждой итерации http://pastebin.com/9QJ589VR.
После того, как вы это поймете, попробуйте реализовать свой вопрос.
Других решений пока нет …