POJ-2299 Ultra-QuickSort（用樹狀數組求逆序對數）

• 2020 年 2 月 24 日
• 筆記

ac程式碼

#include<iostream>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<bitset>  #include<cassert>  #include<cctype>  #include<cmath>  #include<cstdlib>  #include<ctime>  #include<deque>  #include<iomanip>  #include<list>  #include<map>  #include<queue>  #include<set>  #include<stack>  #include<vector>  #define mp make_pair  #define pi acos(-1)  #define pii pair<int, int>  #define pll pair<long long , long long>  #define ll long long  #define ld long double  #define MEMS(x) memset(x, -1, sizeof(x))  #define MEM(x) memset(x, 0, sizeof(x))  const int inf = 0x3f3f3f3f;  const int maxn = 500001;  using namespace std;  int n;  struct Intg  {      int data;      int pos;      bool operator<(const Intg num) const      {          return data < num.data;      }  }a[maxn];  int p[maxn], d[maxn];  int lowbit(int x)  {      return x & (-x);  }  void update(int x)  {      while(x <= maxn)      {          d[x]++;          x += lowbit(x);      }  }  int getsum(int x)  {      int ans = 0;      while(x)    //一定寫成這種形式，否則寫成for循環形式會導致超時      {          ans += d[x];          x -= lowbit(x);      }      return ans;  }  int main()  {  //    freopen("input.txt", "r", stdin);  //    freopen("output.txt", "w", stdout);      while(scanf("%d", &n) != EOF && n)      {          for(int i = 1; i <= n; i++)          {              scanf("%d", &a[i].data);              a[i].pos = i;          }          sort(a + 1, a + n + 1);          p[a[1].pos] = 1;          int idx = 1;          for(int i = 2; i <= n ; i++)          {              if(a[i].data == a[i-1].data)                  p[a[i].pos] = idx;              else                  p[a[i].pos] = ++idx;          }          ll ans = 0;          memset(d, 0, sizeof(d));          for(int i = 1; i <= n; i++)          {              update(p[i]);              ans += i - getsum(p[i]);          }          printf("%lldn", ans);      }  }