根号
简单的根号相关问题
(根号分治 定期重构 分块 莫队)
一. 根号分治
精髓就是拼接两个暴力
1. 余数根号分治：Remainder Problem
首先直接单点更新O(1)，查询暴力跳O(n)。这个暴力的有点在于当查询的x比较大的时候，那么跳的次数就比较少。
另一种暴力思路就是维护c[i][j]为%i = j的下标的数的和，那么更新就是O(n)的，查询则变成O(1)的了。
我们考虑分治 设阈值为B。
当x<=B时用暴力2 O(B) O(1)
x > B时用暴力1 O(1) O(n/B)
B = sqrt(n)时 B = n / B
if(op == 1)
{
rep(i, 1, B) c[i][x % i] += y;
a[x] += y;
}
else
{
if(x <= B) cout << c[x][y] << '\n';
else
{
int res = 0;
for(int i = y; i <= 500000; i += x) res += a[i];
cout << res << '\n';
}
}
小变化
给定一个长度为 ( n ) 的序列 ( x )（元素编号从 ( 1 ) 开始），所有元素初始值为 ( 0 )。接下来进行 ( q ) 次操作，每次操作分为以下两种类型（操作含参数 ( a, b )）：
设有长度为 n 的序列 \(x = (x_1, x_2, \dots, x_n)\)，初始时满足全0
接下来进行 q 次操作，每次操作分为以下两类之一：
-
更新操作：给定 a, b，对所有满足 \(a \cdot i \le n\) 的正整数 \(i\)，执行
\(x_{a \cdot i} \leftarrow x_{a \cdot i} + b\). -
查询操作：给定 \(a, b \; (a \le b)\)，输出
\(\sum_{i=a}^{b} x_i\).
暴力1，直接跳着修改然后BIT查询，复杂度\(O(log(n) \times \sqrt{n})\)
暴力2，对于每个修改直接记录tag[a]加了多少，查询时在区间内查看a的倍数有几个在区间内即为贡献 \(O(B)\)
然后就可以对于a<=B用2，a>B用
分块
比线段树能解决的问题更多但是复杂度更。
[0, B) [B, 2B) [2B, 3B) ... [iB, (i+1)B)
区间tag + 自身信息 = 真实信息
inline int get(int i)
{
return i / len;
}
void modify(int l, int r, int d)
{
int x = get(l), y = get(r);
if (x == y)for (int i = l; i <= r; i++)a[i] += d, sum[get(i)] += d; // 同一块内
else // 跨块
{
for (int i = l; i < (x + 1) * len; i++)a[i] += d, sum[get(i)] += d;
for (int i = x + 1; i < y; i++)add[i] += d, sum[i] += 1ll * d * len;
for (int i = y * len; i <= r; i++)a[i] += d, sum[get(i)] += d;
}
}
ll query(int l, int r)
{
ll ans = 0;
int x = get(l), y = get(r);
if (x == y)for (int i = l; i <= r; i++)ans += a[i] + add[get(i)];
else
{
for (int i = l; i < (x + 1) * len; i++) ans += a[i] + add[get(i)];
for (int i = x + 1; i < y; i++) ans += sum[i];
for (int i = y * len; i <= r; i++) ans += a[i] + add[get(i)];
}
return ans;
}
分块最正经的写法
线段树不太能做的 教主的魔法
[1, B] [B+1, 2B] [2B+1, 3B] ... [kB+1, n]
注意最后是 n !
一个显然的做法就是每次查询对一个块进行排序然后二分，但是这样整块太多了复杂度就退化了。
那么我们考虑在修改时维护块内的顺序，因为整块的修改并不会改变相对大小关系，所以只需要在暴力改单个元素的那至多两个块内排序即可。所以修改的复杂度就是 \(O(B*logB + n/B)\) 查询(由于已经维护了有序的情况所以块内直接二分即可)则是 \(O(n/B * log B)\)
对于每一块如果他们同时加上k，那么他们的相对大小不变。
对于块内部分元素的加，则会打乱相对大小所以需要重新排序。
#include <bits/stdc++.h>
#define ls cur << 1
#define rs cur << 1 | 1
#define repf(i, a, b) for(long long i = (a); i >= (b); i -- )
#define rep(i, a, b) for(long long i = (a); i <= (b); i ++ )
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
const int M = 2e6 + 10;
int a[N], tag[1010];
int b[N]; // sort
int B;
int L[1010], R[1010], cnt;
int get(int x)
{
return (x - 1) / B + 1;
}
void xg(int l, int r, int val)
{
rep(i, l, r) a[i] += val;
int c = get(l);
memcpy(b + L[c], a + L[c], (R[c] - L[c] + 1) * sizeof(int));
sort(b + L[c], b + R[c] + 1);
}
void modify(int l, int r, int val)
{
int x = get(l), y = get(r);
if(x == y) xg(l, r, val);
else
{
xg(l, R[x], val);
xg(L[y], r, val);
rep(i, x + 1, y - 1) tag[i] += val;
}
}
int qs(int l, int r, int val)
{
int k = val - tag[get(l)];
int res = 0;
rep(i, l, r) if(a[i] >= k) res ++;
return res;
}
int query(int l, int r, int val)
{
int x = get(l), y = get(r);
if(x == y) return qs(l, r, val);
int ans = 0;
ans += qs(l, R[x], val);
ans += qs(L[y], r, val);
rep(i, x + 1, y - 1)
{
int LL = L[i], RR = R[i], best = -1;
int k = val - tag[i];
while(LL <= RR)
{
int mid = LL + RR >> 1;
if(b[mid] >= k) best = mid, RR = mid - 1;
else LL = mid + 1;
}
if(best == -1) continue;
ans += R[i] - best + 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q; cin >> n >> q;
rep(i, 1, n) cin >> a[i], b[i] = a[i];
B = sqrt(n);
cnt = get(n);
rep(i, 1, cnt)
{
L[i] = (i - 1) * B + 1;
R[i] = i * B;
if(i == cnt) R[i] = n;
sort(b + L[i], b + R[i] + 1);
}
while( q -- )
{
char op; cin >> op;
int l, r, val; cin >> l >> r >> val;
if(op == 'M') modify(l, r, val);
else cout << query(l, r, val) << '\n';
}
return 0;
}
分块 (序列分块 操作分块(对时间轴分块技巧))
数列分块入门 1 太简单不写了
数列分块入门 2 与教主的魔法完全相同
数列分块入门 3 区间加法，询问区间内某个值 x 的前驱（比其小的最大元素）
查询可以拆到整块和散块上 （对于每个块查一个前驱，散块也是再求最大值即可）
查排名和前驱后继是等难的问题 处理方式几乎相同 处理方法也类似2
数列分块入门 4 区间加 区间求和 简单
数列分块入门 5 区间开方 区间求和
类似势能线段树，每个数被开方的次数<= 6次。 V < 2^32。 所以当区间最大值 > 1时暴力开方即可。
一个较为精确的上界是 loglogV，因为每一次开根都是在指数上 ÷ 2。
数列分块入门 6 定期重构
先想一个暴力，插入分块后O(块的个数)的代价定位，然后再O(块长)插入。
这样有一个问题就是如果往一个块内一直插入，那么O(块长)插入就变得很慢 退化至平方。
所以考虑插入到一定数量(2*B)后 重新分块(代价就是O(n))。重构的次数不会很多，都往一个里面插\(O(\frac{q}{B} \times n)\)
定期重构
数列分块6
与块状链表相似
注意莫队的写法 先加后减最好 保证 l >= r
// 1. 先把需要扩大的方向处理完 (加点)
while (l > x) add(-- l); // 左指针向左扩
while (r < y) add(++ r); // 右指针向右扩
// 2. 再把需要缩小的方向处理完 (删点)
while (l < x) del(l ++); // 左指针向右缩
while (r > y) del(r --); // 右指针向左缩
不然可能出现删除一个没出现的元素，比较奇怪
带修莫队，就是HH的项链的带修改版本，考虑加上一维时间 其实就做完了
排序关键字就是 左端点所在块 右端点所在块 时间轴
复杂度有点点难分析就是 \(O(n^{5/3})\)
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
using namespace std;
typedef long long ll;
const int N = 1.4e5 + 10;
const int P = 1e9 + 7;
int n, m, B;
int a[N], cntq, cntm;
struct qs
{
int l, r, t, id;
} qq[N], qr[N];
inline bool cmp(qs q1, qs q2)
{
return q1.l/B == q2.l/B ? (q1.r/B == q2.r/B ? q1.t < q2.t : q1.r < q2.r) : q1.l < q2.l;
}
int cnt[1000010], res, ans[N];
inline void add(int x)
{
cnt[a[x]] ++;
if(cnt[a[x]] == 1) res ++;
}
inline void del(int x)
{
cnt[a[x]] --;
if(cnt[a[x]] == 0) res --;
}
inline void xg(int x, int t)
{
if(qq[x].l <= qr[t].l && qr[t].l <= qq[x].r)
{
del(qr[t].l);
cnt[qr[t].r] ++;
if(cnt[qr[t].r] == 1) res ++;
}
swap(a[qr[t].l], qr[t].r);
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m; B = pow(n, 0.666); rep(i, 1, n) cin >> a[i];
if(B < 1) B = 1;
rep(i, 1, m)
{
char op; int l, r; cin >> op >> l >> r;
if(op == 'Q') ++ cntq, qq[cntq] = {l, r, cntm, cntq};
else ++ cntm, qr[cntm] = {l, r, 0, 0};
}
sort(qq + 1, qq + 1 + cntq, cmp); int l = 1, r = 0, t = 0;
rep(i, 1, cntq)
{
while(l > qq[i].l) add(-- l);
while(r < qq[i].r) add(++ r);
while(l < qq[i].l) del(l ++);
while(r > qq[i].r) del(r --);
while(t < qq[i].t) xg(i, ++ t);
while(t > qq[i].t) xg(i, t --);
ans[qq[i].id] = res;
}
rep(i, 1, cntq) cout << ans[i] << '\n';
return 0;
}
回滚莫队&不删除莫队
这类莫队是可以解决 add一个元素维护信息很容易 但是del并不容易。例如维护max
其实很简单就是排序询问还是一样的，考虑如何不删呢？考虑现在的左端点都在块k，那么对于右端点也在块k询问显然可以直接暴力处理，那么对于右端点不在块k内的呢？此时\(r\)是递增的，\(l\)是在块k内的，所以\(r\)是好维护的，而\(l\)只在块k内所以直接暴力即可。
初始化基准点：将莫队的左指针设为块 \(k\) 的右边界下一个位置（即 \(R\_block + 1\)），右指针设为块 \(k\) 的右边界（即 \(R\_block\)）。此时区间为空。
维护右端点（只加不减）：因为这些询问的右端点 \(r\) 是递增的，所以右指针只需一直往右移动并 Add 元素，永远不需要往回走（不需要 Del）。
处理左端点（暴力加 + 撤销）：对于当前询问的左端点 \(l\)，它一定在块 \(k\) 内。我们将左指针从 \(R\_block + 1\) 往左移动到 \(l\)，沿途 Add 元素。
精髓：回滚（Rollback）：记录下答案后，我们需要把左指针移回 \(R\_block + 1\)。注意，这里的“撤销”不是传统意义上的 Del 去重新计算 Max，而是直接回滚状态。
具体做法：在左指针移动前，备份当前的 Max 值（或全局状态）。左指针往左 Add 时，记录下修改了哪些元素的出现次数。询问结束后，把这些元素的出现次数暴力减回去，并直接把 Max 恢复为之前备份的值。因为左指针的移动距离不超过 \(\sqrt{N}\)，这个撤销操作的代价非常小。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
int n, m, B;
int a[N], id[N], br[N], buc[N], cnt[N];
int C[N];
ll res, ans[N];
struct qs
{
int l, r, id;
} q[N];
inline bool cmp(qs n1, qs n2)
{ return id[n1.l] == id[n2.l] ? n1.r < n2.r : id[n1.l] < id[n2.l]; }
inline void add(int x)
{
cnt[a[x]] ++;
res = max(res, 1ll*cnt[a[x]]*buc[a[x]]);
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m; B = max(1.0, n / sqrt(1.0*m));
int t = 0;
rep(i, 1, n)
{
cin >> a[i]; buc[i] = a[i];
id[i] = (i - 1) / B + 1, br[id[i]] = i;
}
sort(buc + 1, buc + 1 + n);
t = unique(buc + 1, buc + 1 + n) - (buc + 1);
rep(i, 1, n) a[i] = lower_bound(buc + 1, buc + 1 + t, a[i]) - buc;
rep(i, 1, m)
{
cin >> q[i].l >> q[i].r; q[i].id = i;
} sort(q + 1, q + 1 + m, cmp);
int l = 1, r = 0, lst = 0;
rep(i, 1, m)
{
if(id[q[i].l] == id[q[i].r])
{
ll tres = 0;
rep(j, q[i].l, q[i].r)
{
C[a[j]] ++;
tres = max(tres, 1ll * buc[a[j]] * C[a[j]]);
}
ans[q[i].id] = tres;
rep(j, q[i].l, q[i].r) C[a[j]] --;
continue;
}
if(id[q[i].l] != lst)
{
rep(j, l, r) cnt[a[j]] --;
lst = id[q[i].l];
l = br[lst] + 1;
r = l - 1;
res = 0;
}
while(r < q[i].r) add(++ r);
ll tmp = res;
int bnd = l;
while(l > q[i].l) add(-- l);
ans[q[i].id] = res;
rep(j, l, bnd - 1) cnt[a[j]] --;
res = tmp; l = bnd;
}
rep(i, 1, m) cout << ans[i] << '\n';
return 0;
}
在线莫队，如何在线的做莫队呢？很自然的想到把每两个块之间的答案预处理一下，然后询问时将区间拆分成三份 \([l, k1*B] [k1*B+1, k2*B] [k2*B+1, r]\) 中间的部分我们已经预处理过了，所以每次暴力做两边即可，这样会产生更多的空间需求（预处理）。
怎么快速求任意一个数字 \(Y\) 在 \([l, r]\) 里的出现次数？
做法 A：空间换时间 —— 前缀和桶（空间 \(O(n\sqrt{n})\)，查询 \(O(\sqrt{n})\)， 开一个二维数组 pre_cnt[i][v]，表示前 \(i\) 个块中，数字 \(v\) 出现的次数。
做法 B：极致压缩空间 —— vector 二分（空间 \(O(n)\)，查询 \(O(\sqrt{n} \log n)\)）这就是我上一轮跟你说的、OI 实战中最常用的神级做法。预处理： 给每种颜色开一个 vector
浙公网安备 33010602011771号