Gym102082 G-What Goes Up Must Come Down(树状数组）

Several cards with numbers printed on them are lined up on the table.

We’d like to change their order so that first some are in non-decreasing order of the numbers on them, and the rest are in non-increasing order. For example, (1, 2, 3, 2, 1), (1, 1, 3, 4, 5, 9, 2), and (5, 3, 1) are acceptable orders, but (8, 7, 9) and (5, 3, 5, 3) are not.

To put it formally, with n the number of cards and bi the number printed on the card at the i-th position (1 ≤ i ≤ n) after reordering, there should exist k ∈ {1, . . . , n} such that (bi ≤ bi+1 ∀i ∈ {1, . . . , k − 1}) and (bi ≥ bi+1 ∀i ∈ {k, . . . , n − 1}) hold.

For reordering, the only operation allowed at a time is to swap the positions of an adjacent card pair. We want to know the minimum number of swaps required to complete the reorder.

Input

The input consists of a single test case of the following format. n a1 . . . an An integer n in the first line is the number of cards (1 ≤ n ≤ 100 000). Integers a1 through an in the second line are the numbers printed on the cards, in the order of their original positions (1 ≤ ai ≤ 100 000).

Output

Output in a line the minimum number of swaps required to reorder the cards as specified.

Sample Input 1

1 7 3 1 4 1 5 9 2

Sample Output

题意：

相邻的数字交换，求交换次数，使原数组变成前半部分为非降序列，后半部分为非升序列。

思路：

较小的必定在较大的外层，所以可以先把较小的数字移到外层。

移动到最外层的步数要O1算出，计算方法就是用树状数组记录中间已经被移走的数字个数，移到最边上的时候忽视被移走的数字就行了。

对于某一个确定的数字x，要算出4个值，最左边的x移到最左边的步数，移到最右边的步数，最右边的x移到最右边的步数，移到最左边的步数。这四个值的最小值取到哪里（左边的x或者右边的x），就把这个数移走。并更新树状数组。

代码（队友写的）

#include <bits/stdc++.h>

#define eps 1e-8

#define INF 0x3f3f3f3f

#define PI acos(-1)

#define lson l,mid,rt<<1

#define rson mid+1,r,(rt<<1)+1

#define CLR(x,y) memset((x),y,sizeof(x))

#define fuck(x) cerr << #x << "=" << x << endl

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int seed = ;

const int maxn = 1e5 + ;

const int mod = 1e9 + ;

int bit[maxn];

int n;

int a[maxn];

int lowbit(int i) {

    return i & -i;

}

void add(int i, int x) {

    while (i <= ) {

        bit[i] += x;

        i += lowbit(i);

    }

}

int sum(int i) {

    int num = ;

    while (i) {

        num += bit[i];

        i -= lowbit(i);

    }

    return num;

}

vector<int>v[maxn];

int main() {

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    for (int i = ; i <= n; i++) {

        v[a[i]].push_back(i);

    }

    ll ans = ;

    for (int k = ; k <= ; k++) {

        int i = , j = v[k].size() - ;

        while (i <= j) {

            int t1 = v[k][i] - sum(v[k][i]) - ;

            int t2 = n - v[k][i] - (sum() - sum(v[k][i]));

            int t3 = v[k][j] - sum(v[k][j]) - ;

            int t4 = n - v[k][j] - (sum() - sum(v[k][j]));

            int MIN1 = min(t1, t2);

            int MIN2 = min(t3, t4);

            if (MIN1 < MIN2) {

                add(v[k][i], );

                i++;

            } else {

                add(v[k][j], );

                j--;

            }

//            fuck();

//            int MIN=min(MIN);

            ans += min(MIN1, MIN2);

        }

    }

    printf("%lld\n", ans);

    return ;

}

巴特西

Gym102082 G-What Goes Up Must Come Down(树状数组）

最新文章

热门文章