poj 2299 Ultra-QuickSort (树状数组+离散化)

这道题可以总结的地方不少。

1:对于一组乱序数列,每次只能交换相邻元素,达到有序交换的次数就是原数列中你逆序对的个数。

  cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。

2:原始数组a[i]和树状数组的t[i]的对应问题(???存在疑问。。。应该只是这道题,而不是一般规律!)

  这道题n是500000,如果直接开数组是可以开得下的,不需要离散化。**但是树状数组的下标对应的是原始数组的值!**也就是t[i]的下表最大可能为999,999,999 ! 显然存不下,需要离散化。

**3:学习了离散化的又一种写法。 **

/*************************************************************************
	> File Name: code/poj/2299.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月04日 星期二 12时27分32秒
 ************************************************************************/
 1#include<iostream>
 2#include<iomanip>
 3#include<cstdio>
 4#include<algorithm>
 5#include<cmath>
 6#include<cstring>
 7#include<string>
 8#include<map>
 9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)  
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=5E5+7;
25int n;
26int t[N];
27int ref[N];
1struct Q
2{
3    int val,id;
4}q[N];
 1bool cmp(Q a,Q b)
 2{
 3    if (a.val<b.val) return true;
 4    return false;
 5}
 6int lowbit( int x)
 7{
 8    return x&(-x);
 9}
10void update ( int x,int c)
11{
12    for ( int i = x ; i < N ; i = i + lowbit(i))
13    {
14	t[i] = t[i] + c;
15    }
16}
17LL Sum( int x)
18{
19    LL res = 0;
20    for ( int i = x; i >= 1 ; i = i - lowbit(i))
21    {
22	res = res + t[i];
23    }
24    return res;
25}
26int main()
27{
28    while (~scanf("%d",&n)&&n)
29    {
30	memset(t,0,sizeof(t));
31	for ( int i = 1 ; i  <= n ; i++ )
32	{
33	    scanf("%d",&q[i].val);  //离散化的时候相对大小不能打乱
34	    q[i].id = i;
35	}
36	sort(q+1,q+n+1,cmp);
37	for ( int i = 1 ; i <= n ; i++ )
38	{
39	    ref[q[i].id] = i;
40	}
41	LL ans = 0;
42	for ( int i = 1 ; i <= n ; i++ )
43	{
44	    update(ref[i],1);
45	    ans = ans + i-Sum(ref[i]);  
46	  //  cout<<"ans:"<<ans<<endl;
1	}
2	cout<<ans<<endl;
3    }
4	return 0;
5}