BZOJ3295【CQOI2011】动态逆序对 < CDQ分治 >

Posted on Symbols count in article: 807 Reading time ≈ 3 mins.

Problem

【CQOI2011】动态逆序对

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

对于序列AA，它的逆序对数定义为满足i<ji<j，且Ai>AjA_i>A_j的数对(i,j)(i,j)的个数。
给11到nn的一个排列，按照某种顺序依次删除mm个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

Input

输入第一行包含两个整数nn和mm，即初始元素的个数和删除的元素个数。
以下nn行每行包含一个11到nn之间的正整数，即初始排列。
以下mm行每行一个正整数，依次为每次删除的元素。

Output

输出包含mm行，依次为删除每个元素之前，逆序对的个数。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 4
1
5
3
4
2
5
1
4
2

Sample Output

1
2
3
4
5
2
2
1

HINT

N≤105,  M≤5×104N\le10^5,\;M\le5\times10^4

标签：CDQ分治 树状数组 三维偏序

Solution

三维偏序，可上CDQ\mathrm{CDQ}分治。

首先将删除操作离线，倒着做变成插入，并给每个数编号(x,y,z)(x,y,z)分别表示其下标、数值、插入时间。需要计算每个元素插入后会多出多少个逆序对，即对于三元组(xi,yi,zi)(x_i,y_i,z_i)，有多少个j≠ij\ne i满足xj<xi,yj>yi,zj≤zix_j<x_i,y_j>y_i,z_j\le z_i或xj>xi,yj<yi,zj<zix_j>x_i,y_j<y_i,z_j<z_i。
两个三维偏序，做两次CDQ\mathrm{CDQ}分治后统计即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, pos[MAX_N+5], tr[MAX_N+5]; lnt ans[MAX_N+5];
struct node {int x, y, z, p, s;} a[MAX_N+5], b[MAX_N+5];
bool cmp1 (const node &a, const node &b) {return a.x < b.x;}
bool cmp2 (const node &a, const node &b) {return a.x > b.x;}
void inc(int p) {for (; p <= m+2; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= m+2; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
void CDQ1(int s, int t) {
    if (s == t) return; CDQ1(s, mid), CDQ1(mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        b[i] = (p1 <= mid && (p2 > t || a[p1].y > a[p2].y)) ? a[p1++] : a[p2++];
    for (int i = s; i <= t; i++) a[i] = b[i];
    for (int i = s; i <= t; i++)
        if (a[i].x <= mid) inc(a[i].z+1);
        else a[i].s += sum(a[i].z+1);
    for (int i = s; i <= t; i++)
        if (a[i].x <= mid) dec(a[i].z+1);
}
void CDQ2(int s, int t) {
    if (s == t) return; CDQ2(s, mid), CDQ2(mid+1, t);
    for (int i = s, p1 = s, p2 = mid+1; i <= t; i++)
        b[i] = (p1 <= mid && (p2 > t || a[p1].y < a[p2].y)) ? a[p1++] : a[p2++];
    for (int i = s; i <= t; i++) a[i] = b[i];
    for (int i = s; i <= t; i++)
        if (a[i].x >= n-mid+1) inc(a[i].z+2);
        else a[i].s += sum(a[i].z+1);
    for (int i = s; i <= t; i++)
        if (a[i].x >= n-mid+1) dec(a[i].z+2);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        a[i].x = i, read(a[i].y), pos[a[i].y] = i;
    for (int i = m, x; i; i--) read(x), a[pos[x]].z = i;
    sort(a+1, a+n+1, cmp1); CDQ1(1, n);
    sort(a+1, a+n+1, cmp2); CDQ2(1, n);
    for (int i = 1; i <= n; i++) ans[a[i].z] += a[i].s;
    for (int i = 1; i <= m; i++) ans[i] += ans[i-1];
    for (int i = m; i; i--) printf("%lld\n", ans[i]); return 0;
}