BZOJ2125: 最短路 仙人掌+LCA
BZOJ4140: 共点圆加强版 二进制分组+三分+点积

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

shinbokuow posted @ Dec 26, 2015 04:04:39 PM in BZOJ with tags 分块 并查集 离线 , 1888 阅读

 

首先看到这题我们会想到用莫队算法,但是不能便捷地维护删除一个数字的操作,所以我们只能用线段树维护最长的权值连续存在区间,这样的话,复杂度是$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

Alyssa 说:
Jan 09, 2023 01:11:01 PM

Permu block + merge search + offline is a powerful combination for solving optimization problems. This technique can be used to solve problems in a wide range of fields, from scheduling diamond loose stones wholesale to resource allocation. This approach is particularly well-suited to large-scale optimization problems, as it can efficiently handle very large amounts of data.

pavzi.com 说:
Jan 10, 2024 01:37:56 PM

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter