BZOJ3295: [Cqoi2011]动态逆序对（树状数组套主席树）

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

Sample Output

5
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=100010;
struct in{
    int l,r,sum;
}s[maxn*100];
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)>>1;
    if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);
    else add(s[Now].r,Mid+1,R,pos,v);
}
void Add(int x,int pos,int v)
{
    while(x<=N){
        add(rt[x],1,N,pos,v);
        x+=(-x)&x;
    }
}
int query(int Now,int L,int R,int l,int r)
{
    if(!Now) return 0;
    if(l<=L&&r>=R) return s[Now].sum;
    int Mid=(L+R)>>1,res=0;
    if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);
    if(r>Mid) res+=query(s[Now].r,Mid+1,R,l,r);
    return res;
}
int Query(int x,int L,int R)
{
    if(L>R) return 0;
    int res=0; while(x){
        res+=query(rt[x],1,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=0; while(x){ res+=num[x]; x-=(-x)&x;} return res;}
int main()
{
    scanf("%d%d",&N,&M);
    rep(i,1,N){
        scanf("%d",&a[i]); p[a[i]]=i;
        ans+=i-1-Sum(a[i]-1);
        Add(i,a[i],1); ADD(a[i],1);
    }
    rep(i,1,M){
        int pos; scanf("%d",&pos); pos=p[pos];
        printf("%lld
",ans);
        ans-=Query(pos-1,a[pos]+1,N);
        ans-=(Sum(a[pos]-1)-Query(pos-1,1,a[pos]-1));
        Add(pos,a[pos],-1);
        ADD(a[pos],-1);
    }
    return 0;
}