[国家集训队]排队

题目描述

思路

对于交换 $i , j$ 的数字，我们考虑交换这两个数字（记这两个数字分别为 $a,b$ ）对答案的贡献。

显然，对于区间 $[i+1,j-1]$ 中每一个大于 $a$ 的数字会产生 $+1$ 的贡献，每一个小于 $a$ 的数字会产生 $-1$ 的贡献，每一个小于 $b$ 的数字会产生 $+1$ 的贡献，每一个大于 $b$ 的数字会产生 $-1$ 的贡献。最后还有 $a$ 与 $b$ 是否为逆序对的贡献。

显然，我们需要求出区间中大（小）于一个数字的个数。这个问题可以使用树套树~~或暴力~~解决，但是在此处讲一种别致的分块。

对数列进行离散化，数的大小的值域为 $1 \sim n$ 。我们不妨在数列分块中在套上一个值域分块。记 Cnt1[x][y] 表示前 $x$ 块的数列中值域在第 $y$ 块出现的次数，记 Cnt2[x][y] 表示前 $x$ 块的数列中数字 $y$ ，记 Bel[i] 表示数字 $i$ 所对应的块，由于值域和块大小是同阶的，所以这个数组既可以表示数列对应的块，也可以表示数值对应的块。

一下的操作仅讨论查询小于一个数的个数，大于一个数字同理。

查询：设查询小于的数字为 $k$ ，块大小为 block_size。对于数列中的块外元素，暴力解决，时间复杂度 $O(\sqrt n)$ 。数列中的块内元素我们再此分为两类，第一类为完整值域中出现，即值域 Bel[0] $\sim$ Bek[k]-1，这个利用 Cnt1 前缀相减可以在 $O(\sqrt n)$ 的时间内算完；第二类为不在完整块内的，即数值 (Bel[k]-1)*block_size+1 $\sim k$ ，这个利用 Cnt2 前缀相减可以在 $O(\sqrt n)$ 的时间内算完。总时间复杂度为 $O(\sqrt n)$ 。

交换：将 Cnt1[][Bel[a]],Cnt1[][Bel[b]],Cnt2[][a],Cnt2[][a] 四个数组总后往前差分即可得到每一块的数，修改对应的值并维护然后做前缀和就好了。这里有个细微的优化，差分（前缀）只需从 Bel[j] 到 Bel[i] 就可以了。由于块的数量不超过根号，所以时间复杂度为 $O(\sqrt n)$ 。

显然，Cnt1 可以 $O(n)$ 预处理， Cnt2 可以 $O(n\sqrt n)$ 预处理。至此，我们就已经在 $O(n \sqrt n)$ 的时间复杂度内 AC。

这个思路来自于 [Ynoi2018] 未来日记的启发。

代码

#include <bits/stdc++.h>
using namespace std;

char gc() {
    static char now[1 << 20], *S, *T;
    if (T == S) {
        T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
        if (T == S) return EOF;
    }
    return *S++;
}
template <typename T>
void read(T &x) {
    x = 0;
    char c = gc();
    while (c < '0' || c > '9') c = gc();
    x = c - '0';
    while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void read(T &x, Args &...args) {
    read(x);
    read(args...);
}

const int MAXN = 20010;

int Num[MAXN] , Temp[MAXN] , N , M , Num2[MAXN] , l , r , Block;

long long Sum;

int Cnt1[600][600];
int Cnt2[600][MAXN];

int Left[600] , Right[600] , Bel[MAXN];

void Merge(int l1 , int r1 , int l2 , int r2) {
	int ToT = 0;
	while(l1 <= r1 && l2 <= r2) {
		if(Num[l1] <= Num[l2]) {
			Temp[++ToT] = Num[l1++];
		}
		else {
			Temp[++ToT] = Num[l2++];
			Sum += r1 - l1 + 1;
		}
	}
	while(l1 <= r1) Temp[++ToT] = Num[l1++];
	while(l2 <= r2) Temp[++ToT] = Num[l2++];
	
	for(int i = ToT , j = r2; i >= 1; i--, j--) {
        Num[j] = Temp[i];
    }
}

void MergeSort(int l , int r) {
	if(l < r) {
		int Mid = l + r >> 1;
		MergeSort(l , Mid);
		MergeSort(Mid + 1 , r);
		Merge(l , Mid , Mid + 1 , r);
	}
}

int Query1(int l , int r , int k) { //查找 < k 的数的个数 
	int Bel_R = Bel[r] , Bel_L = Bel[l];
	
	if(Bel_L == Bel_R) {
		int res = 0;
		
		for(int i = l; i <= r; i++) {
			if(Num2[i] < k) res++;
		}
		
		return res;
	}
	else {
		int res = 0;
		
		for(int i = l; i <= Right[Bel_L]; i++) {
			if(Num2[i] < k) res++;
		}
		
		for(int i = 0; i < Bel[k]; i++) {
			res += Cnt1[Bel_R - 1][i] - Cnt1[Bel_L][i];
		}
		for(int i = (Bel[k] - 1) * Block + 1; i < k; i++) {
			res += Cnt2[Bel_R - 1][i] - Cnt2[Bel_L][i];
		}
		
		for(int i = Left[Bel_R]; i <= r; i++) {
			if(Num2[i] < k) res++;
		}
		
		return res;
	}
}

int Query2(int l , int r , int k) { //查找 > k 的数的个数 
	int Bel_R = Bel[r] , Bel_L = Bel[l];
	
	if(Bel_L == Bel_R) {
		int res = 0;
		
		for(int i = l; i <= r; i++) {
			if(Num2[i] > k) res++;
		}
		
		return res;
	}
	else {
		int res = 0;
		
		for(int i = l; i <= Right[Bel_L]; i++) {
			if(Num2[i] > k) res++;
		}
		
		for(int i = Bel[N]; i > Bel[k]; i--) {
			res += Cnt1[Bel_R - 1][i] - Cnt1[Bel_L][i];
		}
		for(int i = min(Bel[k] * Block , 20000); i > k; i--) {
			res += Cnt2[Bel_R - 1][i] - Cnt2[Bel_L][i];
		}
		
		for(int i = Left[Bel_R]; i <= r; i++) {
			if(Num2[i] > k) res++;
		}
		
		return res;
	}
}

void Swap(int l , int r) {
	int x = Num2[l] , y = Num2[r];
	
	int Bel_R = Bel[r] , Bel_L = Bel[l];
	
	for(int i = Bel[N]; i >= Bel_L; i--) {
		Cnt1[i][Bel[x]] -= Cnt1[i - 1][Bel[x]];
		Cnt1[i][Bel[y]] -= Cnt1[i - 1][Bel[y]];
		Cnt2[i][x] -= Cnt2[i - 1][x];
		Cnt2[i][y] -= Cnt2[i - 1][y];
	}
	
	Cnt1[Bel_L][Bel[y]]++;
	Cnt1[Bel_L][Bel[x]]--;
	Cnt2[Bel_L][y]++;
	Cnt2[Bel_L][x]--;
	
	Cnt1[Bel_R][Bel[y]]--;
	Cnt1[Bel_R][Bel[x]]++;
	Cnt2[Bel_R][y]--;
	Cnt2[Bel_R][x]++;
	
	for(int i = Bel_L; i <= Bel[N]; i++) {
		Cnt1[i][Bel[x]] += Cnt1[i - 1][Bel[x]];
		Cnt1[i][Bel[y]] += Cnt1[i - 1][Bel[y]];
		Cnt2[i][x] += Cnt2[i - 1][x];
		Cnt2[i][y] += Cnt2[i - 1][y];
	}
	
	swap(Num2[l] , Num2[r]);
}

int main() {
	scanf("%d" ,&N);
	
	Block = sqrt(N);
	
	for(int i = 1; i <= N; i++) {
		scanf("%d" ,&Num[i]);
		Num2[i] = Num[i];
	}
	
	for(int i = 1; i <= 20000; i++) {
		Bel[i] = (i - 1) / Block + 1;
	}
	MergeSort(1 , N);
	
	int Size = unique(Num + 1 , Num + 1 + N) - Num - 1;
	
	for(int i = 1; i <= N; i++) {
		Num2[i] = lower_bound(Num + 1 , Num + 1 + Size , Num2[i]) - Num;
	}
	
	for(int i = 1; i <= Bel[N]; i++) {
		Left[i] = Right[i - 1] + 1;
		Right[i] = i * Block;
	}

	Right[Bel[N]] = N;
	
	for(int i = 1; i <= Bel[N]; i++) {
		for(int j = 1; j <= Bel[N]; j++) {
			Cnt1[i][j] = Cnt1[i - 1][j];
		}
		
		for(int j = 1; j <= N; j++) {
			Cnt2[i][j] = Cnt2[i - 1][j];
		}
		
		for(int j = Left[i]; j <= Right[i]; j++) {
			Cnt1[i][Bel[Num2[j]]]++;
			Cnt2[i][Num2[j]]++;
		}
	}
	
	scanf("%d" ,&M);
	
	printf("%lld\n" ,Sum);
	

	while(M--) {
		scanf("%d%d" ,&l ,&r);
		
		if(l > r) swap(l , r);
		
		Sum = Sum - Query1(l + 1 , r - 1 , Num2[l]) + Query2(l + 1 , r - 1 , Num2[l]) + Query1(l + 1 , r - 1 , Num2[r]) - Query2(l + 1 , r - 1 , Num2[r]);
		if(Num2[r] > Num2[l]) Sum++;
		if(Num2[r] < Num2[l]) Sum--;
		
		Swap(l , r);
		
		printf("%lld\n" ,Sum);
	}
	return 0;
}