算法能解决的问题
- 区间在线的统计某种信息
- 区间在线的修改属性
算法原理
首先确定块的大小, 然后对序列进行分块
修改操作可以只考虑对散列块的影响, 整块的影响直接计算
查询首先查询散列块, 然后再计算整块
算法步骤
对块初始化, 定义块的起始位置和结束位置, 初始位置下标是 1 1 1
void init() {
// 计算块大小
bsize = sqrt(n);
// 计算块的数量
bcnt = (n - 1) / bsize + 1;
// 计算块的起始位置和结束位置
for (int i = 1; i <= bcnt; ++i) {
st[i] = (i - 1) * bsize + 1;
ed[i] = min(i * bsize, n);
}
// 计算每个下标属于哪个块
for (int i = 1; i <= n; ++i) b[i] = (i - 1) / bsize + 1;
// 初始化区间和
for (int i = 1; i <= n; ++i) {
s[b[i]] += w[i];
}
}
示例代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
int w[N];
LL add[N], s[N];
int bsize, bcnt, st[N], ed[N];
int b[N];
void init() {
// 计算块大小
bsize = sqrt(n);
// 计算块的数量
bcnt = (n - 1) / bsize + 1;
// 计算块的起始位置和结束位置
for (int i = 1; i <= bcnt; ++i) {
st[i] = (i - 1) * bsize + 1;
ed[i] = min(i * bsize, n);
}
// 计算每个下标属于哪个块
for (int i = 1; i <= n; ++i) b[i] = (i - 1) / bsize + 1;
// 初始化区间和
for (int i = 1; i <= n; ++i) {
s[b[i]] += w[i];
}
}
void modify(int l, int r, int v) {
int x = b[l], y = b[r];
if (x == y) {
for (int i = l; i <= r; ++i) w[i] += v, s[x] += v;
return;
}
for (int i = l; i <= ed[x]; ++i) w[i] += v, s[x] += v;
for (int i = st[y]; i <= r; ++i) w[i] += v, s[y] += v;
// 在修改的时候直接修改区间, 延迟标记只对散列块生效
for (int i = x + 1; i < y; ++i) {
add[i] += v;
int len = ed[i] - st[i] + 1;
s[i] += len * v;
}
}
LL query(int l, int r) {
LL ans = 0;
int x = b[l], y = b[r];
if (x == y) {
for (int i = l; i <= r; ++i) ans += w[i] + add[x];
return ans;
}
for (int i = l; i <= ed[x]; ++i) ans += w[i] + add[x];
for (int i = st[y]; i <= r; ++i) ans += w[i] + add[y];
for (int i = x + 1; i < y; ++i) ans += s[i];
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> w[i];
init();
char c;
while (m--) {
cin >> c;
int l, r, d;
cin >> l >> r;
if (c == 'C') {
cin >> d;
modify(l, r, d);
}
else cout << query(l, r) << '\n';
}
return 0;
}
*P2801 教主的魔法
对序列分块, 修改的时候首先修改块的两侧, 然后修改整块, 注意修改后需要对备份数组 t t t进行排序处理, 查询的时候暴力查询整块的两侧, 然后再二分查询块内
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 1010;
int n, m;
int a[N], t[N];
int add[M], st[M], ed[M];
int b[N];
// 块的大小和块的数量
int bsize, bcnt;
void _sort(int x) {
for (int i = st[x]; i <= ed[x]; ++i) t[i] = a[i];
sort(t + st[x], t + ed[x] + 1);
}
void init() {
bsize = sqrt(n);
bcnt = (n - 1) / bsize + 1;
for (int i = 1; i <= bcnt; ++i) {
st[i] = (i - 1) * bsize + 1;
ed[i] = min(i * bsize, n);
}
for (int i = 1; i <= n; ++i) {
b[i] = (i - 1) / bsize + 1;
}
for (int i = 1; i <= bcnt; ++i) _sort(i);
}
void modify(int l, int r, int c) {
int x = b[l], y = b[r];
if (x == y) {
for (int i = l; i <= r; ++i) a[i] += c;
_sort(x);
return;
}
for (int i = l; i <= ed[x]; ++i) a[i] += c;
for (int i = st[y]; i <= r; ++i) a[i] += c;
for (int i = x + 1; i < y; ++i) add[i] += c;
_sort(x), _sort(y);
}
int query(int l, int r, int v) {
int ans = 0;
int x = b[l], y = b[r];
if (x == y) {
for (int i = l; i <= r; ++i) {
if (a[i] + add[x] >= v) ans++;
}
return ans;
}
for (int i = l; i <= ed[x]; ++i) {
if (a[i] + add[x] >= v) ans++;
}
for (int i = st[y]; i <= r; ++i) {
if (a[i] + add[y] >= v) ans++;
}
// 计算>= val的数字个数
for (int i = x + 1; i < y; ++i) {
int val = v - add[i];
// 统计块内<=val的数的位置
int p = lower_bound(t + st[i], t + ed[i] + 1, val) - t;
ans += ed[i] - p + 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
init();
while (m--) {
char c;
cin >> c;
int l, r, v;
cin >> l >> r >> v;
if (c == 'M') modify(l, r, v);
else cout << query(l, r, v) << '\n';
}
return 0;
}
*P3373 【模板】线段树 2
如何维护延迟标记?
维护散列块的延迟标记 m u l [ x ] , a d d [ x ] mul[x], add[x] mul[x],add[x], 整块直接计算
- 修改的时候, 首先下传延迟标记, 如果是散块直接暴力修改并且累计变化量
- 修改的时候, 如果是整块直接修改
- 查询的时候首先将延迟标记下传, 然后再分散列块和整块查询
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m, p;
int w[N];
LL add[N], mul[N], s[N];
int bsize, bcnt, b[N], st[N], ed[N];
void init() {
bsize = max(1, (int) sqrt(n));
bcnt = (n - 1) / bsize + 1;
for (int i = 1; i <= bcnt; ++i) {
st[i] = (i - 1) * bsize + 1;
ed[i] = min(i * bsize, n);
}
for (int i = 1; i <= n; ++i) b[i] = (i - 1) / bsize + 1;
for (int i = 1; i <= bcnt; ++i) {
mul[i] = 1;
add[i] = 0;
}
for (int i = 1; i <= n; ++i) {
w[i] %= p;
if (w[i] < 0) w[i] += p;
s[b[i]] = (s[b[i]] + w[i]) % p;
}
}
void pushdown(int x) {
if (mul[x] == 1 && add[x] == 0) return;
for (int i = st[x]; i <= ed[x]; ++i) {
w[i] = ((LL) w[i] * mul[x] + add[x]) % p;
if (w[i] < 0) w[i] += p;
}
mul[x] = 1;
add[x] = 0;
}
void mmul(int l, int r, int d) {
d %= p;
if (d < 0) d += p;
int x = b[l], y = b[r];
if (x == y) {
pushdown(x);
LL tmp = 0;
for (int i = l; i <= r; ++i) {
int val1 = w[i];
int val2 = (int) ((LL) val1 * d % p);
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[x] = (s[x] + tmp) % p;
if (s[x] < 0) s[x] += p;
return;
}
pushdown(x);
LL tmp = 0;
for (int i = l; i <= ed[x]; ++i) {
int val1 = w[i];
int val2 = (int) ((LL) val1 * d % p);
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[x] = (s[x] + tmp) % p;
if (s[x] < 0) s[x] += p;
pushdown(y);
tmp = 0;
for (int i = st[y]; i <= r; ++i) {
int val1 = w[i];
int val2 = (int) ((LL) val1 * d % p);
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[y] = (s[y] + tmp) % p;
if (s[y] < 0) s[y] += p;
for (int i = x + 1; i <= y - 1; ++i) {
mul[i] = mul[i] * d % p;
add[i] = add[i] * d % p;
s[i] = s[i] * d % p;
if (s[i] < 0) s[i] += p;
}
}
void madd(int l, int r, int c) {
c %= p;
if (c < 0) c += p;
int x = b[l], y = b[r];
if (x == y) {
pushdown(x);
LL tmp = 0;
for (int i = l; i <= r; ++i) {
int val1 = w[i];
int val2 = val1 + c;
if (val2 >= p) val2 -= p;
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[x] = (s[x] + tmp) % p;
if (s[x] < 0) s[x] += p;
return;
}
pushdown(x);
LL tmp = 0;
for (int i = l; i <= ed[x]; ++i) {
int val1 = w[i];
int val2 = val1 + c;
if (val2 >= p) val2 -= p;
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[x] = (s[x] + tmp) % p;
if (s[x] < 0) s[x] += p;
pushdown(y);
tmp = 0;
for (int i = st[y]; i <= r; ++i) {
int val1 = w[i];
int val2 = val1 + c;
if (val2 >= p) val2 -= p;
w[i] = val2;
tmp += (val2 - val1);
}
tmp %= p;
s[y] = (s[y] + tmp) % p;
if (s[y] < 0) s[y] += p;
for (int i = x + 1; i <= y - 1; ++i) {
add[i] = (add[i] + c) % p;
int len = ed[i] - st[i] + 1;
s[i] = (s[i] + (LL) len * c) % p;
if (s[i] < 0) s[i] += p;
}
}
LL query(int l, int r) {
LL ans = 0;
int x = b[l], y = b[r];
if (x == y) {
pushdown(x);
for (int i = l; i <= r; ++i) ans = (ans + w[i]) % p;
return (ans % p + p) % p;
}
pushdown(x);
for (int i = l; i <= ed[x]; ++i) ans = (ans + w[i]) % p;
pushdown(y);
for (int i = st[y]; i <= r; ++i) ans = (ans + w[i]) % p;
for (int i = x + 1; i <= y - 1; ++i) ans = (ans + s[i]) % p;
return (ans % p + p) % p;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> p;
for (int i = 1; i <= n; ++i) cin >> w[i];
init();
cin >> m;
while (m--) {
int op, x, y, k;
cin >> op >> x >> y;
if (op == 1) {
cin >> k;
mmul(x, y, k);
}
else if (op == 2) {
cin >> k;
madd(x, y, k);
}
else cout << query(x, y) % p << '\n';
}
return 0;
}
*蒲公英
求的是区间众数最多的数字是那哪个
发现数据范围是 ≤ 4 × 1 0 4 \le 4 \times 10 ^ 4 ≤4×104, n = 200 \sqrt n = 200 n=200, 可以分块
做这样预处理定义 s ( x , i ) s(x, i) s(x,i)表示前 x x x个块中 w i w_i wi出现的次数, 暴力预处理这样数组, 算法时间复杂度 O ( n ) O(n) O(n)
再处理 f ( x , y ) f(x, y) f(x,y)表示从块 x x x开始位置, 到 y y y结束位置的众数, 算法时间复杂度 O ( n n ) O(n \sqrt n) O(nn)
这样一来, 块内的众数就知道了, 查询的时候需要查询散列块的众数是否会对结果造成影响
开一个桶, 首先统计散列块的数值累计到桶中, 然后判断散列块的每个位置(假设是 w i w_i wi)是否会成为整个区间的众数
具体的来说, 假设区间左端点块号是 x x x, 右端点块号是 y y y
t [ w i ] + s [ y − 1 ] [ w i ] − s [ x ] [ w i ] t[w_i] + s[y - 1][w_i] - s[x][w_i] t[wi]+s[y−1][wi]−s[x][wi]
就是整个区间内 w i w_i wi出现的次数, 初始的众数是块内的众数 f ( x + 1 , y − 1 ) f(x + 1, y - 1) f(x+1,y−1)
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 10, M = 210;
int n, m, w[N];
vector<int> vec;
int s[M][N], f[M][M];
int bsize, bcnt, st[N], ed[N], b[N];
void init() {
bsize = sqrt(n);
bcnt = (n - 1) / bsize + 1;
for (int i = 1; i <= bcnt; ++i) {
st[i] = (i - 1) * bsize + 1;
ed[i] = min(n, i * bsize);
}
for (int i = 1; i <= n; ++i) b[i] = (i - 1) / bsize + 1;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
int find(int x) {
return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}
void del(int a[], int l, int r) {
for (int i = l; i <= r; ++i) a[w[i]] = 0;
}
int query(int l, int r) {
static int t[N];
int x = b[l], y = b[r];
if (x == y) {
int cnt = 0, v = 0;
for (int i = l; i <= r; ++i) {
t[w[i]]++;
if (t[w[i]] > cnt || t[w[i]] == cnt && w[i] < v) {
cnt = t[w[i]];
v = w[i];
}
}
del(t, l, r);
return v;
}
for (int i = l; i <= ed[x]; ++i) t[w[i]]++;
for (int i = st[y]; i <= r; ++i) t[w[i]]++;
int ans = f[x + 1][y - 1];
for (int i = l; i <= ed[x]; ++i) {
int a = t[ans] + s[y - 1][ans] - s[x][ans];
int b = t[w[i]] + s[y - 1][w[i]] - s[x][w[i]];
if (b > a || (a == b && w[i] < ans)) ans = w[i];
}
for (int i = st[y]; i <= r; ++i) {
int a = t[ans] + s[y - 1][ans] - s[x][ans];
int b = t[w[i]] + s[y - 1][w[i]] - s[x][w[i]];
if (b > a || (a == b && w[i] < ans)) ans = w[i];
}
del(t, l, ed[x]);
del(t, st[y], r);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> w[i], vec.push_back(w[i]);
init();
for (int i = 1; i <= n; ++i) w[i] = find(w[i]);
for (int i = 1; i <= bcnt; ++i) {
for (int j = st[i]; j <= ed[i]; ++j) s[i][w[j]]++;
// 加上前面块的, 累计前缀和
for (int j = 0; j < (int) vec.size(); ++j) s[i][j] += s[i - 1][j];
}
// 处理[i, j]块内的众数
for (int i = 1; i <= bcnt; ++i) {
for (int j = i; j <= bcnt; ++j) {
int tmp = f[i][j - 1];
for (int k = st[j]; k <= ed[j]; ++k) {
int a = s[j][w[k]] - s[i - 1][w[k]];
int b = s[j][tmp] - s[i - 1][tmp];
if (a > b || (a == b && w[k] < tmp)) tmp = w[k];
}
f[i][j] = tmp;
}
}
int last = 0;
while (m--) {
int l, r;
cin >> l >> r;
l = (l + last - 1) % n + 1;
r = (r + last - 1) % n + 1;
if (l > r) swap(l, r);
int ans = vec[query(l, r)];
cout << ans << '\n';
last = ans;
}
return 0;
}
京公网安备 11010502036488号