连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);
}
}
Historical Comments
Unknown friend at 2014-11-14T19:14:09
OTL