復原莫隊學習筆記

\(\text{Part1}\)

如果是隻增，那麼将詢問按左端點所在塊為第一關鍵字升序，右端點為第二關鍵字升序排序

如果詢問在一個塊内，暴力掃

不然對于左端點在同一個塊的所有詢問，先将莫隊區間左端點移到塊右端點 \(+1\)，右端點移到塊右端點，這是一個空區間

然後右端點遞增，保證了隻增，左端點向左也是隻增，每個詢問增完後要将左端點復原到增之前的位置，為了以後隻增

\(O(n\sqrt m+m\sqrt n)\)

例如

\(\text{「JOISC 2014 Day1」曆史研究}\)

\(\text{Code}\)

#include <cstdio>
#include <algorithm>
#include <cmath>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;

const int N = 1e5 + 5;
int n, m, a[N], b[N], c[N], R[N], buc[N], tbuc[N], pos[N];
LL ans[N];
struct node{int l, r, id;}Q[N];
IN bool cmp(node a, node b){return pos[a.l] < pos[b.l] ? 1 : (pos[a.l] == pos[b.l] ? a.r < b.r : 0);}

IN void Init()
{
	scanf("%d%d", &n, &m);
	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + n + 1); int len = unique(b + 1, b + n + 1) - b - 1;
	for(RE int i = 1; i <= n; i++) c[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
	int bl = sqrt(n);
	for(RE int i = 1; i <= m; i++)
		scanf("%d%d", &Q[i].l, &Q[i].r), pos[Q[i].l] = Q[i].l / bl, pos[Q[i].r] = Q[i].r / bl, Q[i].id = i;
	sort(Q + 1, Q + m + 1, cmp), R[0] = bl - 1, R[n / bl] = n;
	for(RE int i = 1; i < n / bl; i++) R[i] = R[i - 1] + bl;
}
IN void Add(int x, LL &s){++buc[c[x]], s = max(s, (LL)a[x] * buc[c[x]]);}
IN void Del(int x){--buc[c[x]];}

int main()
{
	Init();
	int l = 1, r = 0, lst = -1, tl; LL Ans = 0, tmp;
	for(RE int i = 1; i <= m; i++)
	{
		if (pos[Q[i].l] == pos[Q[i].r])
		{
			for(RE int j = Q[i].l; j <= Q[i].r; j++)
				++tbuc[c[j]], ans[Q[i].id] = max(ans[Q[i].id], (LL)a[j] * tbuc[c[j]]);
			for(RE int j = Q[i].l; j <= Q[i].r; j++) --tbuc[c[j]];
			continue;
		}
		if (pos[Q[i].l] != lst)
		{
			while (r > R[pos[Q[i].l]]) Del(r--);
			while (l < R[pos[Q[i].l]] + 1) Del(l++);
			Ans = 0, lst = pos[Q[i].l];
		}
		while (r < Q[i].r) Add(++r, Ans);
		tl = l, tmp = Ans;
		while (tl > Q[i].l) Add(--tl, tmp);
		ans[Q[i].id] = tmp;
		while (tl < l) Del(tl++);
	}
	for(RE int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}
           

\(\text{Part2}\)

隻删的話，對比隻增，左端點同塊時，需要莫隊區間 \(r\) 的移動是遞減的

于是将詢問按左端點所在塊為第一關鍵字升序，右端點為第二關鍵字降序排序

不然對于左端點在同一個塊的所有詢問，先将莫隊區間左端點移到塊左端點，右端點移動到 \(n\)，這是一個大區間

然後右端點遞減，保證了隻删，左端點向右也是隻删，每個詢問删完後要将左端點復原到删之前的位置，為了以後隻删

例如區間 \(mex\)