Description
对于序列A，它的逆序对数定义为满足
i<j
i
<
j
，且
Ai>Aj
A
i
>
A
j
的数对
(i,j)
(
i
,
j
)
的个数。给
1
1
到nn的一个排列，按照某种顺序依次删除
m
m
<script type="math/tex" id="MathJax-Element-28">m</script>个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Solution
非主席树做法。
考虑在原本的位置、大小的基础上，将时间看做另一维，便是一个三维偏序的问题了。
直接CDQ两次即可。
Source
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<
int,
int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <
typename T>
inline bool chkmax(T &a, T b) {
return a < b ? a = b,
1 :
0; }
template <
typename T>
inline bool chkmin(T &a, T b) {
return b < a ? a = b,
1 :
0; }
inline int read()
{
register int _, __;
register char c_;
for (_ =
0, __ =
1, c_ = getchar(); c_ <
'0' || c_ >
'9'; c_ = getchar())
if (c_ ==
'-') __ = -
1;
for ( ; c_ >=
'0' && c_ <=
'9'; c_ = getchar()) _ = (_ <<
1) + (_ <<
3) + (c_ ^
48);
return _ * __;
}
inline void File()
{
#ifdef hany01
freopen(
"bzoj3295.in",
"r", stdin);
freopen(
"bzoj3295.out",
"w", stdout);
#endif
}
const int maxn =
100005;
struct Data {
int x, y, z, Ans, id; }A[maxn];
inline bool cmp1(
const Data &A,
const Data &B)
{
if (A.x != B.x)
return A.x < B.x;
if (A.y != B.y)
return A.y < B.y;
return A.z < B.z;
}
inline bool cmp2(
const Data &A,
const Data &B)
{
if (A.y != B.y)
return A.y < B.y;
return A.z < B.z;
}
int n, m, del[maxn], pos[maxn];
LL Ans[maxn];
struct BIT
{
int c[maxn];
#define lb(x) ((x) & -(x))
inline void update(
int x,
int dt) {
for ( ; x <= n; x += lb(x)) c[x] += dt; }
inline int query(
int x) {
int Ans =
0;
for ( ; x; x -= lb(x)) Ans += c[x];
return Ans; }
}bit;
inline void CDQ(
int l,
int r)
{
if (l == r)
return ;
int mid = (l + r) >>
1;
CDQ(l, mid), CDQ(mid +
1, r);
sort(A + l, A + mid +
1, cmp2), sort(A + mid +
1, A + r +
1, cmp2);
int x = l, y = mid +
1;
while (y <= r) {
while (x <= mid && A[x].y < A[y].y) bit.update(A[x].z,
1), ++ x;
A[y].Ans += bit.query(A[y].z -
1), ++ y;
}
For(i, l, x -
1) bit.update(A[i].z, -
1);
}
int main()
{
File();
n = read(), m = read();
For(i,
1, n)
A[i].z = n - read() +
1, A[i].x = i, A[i].id = i, pos[n - A[i].z +
1] = i;
For(i,
1, m) A[pos[del[i] = read()]].y = n - i +
1;
static int cntt =
0;
For(i,
1, n)
if (!A[i].y) A[i].y = ++ cntt;
CDQ(
1, n);
For(i,
1, n) A[i].x = n - A[i].x +
1, A[i].z = n - A[i].z +
1;
sort(A +
1, A +
1 + n, cmp1);
CDQ(
1, n);
For(i,
1, n) pos[A[i].z] = i;
For(i,
1, n)
if (A[i].y <= n - m) Ans[m +
1] += A[i].Ans;
Fordown(i, m,
1) Ans[i] = Ans[i +
1] + A[pos[del[i]]].Ans;
For(i,
1, m)
printf(
"%lld\n", Ans[i]);
return 0;
}
