[bzoj 3289] Mato的文件管理

有一个可以在1单位时间内交换两个相邻数的排序程序. n个数的序列, q个询问, 问将[l,r]内的数排成升序最少需要交换多少次. (n,q≤5*10^4) 题目问的有点奇怪, 试一试能否转化为熟悉的对象. 排序 - 逆序对. 交换两个相邻的数至多使逆序对减少1, 所以至少交换逆序对的数目那么多次. 这个下界是可以达到的. 所以, 本题即为区间逆序对查询. 这里不等号是严格的.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
const int N = 5e4, M = 5e4;
int n, top, b[N], out[M], A[N], H[N], ans;

struct Query {
	int k, l, r;
	bool operator<(const Query& rhs) const
	{
		return b[l] < b[rhs.l] || (b[l] == b[rhs.l] && r < rhs.r);
	}
} Q[M];

void init()
{
	int sz = 1;
	while (sz * sz < n) ++sz;
	for (int i = 0, k = 0; k < n; ++i)
		Rep (j, 0, min(sz, n-k))
			b[k++] = i;
}

struct BIT {
	int x[N+1], sum;
	static int lowbit(int x) { return x & -x; }
	
	void add(int p, int v)
	{
		sum += v;
		while (p <= n) {
			x[p] += v;
			p += lowbit(p);
		}
	}

	int query(int p)
	{
		int ret = 0;
		while (p) {
			ret += x[p];
			p -= lowbit(p);
		}
		return ret;
	}
} T;

inline void add(int v, int t)
{
	ans += t ? T.sum - T.query(v) : T.query(v-1);
	T.add(v, 1);
}

inline void remove(int v, int t)
{
	T.add(v, -1);
	ans -= t ? T.sum - T.query(v) : T.query(v-1);
}

inline int id(int x)
{
	return lower_bound(H, H+top, x) - H + 1;
}

int main()
{
	int q;
	scanf("%d", &n);
	init();

	Rep (i, 0, n) {
		scanf("%d", &A[i]);
		H[top++] = A[i];
	}
	sort(H, H+top);
	Rep (i, 0, n)
		A[i] = id(A[i]);
	
	scanf("%d", &q);
	Rep (i, 0, q) {
		scanf("%d%d", &Q[i].l, &Q[i].r);
		--Q[i].l;
		--Q[i].r;
		Q[i].k = i;
	}
	sort(Q, Q+q);

	int l = Q[0].l, r = Q[0].l - 1;
	Rep (i, 0, q) {
		while (r < Q[i].r)
			add(A[++r], 1);
		while (l > Q[i].l)
			add(A[--l], 0);
		while (r > Q[i].r)
			remove(A[r--], 1);
		while (l < Q[i].l)
			remove(A[l++], 0);
		out[Q[i].k] = ans;
	}

	Rep (i, 0, q)
		printf("%d\n", out[i]);

	return 0;
}