回滚莫队
有些问题不支持从序列中删除元素。回滚莫队通过调整扩展的顺序,并增加一些常数,使得删除操作变为回滚(撤销)操作,可以使用栈维护。
回滚莫队和普通莫队的排序方式基本相同,但不能使用奇偶块优化。这样 \(blo[l]\) 相等的所有询问的右端点 \(r\) 就会单调递增。
题意
给定一个长为 \(n\) 序列。有 \(q\) 次询问,每次询问给定一个区间 \([l,r]\),询问 \(\max_{i\in V}\{i\times cnt(i)\}\)。
这种最值形式不易实现删除操作,考虑如何回滚。对于 \(r-l+1\le \sqrt n\) 的询问,直接暴力即可。
考虑左右端点分居两块的情况。记 ed[i]
表示 \(i\) 块的结束位置,初始时 c_l = ed[blo[l]]
,c_r = c_l - 1
。扩展时总是先处理 \(r\),然后处理 \(l\),得到答案后再将 \(l\) 回滚到 ed[blo[l]]
。

容易发现时间复杂度仍为 \(O(n\sqrt m)\),且在块长 \(blen=\frac{n}{\sqrt m}\) 时最优。
模板代码
| #include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1E5 + 10;
int blen, block[N], ed[N];
struct Query {
int l, r, id;
inline bool operator<(const Query& other) const {
if(block[l] != block[other.l]) return block[l] < block[other.l];
return r < other.r;
}
} q[N];
int n, m;
int a[N], num[N], nn = 0;
ll ans[N];
void lisanhua() {
for(int i = 1; i <= n; i++) {
num[++nn] = a[i];
}
sort(num + 1, num + 1 + nn);
nn = unique(num + 1, num + 1 + nn) - (num + 1);
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}
}
ll cnt[N];
int cl, cr;
ll c_ans;
ll buf[N][2], top;
inline void clear() {
c_ans = 0;
// cout << "clear" << endl;
for(int i = 1; i <= nn; i++) cnt[i] = 0;
}
inline void clear_buf() {
// cout << "clear buf" << endl;
top = 0;
}
inline void add(int pos) {
// cout << "add: " << pos << endl;
cnt[a[pos]] += num[a[pos]];
buf[++top][0] = a[pos];
buf[top][1] = c_ans;
if(cnt[a[pos]] > c_ans) c_ans = cnt[a[pos]];
}
inline void roll_back() {
// cout << "roll back" << endl;
cnt[buf[top][0]] -= num[buf[top][0]];
c_ans = buf[top--][1];
}
ll bl[N];
inline ll baoli(int l, int r) {
ll res = 0;
for(int i = l; i <= r; i++) {
bl[a[i]] += num[a[i]];
if(bl[a[i]] > res) res = bl[a[i]];
}
for(int i = l; i <= r; i++) {
bl[a[i]] = 0;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
blen = n / sqrt(m);
for(int i = 1; i <= n; i++) block[i] = (i + blen - 1) / blen;
for(int i = 1; i <= n; i++) ed[block[i]] = i;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
lisanhua();
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
for(int i = 1; i <= m; i++) {
int l = q[i].l, r = q[i].r;
if(block[l] == block[r]) {
ans[i] = baoli(l, r);
}
}
sort(q + 1, q + 1 + m);
for(int i = 1; i <= m; i++) {
int l = q[i].l, r = q[i].r;
if(block[l] == block[r]) {
continue;
}
if(block[l] != block[cl]) {
cl = ed[block[l]], cr = cl - 1;
clear();
}
while(cr < q[i].r) add(++cr);
clear_buf();
while(cl > q[i].l) add(--cl);
ans[q[i].id] = c_ans;
while(cl != ed[block[cl]]) roll_back(), ++cl;
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
|
思路同上。
代码
| #include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2E5 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;
int blen, blo[N], ed[N];
struct Query {
int l, r, id;
inline bool operator<(const Query& other) const {
if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
return r < other.r;
}
} q[N];
int n, m, nn;
int a[N], ans[N];
void lisanhua() {
int num[N];
for(int i = 1; i <= n; i++) num[++nn] = a[i];
sort(num + 1, num + 1 + nn);
nn = unique(num + 1, num + 1 + nn) - (num + 1);
for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}
int b_mn[N], b_mx[N];
int baoli(int l, int r) {
int res = 0;
for(int i = l; i <= r; i++) {
b_mn[a[i]] = min(b_mn[a[i]], i);
b_mx[a[i]] = max(b_mx[a[i]], i);
res = max(res, b_mx[a[i]] - b_mn[a[i]]);
}
for(int i = l; i <= r; i++) {
b_mn[a[i]] = INF;
b_mx[a[i]] = 0;
}
return res;
}
int c_l, c_r, c_ans;
int mn[N], mx[N];
int buf[N][4], nb;
void clear_buf() {
nb = 0;
}
void clear() {
nb = 0;
c_ans = 0;
for(int i = 1; i <= nn; i++) mn[i] = INF, mx[i] = 0;
}
void update(int pos) {
buf[++nb][0] = a[pos];
buf[nb][1] = mn[a[pos]];
buf[nb][2] = mx[a[pos]];
buf[nb][3] = c_ans;
mn[a[pos]] = min(mn[a[pos]], pos);
mx[a[pos]] = max(mx[a[pos]], pos);
c_ans = max(c_ans, mx[a[pos]] - mn[a[pos]]);
}
void roll_back() {
int pos = buf[nb][0];
mn[pos] = buf[nb][1];
mx[pos] = buf[nb][2];
c_ans = buf[nb--][3];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
blen = max(1, (int)(n / sqrt(m)));
for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
for(int i = n; i >= 1; i--) ed[i] = (blo[i] == blo[i + 1]) ? ed[i + 1] : i;
lisanhua();
sort(q + 1, q + 1 + m);
for(int i = 1; i <= nn; i++) mn[i] = b_mn[i] = INF;
for(int i = 1; i <= m; i++) {
int l = q[i].l, r = q[i].r;
if(blo[l] == blo[r]) {
ans[q[i].id] = baoli(l, r);
continue;
}
if(blo[l] != blo[c_l]) {
clear();
c_l = ed[l], c_r = c_l - 1;
}
while(c_r < r) update(++c_r);
clear_buf();
while(c_l > l) update(--c_l);
ans[q[i].id] = c_ans;
while(c_l < ed[c_l]) roll_back(), ++c_l;
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
|
题意
给定一个长为 \(n\) 的排列 \(p\),有 \(q\) 次询问,每次询问给定一个整数四元组 \((l, r, a, b)\),表示查询有多少个整数二元组 \((u, v)\) 满足:
- \(l\le u\le v\le r\);
- 对于任意 \(\forall u\le i\le v\),有 \(a\le p_i\le b\)。
\(n\le 2\times 10^5\)
在区间 \([l,r]\) 内,一段极长的满足 \(p_i\in [a,b]\) 的区间 \([l',r']\) 会产生 \(\frac 12 (len+1)len\) 的贡献。
如果我们使用线段树维护序列,则没法处理值域。两个维度也都不可差分,不能离线扫描线。那么,我们需要使用两个数据结构分别维护序列和值域。
考虑在值域上莫队,现在我们只需要使用序列上的数据结构维护连续段,做到 \(O(1)\) 插入,\(O(\sqrt n)\) 查询区间连续段贡献(假设 \(n,q\) 同阶)即可。由于要求 \(O(1)\) 插入,考虑分块:我们维护块内部的答案和块两侧的极长段长度;查询时枚举整块,处理相邻整块之间的贡献,散块暴力即可。
如何维护连续段呢?我们可以给每个位置维护一个 \(hd\) 和 \(tl\) 表示所在连续段的起始和终止位置。然而,这种维护方式不易实现删除。因此使用回滚莫队,原封不动的恢复数组的改动即可。
代码
| #include<iostream>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<iomanip>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int N2 = 500;
int blo[N], blen, bcnt;
int bg[N2], ed[N2];
struct Query {
int l, r, u, v, id;
inline bool operator<(const Query &b) const {
if(blo[u] != blo[b.u]) return blo[u] < blo[b.u];
return v < b.v;
}
} qr[N];
int n, q;
int a[N], ia[N];
int ans[N];
ll baoli(int l, int r, int u, int v) {
int len = 0;
ll res = 0;
for(int i = l; i <= r; i++) {
if(u <= a[i] && a[i] <= v) {
++len;
} else {
res += (ll)len * (len + 1) / 2;
len = 0;
}
}
res += (ll)len * (len + 1) / 2;
return res;
}
// 链表
int sz[N], hd[N], tl[N];
int c_l, c_r, c_ans[N2];
int sta[N], top;
void clear() {
if(!top) return;
for(int i = 1; i <= n; i++) hd[i] = tl[i] = i;
for(int i = 1; i <= bcnt; i++) c_ans[i] = 0;
for(int i = 1; i <= n; i++) sz[i] = 0;
top = 0;
}
void insert(int v) {
int pos = ia[v], bp = blo[pos];
sta[++top] = pos;
sz[pos] = 1;
c_ans[bp] += 1;
if(pos != bg[blo[pos]] && sz[hd[pos - 1]]) {
c_ans[bp] += sz[hd[pos - 1]] * sz[pos];
hd[pos] = hd[pos - 1];
tl[hd[pos]] = pos;
sz[hd[pos]] += sz[pos];
}
if(pos != ed[blo[pos]] && sz[pos + 1]) {
c_ans[bp] += sz[pos + 1] * sz[hd[pos]];
hd[tl[pos + 1]] = hd[pos];
tl[hd[pos]] = tl[pos + 1];
sz[hd[pos]] += sz[pos + 1];
}
}
void roll_back() {
int pos = sta[top--], bp = blo[pos];
if(pos != ed[blo[pos]] && sz[pos + 1]) {
sz[hd[pos]] -= sz[pos + 1];
tl[hd[pos]] = pos;
hd[tl[pos + 1]] = pos + 1;
c_ans[bp] -= sz[pos + 1] * sz[hd[pos]];
}
if(pos != bg[blo[pos]] && sz[hd[pos - 1]]) {
sz[hd[pos]] -= sz[pos];
tl[hd[pos]] = pos - 1;
hd[pos] = pos;
c_ans[bp] -= sz[hd[pos - 1]] * sz[pos];
}
assert(sz[pos] == 1);
c_ans[bp] -= 1;
sz[pos] = 0;
hd[pos] = tl[pos] = pos;
}
int query(int l, int r) {
int res = 0, tmp = 0;
if(l != bg[blo[l]]) {
int len = 0;
for(int i = l; i <= ed[blo[l]]; i++) {
if(sz[i]) ++len;
else {
res += len * (len + 1) / 2;
len = 0;
}
}
res += len * (len + 1) / 2;
tmp = len;
l = bg[blo[l] + 1];
}
for(int i = blo[l]; i < blo[r]; i++) {
res += tmp * sz[bg[i]];
if(sz[hd[ed[i]]] != blen) tmp = sz[hd[ed[i]]];
else tmp += sz[hd[ed[i]]];
res += c_ans[i];
}
int len = 0;
for(int i = r; i >= bg[blo[r]]; i--) {
if(sz[i]) ++len;
else {
res += len * (len + 1) / 2;
len = 0;
}
}
res += len * (len + 1) / 2;
res += tmp * len;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= q; i++) cin >> qr[i].l >> qr[i].r >> qr[i].u >> qr[i].v;
for(int i = 1; i <= q; i++) qr[i].id = i;
for(int i = 1; i <= n; i++) ia[a[i]] = i;
blen = max((int)3, (int)sqrt(n));
bcnt = (n + blen - 1) / blen;
for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
for(int i = 1; i <= bcnt; i++) bg[i] = (i - 1) * blen + 1;
for(int i = 1; i <= bcnt; i++) ed[i] = i * blen;
ed[bcnt] = n;
sort(qr + 1, qr + 1 + q);
for(int i = 1; i <= n; i++) hd[i] = tl[i] = i;
for(int i = 1; i <= q; i++) {
int l = qr[i].l, r = qr[i].r, u = qr[i].u, v = qr[i].v, id = qr[i].id;
if(r - l + 1<= blen) {
ans[id] = baoli(l, r, u, v);
continue;
}
if(v - u + 1 <= blen) {
clear();
c_l = u;
c_r = u - 1;
while(c_r < v) insert(++c_r);
ans[id] = query(l, r);
while(top) roll_back();
c_l = 0;
continue;
}
if(c_l <= u) {
clear();
c_l = ed[blo[u]] + 1;
c_r = ed[blo[u]];
}
while(c_r < v) insert(++c_r);
while(c_l > u) insert(--c_l);
ans[id] = query(l, r);
while(c_l < ed[blo[u]] + 1) ++c_l, roll_back();
}
for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}
|