题面
题解
树套树（树状数组套动态开点线段树）
静态使用树状数组求逆序对就不多说了
用线段树代替树状数组，外面套树状数组统计每个点逆序对数量
设
\(t1[i]\)为\(i\)前面有多少个数比\(a[i]\)大
\(t2[i]\)为\(i\)后面有多少个数比\(a[i]\)小
那么当删除\(a[i]\)时
\(ans\) \(=\) \(ans-(t1[i]+t2[i])+\)\(i\)前面有多少个数比\(a[i]\)大且已经被删了+\(i\)后面有多少个数比\(a[i]\)小且已经被删了
用树套树维护就好了
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
inline int gi() {
RG int x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
return f ? -x : x;
}
const int N = 100010, M = 50010;
int t[N], n, m;
LL ans;
#define lowbit(x) (x&(-x));
inline int Tsum(int x) {
int s = 0;
while (x) s += t[x], x -= lowbit(x);
return s;
}
inline void Tadd(int x) {while (x <= n) t[x]++, x += lowbit(x);}
struct node {
int ls, rs, v;
}st[6000010];
int root[N];
int a[N], t1[N], t2[N], id[N], cnt;
void update(int &rt, int l, int r, int k) {
if (!rt) rt = ++cnt;
st[rt].v++;
if (l == r) return ;
int mid = (l + r) >> 1;
if (k <= mid) update(st[rt].ls, l, mid, k);
else update(st[rt].rs, mid+1, r, k);
}
int sum(int rt, int l, int r, int L, int R) {
if (!rt) return 0;
if (L <= l && r <= R) return st[rt].v;
int mid = (l + r) >> 1, s = 0;
if (L <= mid) s = sum(st[rt].ls, l, mid, L, R);
if (R > mid) s += sum(st[rt].rs, mid+1, r, L, R);
return s;
}
int query(int x, int l, int r) {
int s = 0;
if (l > r) return 0;
while (x) {
s += sum(root[x], 1, n, l, r);
x -= lowbit(x);
}
return s;
}
void insert(int x, int k) {
while (x <= n) {
update(root[x], 1, n, k);
x += lowbit(x);
}
return ;
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = gi(), m = gi();
for (int i = 1; i <= n; i++) a[i] = gi(), id[a[i]] = i;
for (int i = 1; i <= n; i++) {
t1[i] = Tsum(n)-Tsum(a[i]);
ans += t1[i];
Tadd(a[i]);
}
memset(t, 0, sizeof(t));
for (int i = n; i; i--) {
t2[i] = Tsum(a[i]-1);
Tadd(a[i]);
}
while (m--) {
int x = gi(), w = id[x];
printf("%lld\n", ans);
ans -= (t1[w]+t2[w]);
ans += query(w-1, x+1, n);
ans += query(n, 1, x-1)-query(w, 1, x-1);
insert(w, x);
}
return 0;
}