【bzoj3295】[Cqoi2011]动态逆序对

题目描述：

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

输入：

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

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

样例输入：
5 4
1
5
3
4
2
5
1
4
2

样例输出：
5
2
2
1

题解：
动态逆序对，如果把逆序对当做二维偏序，动态的相当于多一维时间。于是就变成了三维偏序问题，然后就可以用cdq来做了。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#ifdef WIN32

	#define LL "%I64d"

#else

	#define LL "%lld"

#endif

#ifdef CT

	#define debug(...) printf(__VA_ARGS__)

	#define setfile()

#else

	#define debug(...)

	#define filename ""

	#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);

#endif

#define R register

#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)

#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)

char B[1 << 15], *S = B, *T = B;

inline int FastIn()

{

	R char ch; R int cnt = 0; R bool minus = 0;

	while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;

	ch == '-' ? minus = 1 : cnt = ch - '0';

	while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';

	return minus ? -cnt : cnt;

}

#define maxn 100010

#define maxm 50010

int pos[maxn], bit[maxn], last[maxn], now, n, m;

struct Event

{

	int pos, t, val;

	inline bool operator < (const Event &that) const

	{

		return t < that.t || (t == that.t && (pos < that.pos || (pos == that.pos && val < that.val)));

	}

}p[maxn], t[maxn];

int ans[maxn];

#define lowbit(_x) ((_x) & -(_x))

inline void add(R int x, R int val)

{

	for (; x <= n; x += lowbit(x))

	{

		if (last[x] != now)

			bit[x] = 0;

		last[x] = now;

		bit[x] += val;

	}

}

inline int query(R int x)

{

	R int ret = 0;

	for (; x ; x -= lowbit(x))

		if (last[x] == now)

			ret += bit[x];

	return ret;

}

void cdq(R int left, R int right)

{

	if (left == right) return ;

	R int mid = left + right >> 1;

	R int i, j, k;

	for (i = k = left, j = mid + 1; k <= right; ++k)

		t[p[k].t <= mid ? i++ : j++] = p[k];

	for (R int i = left; i <= right; ++i)

		p[i] = t[i];

	++now;

	for (R int i = left, j = mid + 1; j <= right; ++j)

	{

		for (; i <= mid && p[i].pos <= p[j].pos; ++i)

			add(p[i].val, 1);

		ans[p[j].t] += i - left - query(p[j].val);

	}

	++now;

	for (R int i = mid, j = right; j > mid; --j)

	{

		for (; i >= left && p[i].pos >= p[j].pos; --i)

			add(p[i].val, 1);

		ans[p[j].t] += query(p[j].val);

	}

	cdq(left, mid); cdq(mid + 1, right);

}

long long sum[maxn];

int main()

{

//	setfile();

	n = FastIn(); m = FastIn();

	for (R int i = 1; i <= n; ++i)

	{

		R int val = FastIn();

		p[i] = (Event) {i, 0, val}, pos[val] = i;

	}

	for (R int i = 1; i <= m; ++i)

		p[pos[FastIn()]].t = n - i + 1;

	R int mcnt = 0;

	for (R int i = 1; i <= n; ++i)

		if (!p[i].t) p[i].t = ++mcnt;

	cdq(1, n);

	for (R int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + ans[p[i].t];

	for (R int i = n; i > n - m; --i) printf("%lld\n",sum[i] );

	return 0;

}

/*

5 4

1 5 3 4 2

5

1

4

2

*/

巴特西

【bzoj3295】[Cqoi2011]动态逆序对

最新文章

热门文章