/*
首先我们更改线段树叶子节点处存储的内容,将其更改为权值,并且记录对于一个权值x的个数。那么我们首先构建一棵空树,对于每次插入的数字x,我们查找x+1到max区间的数字存在的个数,并将这个个数加入答案,然后插入这个数字。最后输出答案就可以了。。
*/
#include < iostream > #include < cstdio > using namespace std;#define N 100010 int n;
struct node {
int l,
r;
long long v;
}
tr[40010 << 4];
void build(int k, int l, int r) {
tr[k].l = l;
tr[k].r = r;
if (tr[k].l == tr[k].r) return;
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
}
long long query(int k, int l, int r) {
if (tr[k].l >= l && tr[k].r <= r) return tr[k].v;
int mid = (tr[k].l + tr[k].r) >> 1;
long long res = 0;
if (l <= mid) res += query(k << 1, l, r);
if (r > mid) res += query(k << 1 | 1, l, r);
return res;
}
void Insert(int k, int l) {
if (tr[k].l == l && tr[k].r == tr[k].l) {
tr[k].v++;
return;
}
int mid = (tr[k].l + tr[k].r) >> 1;
if (l <= mid) Insert(k << 1, l);
if (l > mid) Insert(k << 1 | 1, l);
tr[k].v = tr[k << 1].v + tr[k << 1 | 1].v;
}
int main() {
scanf("%d", &n);
build(1, 1, N);
int x;
long long ans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
ans += query(1, x + 1, N);
Insert(1, x);
}
cout << ans;
return 0;
}
来源: http://www.bubuko.com/infodetail-2288858.html