3295: [Cqoi2011]动态逆序对
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7465 Solved: 2662
[Submit][Status][Discuss]
Description
对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删
除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数
Input
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。
以下n行每行包含一个1到n之间的正整数，即初始排列。
以下m行每行一个正整数，依次为每次删除的元素。
N<=100000 M<=50000
Output
输出包含m行，依次为删除每个元素之前，逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
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)。
2
2
1
样例解释
(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。
思路：先求出总的逆序对数，然后对于每次的删数，我就减去这个位置前面比它大的个数以及后面比它小的个数。
注意这里删去的是元素，不是给的下标，由于没看题，我WA了好多次。
当然，也不难想到用CDQ分治去做。 我个人习惯写主席树。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct in{
int l,r,sum;
}s[maxn*];
int a[maxn],rt[maxn],N,M,cnt; ll ans;
void add(int &Now,int L,int R,int pos,int v)
{
if(!Now) Now=++cnt; s[Now].sum+=v;
if(L==R) return ;int Mid=(L+R)>>;
if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);
else add(s[Now].r,Mid+,R,pos,v);
}
void Add(int x,int pos,int v)
{
while(x<=N){
add(rt[x],,N,pos,v);
x+=(-x)&x;
}
}
int query(int Now,int L,int R,int l,int r)
{
if(!Now) return ;
if(l<=L&&r>=R) return s[Now].sum;
int Mid=(L+R)>>,res=;
if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);
if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);
return res;
}
int Query(int x,int L,int R)
{
if(L>R) return ;
int res=; while(x){
res+=query(rt[x],,N,L,R);
x-=(-x)&x;
} return res;
}
int num[maxn],p[maxn];
void ADD(int x,int v){ while(x<=N){ num[x]+=v; x+=(-x)&x; }}
int Sum(int x){ int res=; while(x){ res+=num[x]; x-=(-x)&x;} return res;}
int main()
{
scanf("%d%d",&N,&M);
rep(i,,N){
scanf("%d",&a[i]); p[a[i]]=i;
ans+=i--Sum(a[i]-);
Add(i,a[i],); ADD(a[i],);
}
rep(i,,M){
int pos; scanf("%d",&pos); pos=p[pos];
printf("%lld\n",ans);
ans-=Query(pos-,a[pos]+,N);
ans-=(Sum(a[pos]-)-Query(pos-,,a[pos]-));
Add(pos,a[pos],-);
ADD(a[pos],-);
}
return ;
}