BZOJ4358: permu 分块+并查集+离线

首先看到这题我们会想到用莫队算法，但是不能便捷地维护删除一个数字的操作，所以我们只能用线段树维护最长的权值连续存在区间，这样的话，复杂度是$O(n\sqrt{n}\log{n})$的，实测是不能够通过此题的。

但是这道题如果只有插入的话是比较容易维护的，只需要利用并查集就行了。

将序列分成$O(\sqrt{n})$块。

我们可以对于每个询问找出这个询问区间中的最大整块$(i,j)$表示从第$i$块到第$j$块。将这个询问存在这个二元组中。

对于每个$i$，我们可以在$O(n\alpha(n))$的时间内处理出每个$(i,j)$中并查集的状态，每到达一个$j$，我们考虑所有在$(i,j)$上的询问，暴力向两边拓展并维护并查集，得出询问的答案之后还原在暴力中对于并查集的修改即可。

可惜的是由于并查集复杂度基于均摊，这样做并不是$O(\alpha(n))$，但是由于进行了启发式合并，复杂度不会高于$O(\log{n})$。

对于那些不跨越任何块的小区间，我们可以利用与区间长度有关的暴力，详情见代码。

然后就用这样奇怪的方式卡过去了。

时间复杂度$O(n\sqrt{n}(\alpha(n)\to{\log n}))$。

#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}
int getint() {
	static int c, x;
	while (!isdigit(c = getc()));
	x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}

#define N 50010
int n, q, p[N], bel[N], be[310], en[310], ans[N];
struct Array {
	int t[N], a[N], tclock;
	int operator [] (int x) {
		if (t[x] != tclock) {
			t[x] = tclock;
			a[x] = 0;
		}
		return a[x];
	}
	void modify(int x, int c) {
		if (t[x] != tclock) {
			t[x] = tclock;
			a[x] = 0;
		}
		a[x] = c;
	}
}f;

int solve(int l, int r) {
	++f.tclock;
	int i, j, k, ans = 0;
	for (i = l; i <= r; ++i)
		f.modify(p[i], 1);
	for (i = l; i <= r; ++i) {
		if (!f[p[i] + 1]) {
			for (j = p[i]; f[j]; --j);
			ans = max(ans, p[i] - j);
		}
	}
	return ans;
}

struct Query {
	int l, r, id, rl, rr;
	friend bool operator < (const Query &a, const Query &b) {
		if (a.l != b.l)
			return a.l < b.l;
		if (a.r != b.r)
			return a.r < b.r;
		return 1;
	}
}sav[N];

int sroot[N], siz[N];
int find(int x) {
	return x == sroot[x] ? x : sroot[x] = find(sroot[x]);
}
void merge(int x, int y) {
	x = find(x), y = find(y);
	if (siz[x] > siz[y])
		swap(x, y);
	siz[y] += siz[x];
	sroot[x] = y;
}
#define fi first
#define se second
#define mp make_pair
#define pu push
stack<pair<int, pair<int, int> > > s;
stack<int> s2;
int _find(int x) {
	if (x == sroot[x])
		return x;
	int y = _find(sroot[x]);
	s.pu(mp(x, mp(sroot[x], siz[x])));
	return sroot[x] = y;
}
void _merge(int x, int y) {
	x = _find(x), y = _find(y);
	s.pu(mp(x, mp(sroot[x], siz[x])));
	s.pu(mp(y, mp(sroot[y], siz[y])));
	if (siz[x] > siz[y])
		swap(x, y);
	sroot[x] = y;
	siz[y] += siz[x];
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("tt.in", "r", stdin);
#endif
	n = getint();
	q = getint();
	int i, j, k;
	for (i = 1; i <= n; ++i)
		p[i] = getint();
	int m = ceil(sqrt(n)), cnt = 0, point = 0;
	while (point < n) {
		++cnt;
		be[cnt] = point + 1;
		for (i = 1; i <= m && point < n; ++i)
			bel[++point] = cnt;
		en[cnt] = point;
	}
	int l, r, id = 0;
	for (i = 1; i <= q; ++i) {
		l = getint();
		r = getint();
		if (bel[r] - bel[l] <= 1)
			ans[i] = solve(l, r);
		else {
			++id;
			sav[id].l = bel[l] + 1;
			sav[id].r = bel[r] - 1;
			sav[id].id = i;
			sav[id].rl = l;
			sav[id].rr = r;
		}
	}
	sort(sav + 1, sav + id + 1);
	point = 1;
	int tans, nowans;
	for (i = 1; i <= cnt; ++i) {
		for (j = 1; j <= n; ++j) {
			sroot[j] = j;
			siz[j] = 1;
		}
		tans = 1;
		++f.tclock;
		for (k = i; k <= cnt; ++k) {
			for (j = be[k]; j <= en[k]; ++j) {
				f.modify(p[j], 1);
				if (f[p[j] - 1]) {
					tans = max(tans, siz[find(p[j])] + siz[find(p[j] - 1)]);
					merge(p[j], p[j] - 1);
				}
				if (f[p[j] + 1]) {
					tans = max(tans, siz[find(p[j])] + siz[find(p[j] + 1)]);
					merge(p[j], p[j] + 1);
				}
			}
			while (sav[point].l == i && sav[point].r == k && point <= id) {
				nowans = tans;
				for (j = sav[point].rl; bel[j] != i; ++j) {
					f.modify(p[j], 1);
					s2.pu(p[j]);
					if (f[p[j] - 1]) {
						nowans = max(nowans, siz[_find(p[j])] + siz[_find(p[j] - 1)]);
						_merge(p[j], p[j] - 1);
					}
					if (f[p[j] + 1]) {
						nowans = max(nowans, siz[_find(p[j])] + siz[_find(p[j] + 1)]);
						_merge(p[j], p[j] + 1);
					}
				}
				for (j = sav[point].rr; bel[j] != k; --j) {
					f.modify(p[j], 1);
					s2.pu(p[j]);
					if (f[p[j] - 1]) {
						nowans = max(nowans, siz[_find(p[j])] + siz[_find(p[j] - 1)]);
						_merge(p[j], p[j] - 1);
					}
					if (f[p[j] + 1]) {
						nowans = max(nowans, siz[_find(p[j])] + siz[_find(p[j] + 1)]);
						_merge(p[j], p[j] + 1);
					}
				}
				ans[sav[point].id] = nowans;
				while (s.size()) {
					sroot[s.top().fi] = s.top().se.fi;
					siz[s.top().fi] = s.top().se.se;
					s.pop();
				}
				while (s2.size()) {
					f.modify(s2.top(), 0);
					s2.pop();
				}
				++point;
			}
		}
	}
	for (i = 1; i <= q; ++i)
		printf("%d\n", ans[i]);
	return 0;
}

233