BZOJ 3295: [Cqoi2011]动态逆序对 CDQ分治

3295: [Cqoi2011]动态逆序对

Description

对于序列A，它的逆序对数定义为满足i<j，且A_i>A_j的数对(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<=100000 M<=50000

Source

题解：

　　CDQ分治第一题

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e5+10, M = 1e3+20,inf = 2e9;

LL ans[N];
int n,m,c[N],mp[N];
struct ss{
    int t,x,y;
    bool operator < (const ss &r) const {
        return x == r.x? y < r.y : x < r.x;
    }
}a[N],t[N];
int cmp(ss s1,ss s2) {
    return s1.t==s2.t?s1.x < s2.x:s1.t<s2.t;
}
void add(int x,int cc) {
    for(int i = x; i <= n; i += i & (-i)) c[i] += cc;
}
int sum(int x) {
    int s = 0;
    for(int i = x; i; i -= i&(-i)) s += c[i];
    return s;
}
void cdq(int l,int r) {
    if(l == r) return ;
    int md = (l+r)>>1;
    cdq(l,md),cdq(md+1,r);
    int i = l, j = md+1,p = l;
    while(i<=md||j<=r) {
        if(j>r||(i<=md&&a[i] < a[j])) add(a[i].y,1),t[p++]=a[i++];
        else ans[a[j].t] += sum(n) - sum(a[j].y),t[p++]=a[j++];
    }
    for(int i = l; i <= md; ++i) add(a[i].y,-1);
    for(int i = l; i <= r; ++i) a[i] = t[i];
    for(int i = r; i >= l; --i) {
        if(a[i].t<=md) add(a[i].y,1);
        else ans[a[i].t] += sum(a[i].y);
    }
    for(int i = l; i <= r; ++i)
        if(a[i].t<=md) add(a[i].y,-1);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d",&x);
        a[i].t =  0;
        a[i].x =  i;
        a[i].y =  x;
        mp[x] = i;
    }
    int Tim = n;
    for(int i = 1; i <= m; ++i) {
        int x;
        scanf("%d",&x);
        a[mp[x]].t = Tim--;
    }
    for(int i = 1; i <= n; ++i) {
        if(!a[i].t) a[i].t = Tim--;
    }
    sort(a+1,a+n+1,cmp);
    cdq(1,n);
    for(int i = 1; i <= n; ++i) ans[i] += ans[i-1];
    for(int i = n; i >= n-m+1; i--) printf("%lld
",ans[i]);
    return 0;
}