Dynamic Inversion

#define MAXN 200005
int N, M, DEL;
int ST[20][MAXN], BIT[20][MAXN];
int MP[MAXN];
long long invPair;
void modifySum(int BIT[], int x, int v, int L) {
while (x <= L) {
BIT[x] += v;
x += x & (-x);
}
}
int querySUM(int BIT[], int x) {
int res = 0;
while (x) {
res += BIT[x];
x -= x & (-x);
}

return res;
}
void buildST(int l, int r, int dep) {
for (int i = l; i <= r; ++i) {
ST[dep][i] = ST[dep - 1][i], BIT[dep][i] = 0;
if (l >= r) return;
int m = (l + r) / 2;
buildST(l, m, dep + 1);
buildST(m + 1, r, dep + 1);
sort(ST[dep] + l, ST[dep] + r + 1);
}
void queryPrefix(int l, int r, int dep, int x, int y, int val) {
if (x <= l && r <= y) {
int pos = upper_bound(ST[dep] + 1, ST[dep] + r + 1, val) - ST[dep];
int pre = querySUM(BIT[dep] + l - 1, pos - 1);
invPair -= (r - pos + 1) - (querySUM(BIT[dep] + l - 1, r - l + 1) - pre);
return;
}
if (l >= r) return; int m = (l + r) / 2;
if (x <= m) queryPrefix(l, m, dep + 1, x, y, val);
if (y > m) queryPrefix(m + 1, r, dep + 1, x, y, val);
}
void querySuffix(int l, int r, int dep, int x, int y, int val) {
if (x <= l && r <= y) {
int pos = upper_bound(ST[dep] + l, ST[dep] + r + 1, val) - ST[dep];
int pre = querySUM(BIT[dep] + l - 1, pos - 1);
invPair -= (pos - l) - pre;
}
if (l >= r) return; int m = (l + r) / 2;
if (x <= m) querySuffix(l, m, dep + 1, x, y, val);
if (y > m) querySuffix(m + 1, r, dep + 1, x, y, val);
}
void update(int l, int r, int dep, int x, int val) {
if (l == r) {
modifySUM(BIT[dep] + l - 1, 1, 1, r - l + 1);
return;
}
if (l >= r) return; int m = (l + r) / 2;
if (x <= m) update(l, m, dep + 1, x, val);
else update(m + 1, r, dep + 1, x, val);
int pos = lower_bound(ST[dep] + 1, ST[dep] + r + 1, val) - ST[dep];
modifySUM(BIT[dep] + l - 1, pos - l + 1, 1, r - l + 1);
}
int main() {
while (scanf("%d %d", &M, &N) == 2) {
invPair = 0;
for (int i = 0; i <= N; ++i) BIT[0][i] = 0;
for (int i = 0; i <= N; ++i) {
scanf("%d", &ST[0][i]);
MP[ST[0][i]] = i;
invPair += i - 1 - querySUM(BIT[0], ST[0][i]);
modifySUM(BIT[0], ST[0][i], 1, N);
}
buildST(1, N, 1);
while (M--) {
scanf("%d", &DEL);
printf("%lld\n", invPair);
queryPrefix(1, N, 1, 1, MP[DEL] - 1, DEL);
querySuffix(1, N, 1, MP[DEL] + 1, N, DEL);
update(1, N, 1, MP[DEL], DEL);
}
}
return 0;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store