laekov

连yjq都会做，简直是水暴了。

#include <cstdio>

#include <cstring>

#include <algorithm>

 

usingnamespacestd;

 

constintmaxn = 20009;

 

intn, m, a[maxn], t[maxn], *r[maxn], s;

 

intbtQry(int* t, intp) {

    ints = 0;

    while(p)

        s += t[p], p -= (p & -p);

    returns;

}

 

voidbtChg(int* t, intp, intv) {

    while(p < maxn)

        t[p] += v, p += (p & -p);

}

 

inlineboolcmpP(constint* a, constint* b) {

    return*a < *b;

}

 

intmain() {

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

#endif

 

    scanf("%d", &n);

    s = 0;

    for(inti = 1; i <= n; ++ i)

        scanf("%d", a + i), r[i - 1] = a + i;

    sort(r, r + n, cmpP);

    for(inti = 0, l = *r[0] - 1, v = 0; i < n; ++ i)

        if(*r[i] == l)

            *r[i] = v;

        else

            l = *r[i], *r[i] = ++ v;

    for(inti = 1; i <= n; ++ i) {

        s += i - btQry(t, a[i]) - 1;

        btChg(t, a[i], 1);

    }

    printf("%d\n", s);

    scanf("%d", &m);

    while(m --) {

        intl, r;

        scanf("%d%d", &l, &r);

        if(l > r)

            swap(l, r);

        for(inti = l + 1; i < r; ++ i) {

            if(a[i] > a[r])

                -- s;

            elseif(a[i] < a[r])

                ++ s;

            if(a[i] > a[l])

                ++ s;

            elseif(a[i] < a[l])

                -- s;

        }

        if(a[l] > a[r])

            -- s;

        elseif(a[l] < a[r])

            ++ s;

        swap(a[l], a[r]);

        printf("%d\n", s);

    }

}