N<=100000 M<=50000
被精神污染搞得半死的我看到了这道题。突然感觉好开心啊，自己想出来了。
首先，静态逆序对求一遍，删除了一个数a，考虑这个数a对整体的影响。对于位置在a之前的所有数b，若b>a，答案就要减一，对于位置在a之后的所有数c，若c<a答案也要减一。换句话说，就是问区间1，i-1中有多少数比a[i]大，区间i+1，n中有多少数比a[i]小，直接上主席树就玩了。还有，修改的时候记得只减不加。
T-T没有过洛谷的数据（TLE一个点）但是bzoj过了，嚯嚯！
贴个代码。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<cmath> #define maxn 160000 using namespace std; int read() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f; } int lowbit(int x) {return x & -x;} int n, m, top, s[maxn], root[maxn], rank[maxn]; long long ans; struct tree { int l, r, sum; tree() : l(0), r(0), sum(0) {} }t[maxn * 60]; int getans(int x) { int sum = 0; for(int i = x; i; i -= lowbit(i)) sum += s[i]; return sum; } int update(int x) { for(int i = x;i <= n; i += lowbit(i)) ++s[i]; } void add_tree(int &cur_p, int pos, int add, int L, int R) { if(!cur_p) cur_p = ++top; t[cur_p].sum += add; if(L == R) return; int mid = L + R >> 1; if(pos <= mid) add_tree(t[cur_p].l, pos, add, L, mid); else add_tree(t[cur_p].r, pos, add, mid + 1, R); } void creat_tree(int p, int pos, int add) { for(int i = p;i <= n; i += lowbit(i)) add_tree(root[i], pos, add, 1, n); } void init() { n = read(); m = read(); for(int i = 1;i <= n; ++i) { int a = read(); rank[a] = i; ans += getans(n) - getans(a); update(a); creat_tree(i, a, 1); } } int get_sum(int p, int pos, int L, int R) { if(L == R) return t[p].sum; int mid = L + R >> 1; if(pos <= mid) return get_sum(t[p].l, pos, L, mid); else return t[t[p].l].sum + get_sum(t[p].r, pos, mid + 1, R); } int query(int p, int pos) { int sum = 0; for(int i = p; i; i -= lowbit(i)) sum += get_sum(root[i], pos, 1, n); return sum; } int ask_prefix(int x, int pos) { return query(pos, n) - query(pos, x); } int ask_suffix(int x, int pos) { return query(n, x) - query(pos, x); } void solve() { for(int i = 1;i <= m; ++i) { printf("%lld\n", ans); int x = read(), pos = rank[x]; ans -= ask_prefix(x, pos) + ask_suffix(x, pos); creat_tree(pos, x, -1); } } int main() { init(); solve(); return 0; } /* 10 9 1 4 6 7 8 5 9 10 2 3 7 5 2 3 1 8 9 10 28 25 21 16 11 11 11 11 11 4 */