首页 > 代码库 > 【HDU1394】Minimum Inversion Number（线段树）

【HDU1394】Minimum Inversion Number（线段树）

2024-07-14 19:15:31   223人阅读

大意：n次操作原串查询逆序数，求出所有串中最小的逆序数。

求逆序数属于线段树的统计问题，建立空树，每次进行插点时进行一次query操作即可。n次操作可以套用结论：如果是0到n的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少a[i],而增加n-1-a[i]。

 

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 const int maxn = 5e3 + 10; 6 int sumv[maxn << 2]; 7  8 void PushUp (int rt) { 9     sumv[rt] = sumv[rt * 2] + sumv[rt * 2 +1];10 }11 12 void build (int l, int r, int rt) {13     sumv[rt] = 0;14     if (l == r) {15         return ;16     }17     int m = (l + r) / 2;18     build (l, m, rt * 2);19     build (m + 1, r, rt * 2 + 1);20 }21 22 void update (int p, int l, int r, int rt) {23     if (l == r) {24         sumv[rt] ++;25         return ;26     }27     int m = (l + r) / 2;28     if (p <= m) {29         update (p, l, m, rt * 2);30     }31     if (p > m) {32         update (p, m + 1, r, rt * 2 + 1);33     }34     PushUp (rt);35 }36 37 int query (int L, int R, int l, int r, int rt) {38     if (L <= l && r <= R) {39         return sumv[rt];40     }41     int m = (l + r) / 2;42     int ret = 0;43     if (L <= m) {44         ret += query (L, R, l, m, rt * 2);45     }46     if (R > m) {47         ret += query (L, R, m + 1, r, rt * 2 + 1);48     }49     return ret;50 }51 52 int x[maxn];53 54 int main () {55     int n;56     while (~scanf ("%d", &n)) {57         build (0, n - 1, 1);58         int sum = 0;59         for (int i = 0 ; i < n; ++ i) {60             scanf ("%d", &x[i]);61             sum += query (x[i], n - 1, 0, n - 1, 1);62             update (x[i], 0, n - 1, 1);63         }64         int res = sum;65         for (int i =  0; i < n; ++ i) {66             sum = sum + n - x[i] - 1 - x[i];67             res = min (res, sum);68         }69         printf ("%d\n", res);70     }71     return 0;72 }

 


联系
我们