《P3157 [CQOI2011] 动态逆序对》
题目描述
对于序列 a，它的逆序对数定义为集合
{(i,j)∣i<j∧ai>aj}
中的元素个数。
现在给出 1∼n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
输入格式
第一行包含两个整数 n 和 m，即初始元素的个数和删除的元素个数。
以下 n 行，每行包含一个 1∼n 之间的正整数，即初始排列。
接下来 m 行，每行一个正整数，依次为每次删除的元素。
输出格式
输出包含 m 行，依次为删除每个元素之前，逆序对的个数。
输入输出样例
输入 #1复制
5 4 1 5 3 4 2 5 1 4 2
输出 #1复制
5 2 2 1
说明/提示
【数据范围】
对于 100% 的数据，1≤n≤105，1≤m≤50000。
【样例解释】
删除每个元素之前的序列依次为：
1,5,3,4,21,3,4,23,4,23,2
代码实现：
#include <cstdio> #include <algorithm> #define lowbit(x) ((x)&(-x)) #define N 150010 #define ll long long using namespace std; struct nd{ int id, x, y; nd(){} nd(int a, int b, int c):id(a), x(b), y(c){} friend bool operator <(nd a, nd b){return (a.x==b.x)?a.y<b.y:a.x<b.x;} }A[N], tmp[N]; int n, m, pos[N]; ll res[N]; inline int rd(){ int x=0, f=1; char ch=getchar(); 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; } namespace bit{ int tr[N]; inline void upd(int x, int v){for(;x<=n;x+=lowbit(x))tr[x]+=v;} inline int qry(int x){int s=0;for(;x;x-=lowbit(x))s+=tr[x];return s;} inline void clr(int x){for(;x<=n&&tr[x];x+=lowbit(x))tr[x]=0;} } void cdq(int l, int r){ if(l==r) return; int mid=(l+r)>>1; cdq(l, mid), cdq(mid+1, r); for(int p=l, q=mid+1, cnt=l;p<=mid||q<=r;) if(q>r||p<=mid&&A[p]<A[q]) bit::upd(A[p].y, 1), tmp[cnt++]=A[p++]; else res[A[q].id]+=bit::qry(n)-bit::qry(A[q].y), tmp[cnt++]=A[q++]; for(int i=l;i<=mid;++i) bit::clr(A[i].y); for(int i=l;i<=r;++i) A[i]=tmp[i]; for(int i=r;i>=l;--i) if(A[i].id<=mid) bit::upd(A[i].y, 1); else res[A[i].id]+=bit::qry(A[i].y); for(int i=l;i<=r;++i) bit::clr(A[i].y); } bool cmp_id(nd a, nd b){return a.id<b.id;} int main(){ n=rd(), m=rd(); for(int i=1, x;i<=n;++i) pos[x=rd()]=i, A[i]=nd(0, i, x); int tim=n; for(int i=1, x;i<=m;++i) A[pos[rd()]].id=tim--; for(int i=1;i<=n;++i) if(!A[i].id) A[i].id=tim--; sort(A+1, A+n+1, cmp_id); cdq(1, n); for(int i=1;i<=n;++i) res[i]+=res[i-1]; for(int i=n;i>=n-m+1;--i) printf("%lld\n", res[i]); return 0; }