【Ynoi 2019 模拟赛】Yuno loves sqrt technology II

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);//预处理前缀upperdo{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);//预处理后缀lowerdo{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);//二次离线莫队处理prequerydo{//查询[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);//二次离线莫队处理sufquerydo{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_JUDGEfreopen("IN.txt", "r+", stdin);
#endifios::sync_with_stdio(false);cin.tie(NULL), cout.tie(NULL);int T = 1; //cin >> T;while (T--)Solve();return 0;
}