首页 > 代码库 > 【HDU1394】Minimum Inversion Number(线段树)
【HDU1394】Minimum Inversion Number(线段树)
大意: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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。