Luogu P5047 Yuno loves sqrt technology II

题意

给定一个长度为 \(n\) 的序列 \(a\)。

有 \(m\) 次询问：查询区间 \([l,r]\) 中的逆序对数。

数据范围与约定

\(1 \le n,m \le 10^5\)，\(0 \le a_i \le 10^9\)。

题解

看到区间问题，先思考线段树。发现用线段树没法合并两个区间的信息。所以考虑分块。分块确实能做，但是这题卡空间，把分块给 ban 了。于是考虑能不能把询问差分成 \([1,r]-[1,l-1]\) 的形式。发现也拆不开。 那就考虑莫队。

莫队直接做很容易，可以用 \(O(n\sqrt{m}logn)\) 的时间复杂度解决。太慢了，而且莫队不像分块，不能把这个 \(logn\) 放到根号内。

以 while (query[i].l < l) 为例。假设移动前区间为 \([l,r]\)，移动后区间为 \([l',r]\)，其中 \(l'=l-1\)。

左指针向左移动，区间被扩大了，多增加了一个元素 \(a_{l'}\)。其对当前询问产生的贡献为 \([l,r]\) 中小于 \(a_{l'}\) 的数的个数。

普通的莫队，这里会维护一个全局的平衡树或者树状数组或者别的数据结构，用 \(O(logn)\) 的时间复杂度内求出这个贡献。这是没办法继续优化的，所以考虑这个地方还有没有别的手段。

为了方便，我们令 \(cnt_{[l,r],lower,x}\) 表示区间 \([l,r]\) 中小于 \(x\) 的数的个数。

差分后发现，\(cnt_{[l,r],lower,a_{l'}}=cnt_{[l,n],lower,a_{l'}}-cnt_{[r+1,n],lower,a_{l'}}\)。

并且其中 \(cnt_{[l,n],lower,a_{l'}}=cnt_{[l',n],lower,a_{l'}}\)。因为要求的是小于，所以自己并不会对自己做出贡献。

所以代入进去就变成：\(cnt_{[l,r],lower,a_{l'}}=cnt_{[l',n],lower,a_{l'}}-cnt_{[r+1,n],lower,a_{l'}}\)。

观察这个式子，我们发现，\(cnt_{[l',n],lower,a_{l'}}\) 非常的好求，从后往前扫一遍预处理一下就行了，复杂度 \(O(nlogn)\)，每次查询都可以 \(O(1)\) 回答。

但是 \(cnt_{[r+1,n],lower,a_{l'}}\) 不太好求，考虑到莫队有 \(O(n\sqrt{m})\) 次指针移动的过程，所以对应的这个查询也有 \(O(n\sqrt{m})\) 次。所以我们必须要有一种能够 \(O(1)\) 回答这个询问的办法。

考虑莫队二次离线，把莫队指针移动产生的 \(O(n\sqrt{m})\) 个形如 \(cnt_{[r+1,n],lower,a_{l'}}\) 的询问再次离线下来。这里需要注意一下，lxl 比较毒瘤，卡了线性空间。所以我们需要把 \(O(n\sqrt{m})\) 个询问想办法用 \(O(n+m)\) 的空间存储。发现我们的指针一次移动是单向的，形成了一段区间，所以没必要把所有指针移动都存下来，只需要存移动的起点和终点就可以了。

发现，虽然有 \(O(n\sqrt{m})\) 次查询，但就只有 \(O(n)\) 次插入操作。这里用到了一个叫做“根号平衡”的思想。我们只需要一种能够 \(O(\sqrt{n})\) 插入，\(O(1)\) 查询的数据结构就可以了。

值域分块，查询比一个数小的数的个数。其实就是求区间和。求区间和就想到了前缀和，插入一个数其实就是对若干个前缀和做贡献。

分成块上前缀和和块内前缀和两部分，因为块长是根号，所以暴力对两部分做贡献加一就可以。一次插入复杂度 \(O(\sqrt{n})\)。

于是我们就求出了中间所有需要的数据。把他们再组织起来就可以了。

考虑到，莫队中，每次指针移动，都是产生了一个对当前询问的贡献，也就是 \(delta\)。所以我们只需要把每次的 \(delta\) 累加到当前询问下就可以了。而相邻两次询问，也是基于上一次询问的数据，加上了这一次询问指针产生的若干 \(delta\) 贡献。所以对所有的询问再做一次前缀和就行。

最后把莫队排完序后的询问还原成原询问顺序输出就可以。

代码

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
const int M = 1e5 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int n, m, a[N];
/*====================*/
template<class Type>
class C_FenwickTree
{
private:
	int n; vector<int>tree;
	/*====================*/
	int lowbit(int x) { return x & (-x); }
public:
	void Init(int n)
	{
		this->n = n; tree.assign(n + 1, Type());
	}
	void Add(int pos, Type d)
	{
		while (pos <= n)
		{
			tree[pos] += d;
			pos += lowbit(pos);
		}
	}
	Type Ask(int pos)
	{
		Type res = Type();
		while (pos)
		{
			res += tree[pos];
			pos -= lowbit(pos);
		}
		return res;
	}
	Type Ask(int l, int r)
	{
		if (l > r)return Type();
		Type res = Type(); l--;
		while (r > l)res += tree[r], r -= lowbit(r);
		while (l > r)res -= tree[l], l -= lowbit(l);
		return res;
	}
};
/*====================*/
int preupper[N], suflower[N];
/*====================*/
const int MO_S = 300;
/*====================*/
struct Query1
{
	int l, r, idx;
	Query1(int _l = 0, int _r = 0, int _idx = 0)
	{
		l = _l, r = _r, idx = _idx;
	}
	friend bool operator<(const Query1& a, const Query1& b)
	{
		return (a.l / MO_S == b.l / MO_S) ? (((a.l / MO_S) & 1) ? (a.r > b.r) : (a.r < b.r)) : (a.l < b.l);
	}
}query[M];
/*====================*/
lnt moans[M];
/*====================*/
struct Query2
{
	int l, r, sign, idx;
	Query2(int _l = 0, int _r = 0, int _sign = 0, int _idx = 0)
	{
		l = _l, r = _r, sign = _sign, idx = _idx;
	}
};
vector<Query2>sufquery[N];
vector<Query2>prequery[N];
/*====================*/
const int Block_S = 300;
const int Block_B = N / Block_S + 10;
/*====================*/
int belong[N];
struct Block
{
	int l, r;
	Block(void)
	{
		l = r = 0;
	}
}block[Block_B];
/*====================*/
void Solve(void)
{
	do
	{
		cin >> n >> m;
		for (int i = 1; i <= n; ++i)
		{
			cin >> a[i];
		}
		for (int i = 1; i <= m; ++i)
		{
			int l, r; cin >> l >> r;
			query[i] = Query1(l, r, i);
		}
	} while (false);//读入

	do
	{
		vector<int>lib;
		for (int i = 1; i <= n; ++i)
		{
			lib.push_back(a[i]);
		}
		sort(lib.begin(), lib.end());
		lib.erase(unique(lib.begin(), lib.end()), lib.end());
		for (int i = 1; i <= n; ++i)
		{
			a[i] = lower_bound(lib.begin(), lib.end(), a[i]) - lib.begin() + 1;
		}
	} while (false);//离散化

	do
	{
		C_FenwickTree<int>tree; tree.Init(n);
		for (int i = 1; i <= n; ++i)
		{
			preupper[i] = tree.Ask(a[i] + 1, n); tree.Add(a[i], 1);
		}
	} while (false);//预处理前缀upper

	do
	{
		C_FenwickTree<int>tree; tree.Init(n);
		for (int i = n; i >= 1; --i)
		{
			suflower[i] = tree.Ask(1, a[i] - 1); tree.Add(a[i], 1);
		}
	} while (false);//预处理后缀lower

	do
	{
		sort(query + 1, query + 1 + m);
		int l = 1, r = 0;
		for (int i = 1; i <= m; ++i)
		{
			if (query[i].l < l)sufquery[r + 1].push_back(Query2(query[i].l, l - 1, -1, i));
			while (query[i].l < l)moans[i] += suflower[--l];
			if (r < query[i].r)prequery[l - 1].push_back(Query2(r + 1, query[i].r, -1, i));
			while (r < query[i].r)moans[i] += preupper[++r];
			if (l < query[i].l)sufquery[r + 1].push_back(Query2(l, query[i].l - 1, +1, i));
			while (l < query[i].l)moans[i] -= suflower[l++];
			if (query[i].r < r)prequery[l - 1].push_back(Query2(query[i].r + 1, r, +1, i));
			while (query[i].r < r)moans[i] -= preupper[r--];
		}
	} while (false);//一次离线莫队

	do
	{
		for (int i = 1; i <= n; ++i)
		{
			belong[i] = i / Block_S + 1;
			if (block[belong[i]].l == 0)
			{
				block[belong[i]].l = i;
			}
			block[belong[i]].r = i;
		}
	} while (false);//预处理分块

	do
	{
		//查询[1,idx]中有多少数大于a[l~r]
		vector<int>cnt1(n + 10, 0), cnt2(belong[n] + 10, 0);
		for (int i = 1; i <= n; ++i)
		{
			//插入a[i]
			for (int j = a[i]; j >= block[belong[a[i]]].l; --j)cnt1[j]++;
			for (int j = belong[a[i]]; j >= belong[1]; --j)cnt2[j]++;
			for (int j = 0; j < prequery[i].size(); ++j)
			{
				int l = prequery[i][j].l;
				int r = prequery[i][j].r;
				for (int k = l; k <= r; ++k)
				{
					//查询大于a[k]的个数
					if (a[k] + 1 <= n)
					{
						moans[prequery[i][j].idx] += prequery[i][j].sign * (cnt1[a[k] + 1] + cnt2[belong[a[k] + 1] + 1]);
					}
				}
			}
		}
	} while (false);//二次离线莫队处理prequery

	do
	{
		//查询[idx,n]中有多少数小于a[l~r]
		vector<int>cnt1(n + 10, 0), cnt2(belong[n] + 10, 0);
		for (int i = n; i >= 1; --i)
		{
			//插入a[i]
			for (int j = a[i]; j <= block[belong[a[i]]].r; ++j)cnt1[j]++;
			for (int j = belong[a[i]]; j <= belong[n]; ++j)cnt2[j]++;
			for (int j = 0; j < sufquery[i].size(); ++j)
			{
				int l = sufquery[i][j].l;
				int r = sufquery[i][j].r;
				for (int k = l; k <= r; ++k)
				{
					//查询小于a[k]的个数
					if (a[k] - 1 >= 1)
					{
						moans[sufquery[i][j].idx] += sufquery[i][j].sign * (cnt1[a[k] - 1] + cnt2[belong[a[k] - 1] - 1]);
					}
				}
			}
		}
	} while (false);//二次离线莫队处理sufquery

	do
	{
		for (int i = 1; i <= m; ++i)
		{
			moans[i] += moans[i - 1];
		}
		vector<lnt>ans(m + 1, 0);
		for (int i = 1; i <= m; ++i)
		{
			ans[query[i].idx] = moans[i];
		}
		for (int i = 1; i <= m; ++i)
		{
			cout << ans[i] << endl;
		}
	} while (false);//处理输出答案
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}