Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

树状数组 + 离散化

Posted by zhouzp15 at 2017-01-20 14:38:38 on Problem 2299
看过题解之后总结需要注意的几个地方:

1. 虽然总体数据数量不过5e5,但数据的范围达到了1e9左右,这里树状数组维护了一种类似于bitmap的结构,1e9这么大的范围如果不离散化的话空间上肯定是不允许的;

2. 所以需要开一个数组(比如说叫做index[])进行离散化,index[i]含义是:如果原序列中,位于i的元素在有序序列中的位置是j,那么index[i] = j。初始化和求和的时候都需要用离散化之后的这个数组进行操作;

3. 一个长度为n的向量中逆序对的数量O(n^2),输出要用long long,如果用printf输出需要用%lld。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 5e5 + 5;
typedef long long LL;
struct Node { int val, pos; } a[N];
int tree[N], index[N], n;

bool cmp(const Node &x, const Node &y) { return x.val < y.val; }

#define lowbit(x) (x & -x)
void add(int idx) { while (idx <= n) tree[idx]++, idx += lowbit(idx); }
int sum(int idx) { int s = 0; while (idx > 0) s += tree[idx], idx -= lowbit(idx); return s; }

int main()
{
	while (scanf("%d", &n) == 1 && n)
	{
		memset(tree, 0, sizeof(tree));
		for (int i = 1; i <= n; i++) scanf("%d", &(a[i].val)), a[i].pos = i;
		sort(a + 1, a + n + 1, cmp);
		for (int i = 1; i <= n; i++) index[ a[i].pos ] = i;
		
		LL ans = 0;
		for (int i = 1; i <= n; i++) add(index[i]), ans += i - sum(index[i]);
		printf("%lld\n", ans);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator