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
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.