【题目描述】
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
HINT
N<=
Source
【题解】
终于把要刷的su套su给A掉了。撒花~~~~~~
那么这道题该怎么做呢？
编号为i的数产生的逆序对数是1~i-1中比a[i]大的数的个数和i+1~n中比a[i]小的数的个数。
那么只要先求出整个序列的逆序对数，然后求出每个数产生的逆序对数。
显然发现：有些数已经被删去了，那么就用树状数组套线段su来维护删去的数就阔以辣！
然而窝一开始在直接维护还剩下的点（好写啊），然后被卡内存了。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=100010;
int n,m,i,x,cnt;
ll ans;
int a[M],pos[M],now[M],now1[M],t[M];
struct node{int l,r;ll w;}tree[M*50];
void insert(int x,int l,int r,int p,int t){
tree[p].w+=t;
if (l==r)return;
int mid=l+r>>1;
if (x<=mid){
if (!tree[p].l)tree[p].l=++cnt;
insert(x,l,mid,tree[p].l,t);
}else{
if (!tree[p].r)tree[p].r=++cnt;
insert(x,mid+1,r,tree[p].r,t);
}
}
void update(int x,int p,int q){
for (int i=x;i<=n;i+=i&-i)insert(p,1,n,i,q);
}
ll query(int x,int y,int l,int r,int p){
if (x==l&&y==r)return tree[p].w;
int mid=l+r>>1;
if (y<=mid)return query(x,y,l,mid,tree[p].l);
else if (x>mid)return query(x,y,mid+1,r,tree[p].r);
else return query(x,mid,l,mid,tree[p].l)+query(mid+1,y,mid+1,r,tree[p].r);
}
ll Query(int x,int y,int l,int r){
ll ans=0;
if (l>r)return 0;
for (int i=y;i;i-=i&-i)ans+=query(l,r,1,n,i);
for (int i=x-1;i;i-=i&-i)ans-=query(l,r,1,n,i);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
cnt=n;
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
pos[a[i]]=i;
for (int j=a[i];j;j-=j&-j)now[i]+=t[j];
now[i]=i-1-now[i];
ans+=now[i];
for (int j=a[i];j<=n;j+=j&-j)t[j]++;
}
memset(t,0,sizeof t);
for (i=n;i;i--){
for (int j=a[i];j;j-=j&-j)now1[i]+=t[j];
for (int j=a[i];j<=n;j+=j&-j)t[j]++;
}
for (i=1;i<=m;i++){
scanf("%d",&x);
int p=pos[x];
printf("%lld\n",ans);
ans-=now[p]+now1[p]-Query(1,p-1,x+1,n)-Query(p+1,n,1,x-1);
update(p,a[p],1);
}
}
评论 (0)
