codeforce div2 C 树状数组

http://codeforces.com/contest/362

题目大意：给你一个序列，用冒泡排序法让他变为非递减的序列最少需要几次。在冒泡交换之间，你有一个swap操作，该swap操作是交换任意两个数组元素的位置，问在该操作后，所再需要的冒泡交换次数是多少，并输出方案数

思路：树状数组维护一下区间序列，知道该区间内比他大的有几个就行了。然后暴力。

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const int maxn =  + ;

int tree[maxn], a[maxn];

int big[maxn][maxn], big2[maxn][maxn];

int n;

int lowbit(int x) {return x & -x;}

int sum(int x){

    int ans = ;

    for (int i = x; i > ; i -= lowbit(i)){

        ans += tree[i];

    }

    return ans;

}

void add(int x, int val){

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

        tree[i] += val;

    }

}

int main(){

    scanf("%d", &n);

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

        int u; scanf("%d", &u); u++;

        a[i] = u;

    }

    int tot = ;

    for (int i = n; i >= ; i--){

        tot += sum(a[i]);

        add(a[i], );

    }

    ///l->r的区间

///区间内比他大的

    for (int i = n; i > ; i--){

        memset(tree, , sizeof(tree));

        for (int j = n; j >= i;j--){///都取不到边界

            if (a[j] > a[i]) add(a[j], );

            big[i][j] = sum(n) - sum(a[i] - );

        }

    }

    ///r->l的区间

///区间内比他大的

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

        memset(tree, , sizeof(tree));

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

            if (a[j] > a[i]) add(a[j], );

            big2[i][j] = sum(n) - sum(a[i] - );

        }

    }

    int mintot = tot;

    int cnt = ;

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

        for (int j = i + ;  j <= n; j++){///right

            if (a[i] < a[j]) continue;

            int t1 =  * (big[i][i + ] - big[i][j]) - (j - (i + ));

            int t2 = j - (i + ) -  * (big2[j][j - ] - big2[j][i]);

            int tmp = tot + t1 + t2 - ;

            if (tmp < mintot) cnt = , mintot = tmp;

            else if (tmp == mintot) cnt++;

        }

    }

    printf("%d %d\n", mintot, cnt);

    return ;

}