poj2299 Ultra-QuickSort ——线段树

May 23, 2013
POJ Data Structure

题目链接：http://poj.org/problem?id=2299 题目大意：　　给n个任意的数字，把他们排序，求最少的交换次数。题目思路：　　开始没想法。后来zjl一说才知道。原来就是求逆序数！每一个数字前面有多少比它小的，这个数字就至少要交换多少次。所以，只需要求这列数字的逆序数就可以！好神奇　　还有一个，就是每个数字的范围比较大，开始我还在想开数组貌似放不下，后来zjl说离散化……好吧，果然，我肿么没想到o(╯□╰)o感觉挺自然的想法啊…… 　　剩下的就是原来做过的题目了……甚至比原来做过的还简单　　最后一个问题就是，最后的结果应该是long long 的，稍微算一下就知道，最大值(2*10^11)超过了4个字节的整型范围(4 * 10^9)，long long 范围是(1*10^19)，所以输出要按照long long 输出……这个问题以后一定要注意，判断一下数字的范围！别傻乎乎地就用int……


//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 500000+10;
typedef struct node {
  int val, index;
  bool operator < (const node & other) const {
    return val < other.val;
  }
}node;
node in[MAX];
int nu[MAX], a[MAX<<2], n;
void solve();
void input() {
  while (~scanf("%d", &n) && n) {
    int i;
    for (i = 0; i < n; ++i) {
      scanf("%d", &in[i].val);
      in[i].index = i;
    }
    sort(in, in + n);
    for (i = 0; i < n; ++i) {
      nu[i] = in[i].index;
    }
    solve();
  }
}
void pushup(int rt) {
  a[rt] = a[rt<<1] + a[rt<<1|1];
}
void build(int l, int r, int rt) {
  if (l == r) {a[rt] = 0; return;}
  int m = (l + r) >> 1; build(lson); build(rson); pushup(rt);
}
int query(int L,int R, int l, int r, int rt) {
  if (L <= l && R >= r) {return a[rt];}
  int m = (l + r) >> 1, ret = 0;
  if (L <= m)  ret += query(L, R, lson);
  if (R > m) ret += query(L, R, rson);
  return ret;
}
void update(int p, int l, int r, int rt) {
  if (l == r) { a[rt]++; return;}
  int m = (l + r) >> 1;
  if (p <= m) update(p, lson); else update(p,rson);
  pushup(rt);
}
void solve() {
  int i; LL sum = 0;
  build(0, n-1, 1);
  for (i = 0; i < n; ++i) {
    sum += query(nu[i], n-1, 0, n-1, 1);
    update(nu[i], 0, n-1, 1);
  }
  printf("%lld\n", sum);
}
int main(void){
#ifdef LOCAL
  freopen("2299.in", "r", stdin);
#endif
  input();

  return 0;
}

复习了一下线段树……

Read more