数列分块入门
2025-12-28 11:39:56
发布于：广东
6阅读
0回复
0点赞
数列分块入门 1
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1);
int B = (int)sqrt(n); // 块大小
int m = (n + B - 1) / B; // 块数量
vector<int> bel(n + 1), L(m + 1), R(m + 1);
vector<long long> tag(m + 1, 0);
for (int b = 1; b <= m; b++) {
L[b] = (b - 1) * B + 1;
R[b] = min(n, b * B);
for (int i = L[b]; i <= R[b]; i++) bel[i] = b;
}
for (int i = 1; i <= n; i++) cin >> a[i];
auto add = [&](int l, int r, long long c) {
int bl = bel[l], br = bel[r];
if (bl == br) {
for (int i = l; i <= r; i++) a[i] += c;
} else {
for (int i = l; i <= R[bl]; i++) a[i] += c;
for (int i = L[br]; i <= r; i++) a[i] += c;
for (int b = bl + 1; b <= br - 1; b++) tag[b] += c;
}
};
while (n--) {
int opt, l, r;
long long c;
cin >> opt >> l >> r >> c;
if (opt == 0) add(l, r, c);
else cout << a[r] + tag[bel[r]] << "\n";
}
return 0;
}
数列分块入门 2
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int B = (int)sqrt(n), m = (n + B - 1) / B;
vector<int> pos(n + 1), L(m + 1), R(m + 1);
vector<long long> tag(m + 1);
vector<bool> flag(m + 1);
vector<vector<long long>> s(m + 1);
for (int b = 1; b <= m; b++) {
L[b] = (b - 1) * B + 1;
R[b] = min(n, b * B);
for (int i = L[b]; i <= R[b]; i++) pos[i] = b;
}
auto rebuild = [&](int b) {
s[b] = vector<long long>(a.begin() + L[b], a.begin() + R[b] + 1);
sort(s[b].begin(), s[b].end());
};
for (int b = 1; b <= m; b++) rebuild(b);
auto add = [&](int l, int r, long long c) {
int bl = pos[l], br = pos[r];
flag[bl] = flag[br] = true;
if (bl == br) for (int i = l; i <= r; i++) a[i] += c;
else {
for (int i = l; i <= R[bl]; i++) a[i] += c;
for (int i = L[br]; i <= r; i++) a[i] += c;
for (int b = bl + 1; b < br; b++) tag[b] += c;
}
};
auto query = [&](int l, int r, long long x) {
int bl = pos[l], br = pos[r];
long long ans = 0;
if (bl == br) for (int i = l; i <= r; i++) ans += (a[i] + tag[bl] < x);
else {
for (int i = l; i <= R[bl]; i++) ans += (a[i] + tag[bl] < x);
for (int i = L[br]; i <= r; i++) ans += (a[i] + tag[br] < x);
for (int b = bl + 1; b < br; b++) {
if(flag[b]) rebuild(b), flag[b] = false;
ans += lower_bound(s[b].begin(), s[b].end(), x - tag[b]) - s[b].begin();
}
}
return ans;
};
while (n--) {
int opt, l, r;
long long c;
cin >> opt >> l >> r >> c;
if (opt == 0) add(l, r, c);
else cout << query(l, r, c * c) << "\n";
}
return 0;
}
数列分块入门 3
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int B = (int)sqrt(n), m = (n + B - 1) / B;
vector<int> pos(n + 1), L(m + 1), R(m + 1);
vector<long long> tag(m + 1);
vector<bool> flag(m + 1);
vector<vector<long long>> s(m + 1);
for (int b = 1; b <= m; b++) {
L[b] = (b - 1) * B + 1;
R[b] = min(n, b * B);
for (int i = L[b]; i <= R[b]; i++) pos[i] = b;
}
auto rebuild = [&](int b) {
s[b] = vector<long long>(a.begin() + L[b], a.begin() + R[b] + 1);
sort(s[b].begin(), s[b].end());
};
for (int b = 1; b <= m; b++) rebuild(b);
auto add = [&](int l, int r, long long c) {
int bl = pos[l], br = pos[r];
flag[bl] = flag[br] = true;
if (bl == br) for (int i = l; i <= r; i++) a[i] += c;
else {
for (int i = l; i <= R[bl]; i++) a[i] += c;
for (int i = L[br]; i <= r; i++) a[i] += c;
for (int b = bl + 1; b < br; b++) tag[b] += c;
}
};
auto query = [&](int l, int r, long long x) {
int bl = pos[l], br = pos[r];
long long ans = -1e12;
if (bl == br) for (int i = l; i <= r; i++) {
if(a[i] + tag[bl] < x) ans = max(ans, a[i] + tag[bl]);
}
else {
for (int i = l; i <= R[bl]; i++) if(a[i] + tag[bl] < x) ans = max(ans, a[i] + tag[bl]);
for (int i = L[br]; i <= r; i++) if(a[i] + tag[br] < x) ans = max(ans, a[i] + tag[br]);
for (int b = bl + 1; b < br; b++) {
if(flag[b]) rebuild(b), flag[b] = false;
auto p = lower_bound(s[b].begin(), s[b].end(), x - tag[b]);
if(p != s[b].begin()) ans = max(ans, *(p - 1) + tag[b]);
}
}
return ans;
};
while (n--) {
int opt, l, r;
long long c;
cin >> opt >> l >> r >> c;
if (opt == 0) add(l, r, c);
else {
long long res = query(l, r, c);
if(res == -1e12) cout << -1 << '\n';
else cout << res << '\n';
}
}
return 0;
}
数列分块入门 4
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int B = (int)sqrt(n), m = (n + B - 1) / B;
vector<int> pos(n + 1), L(m + 1), R(m + 1);
vector<long long> tag(m + 1, 0), sum(m + 1, 0);
for (int b = 1; b <= m; b++) {
L[b] = (b - 1) * B + 1;
R[b] = min(n, b * B);
for (int i = L[b]; i <= R[b]; i++) pos[i] = b;
}
for (int b = 1; b <= m; b++)
for (int i = L[b]; i <= R[b]; i++) sum[b] += a[i];
auto add = [&](int l, int r, long long c) {
int bl = pos[l], br = pos[r];
if (bl == br) {
for (int i = l; i <= r; i++) a[i] += c;
sum[bl] += c * (r - l + 1);
} else {
for (int i = l; i <= R[bl]; i++) a[i] += c;
sum[bl] += c * (R[bl] - l + 1);
for (int i = L[br]; i <= r; i++) a[i] += c;
sum[br] += c * (r - L[br] + 1);
for (int b = bl + 1; b < br; b++) tag[b] += c;
}
};
auto query = [&](int l, int r) {
int bl = pos[l], br = pos[r];
long long ans = 0;
if (bl == br) for (int i = l; i <= r; i++) ans += a[i] + tag[bl];
else {
for (int i = l; i <= R[bl]; i++) ans += a[i] + tag[bl];
for (int i = L[br]; i <= r; i++) ans += a[i] + tag[br];
for (int b = bl + 1; b < br; b++) ans += sum[b] + tag[b] * (R[b] - L[b] + 1);
}
return ans;
};
while (n--) {
int opt, l, r;
long long c;
cin >> opt >> l >> r >> c;
if (opt == 0) add(l, r, c);
else cout << (query(l, r) % (c + 1) + c + 1) % (c + 1) << "\n";
}
return 0;
}
数列分块入门 5
#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
const int N = 3e5 + 5;
int n, a[N];
long long t[N];
int lowbit(int x) { return x & -x; }
void add(int id, int x) {
while(id <= n)
t[id] += x, id += lowbit(id);
}
long long query(int id) {
long long res = 0;
while(id) res += t[id], id -= lowbit(id);
return res;
}
set<int> s;
//=====================================
signed main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
clock_t c1 = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
//=====================================
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i]);
if(a[i] > 1) s.insert(i);
}
for(int i = 1; i <= n; i++) {
int opt, l, r;
cin >> opt >> l >> r;
if (opt == 0) {
auto it = s.lower_bound(l);
while (it != s.end() && *it <= r) {
int pos = *it, nv = sqrt(a[pos]); // floor sqrt
add(pos, nv - a[pos]);
a[pos] = nv;
if (a[pos] <= 1) it = s.erase(it); // erase 返回下一个迭代器
else ++it;
}
}
else cout << query(r) - query(l - 1) << '\n';
}
//=====================================
#ifdef LOCAL
cerr << "Time used: " << clock() - c1 << " ms" << '\n';
#endif
return 0;
}
数列分块入门 6
#include <bits/stdc++.h>
using namespace std;
const int B = 700;
int main() {
int n;
cin >> n;
vector<vector<int>> blk;
vector<int> cur;
for (int i = 0, x; i < n; i++) {
cin >> x;
cur.push_back(x);
if (cur.size() == B) {
blk.push_back(cur);
cur.clear();
}
}
if (!cur.empty()) blk.push_back(cur);
auto split = [&](int id) {
if (blk[id].size() <= 2 * B) return;
// 若某块太大，分裂成两块
int mid = blk[id].size() / 2;
vector<int> nb(blk[id].begin() + mid, blk[id].end());
blk[id].erase(blk[id].begin() + mid, blk[id].end());
blk.insert(blk.begin() + id + 1, nb);
};
auto locate = [&](int k) {
// 返回 (所在块的索引, 块内元素索引)
int id = 0;
while (id < blk.size()) {
int s = blk[id].size();
if (k <= s) return pair<int,int>(id, k - 1);
k -= s;
id++;
}
return make_pair(-1, -1);
};
for (int i = 0; i < n; i++) {
int opt;
cin >> opt;
if (opt == 0) {
int l, r;
cin >> l >> r;
auto [bid, idx] = locate(l);
blk[bid].insert(blk[bid].begin() + idx, r);
split(bid);
} else {
int c;
cin >> c;
auto [bid, idx] = locate(c);
cout << blk[bid][idx] << "\n";
}
}
return 0;
}
数列分块入门 7
#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
int main() {
int n;
cin >> n;
int B = sqrt(n), tot = (n + B - 1) / B;
vector<int> bel(n + 1), L(tot + 1), R(tot + 1);
vector<int> a(n + 1), tagMul(tot + 1, 1), tagAdd(tot + 1);
for (int i = 1; i <= n; i++) cin >> a[i], a[i] %= MOD;
for (int i = 1; i <= tot; i++) {
L[i] = (i - 1) * B + 1, R[i] = min(i * B, n);
for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
}
auto push_down = [&](int b) {
if (tagMul[b] == 1 && tagAdd[b] == 0) return;
for (int i = L[b]; i <= R[b]; i++)
a[i] = ((a[i] * tagMul[b]) % MOD + tagAdd[b]) % MOD;
tagMul[b] = 1, tagAdd[b] = 0;
};
auto add = [&](int l, int r, int c) {
int bl = bel[l], br = bel[r];
push_down(bl), push_down(br);
if(bl == br) for(int i = l; i <= r; i++) (a[i] += c) %= MOD;
else {
for (int i = l; i <= R[bl]; i++) (a[i] += c) %= MOD;
for (int i = L[br]; i <= r; i++) (a[i] += c) %= MOD;
for (int b = bl + 1; b <= br - 1; b++) (tagAdd[b] += c) %= MOD;
}
};
auto mul = [&](int l, int r, int c) {
int bl = bel[l], br = bel[r];
push_down(bl), push_down(br);
if(bl == br) for(int i = l; i <= r; i++) (a[i] *= c) %= MOD;
else {
for (int i = l; i <= R[bl]; i++) (a[i] *= c) %= MOD;
for (int i = L[br]; i <= r; i++) (a[i] *= c) %= MOD;
for (int b = bl + 1; b <= br - 1; b++)
(tagMul[b] *= c) %= MOD, (tagAdd[b] *= c) %= MOD;
}
};
auto query = [&](int x) {
return (((a[x] * tagMul[bel[x]]) % MOD + tagAdd[bel[x]]) % MOD + MOD) % MOD;
};
for (int i = 1; i <= n; i++) {
int opt, l, r, c;
cin >> opt >> l >> r >> c;
if (opt == 0) add(l, r, c % MOD);
else if (opt == 1) mul(l, r, c % MOD);
else cout << query(r) << '\n';
}
return 0;
}
数列分块入门 8
#include <bits/stdc++.h>
using namespace std;
const int NONE = 1e9 + 7;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
int B = sqrt(n), tot = (n + B - 1) / B;
vector<int> bel(n + 1), a(n + 1);
vector<int> L(tot + 1), R(tot + 1), tag(tot + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= tot; i++) {
L[i] = (i - 1) * B + 1, R[i] = min(i * B, n), tag[i] = NONE;
for(int j = L[i]; j <= R[i]; j++) bel[j] = i;
}
auto push_down = [&](int b) {
if(tag[b] == NONE) return;
for(int i = L[b]; i <= R[b]; i++) a[i] = tag[b];
tag[b] = NONE;
};
auto work = [&](int l, int r, int c) {
int bl = bel[l], br = bel[r], res = 0;
push_down(bl), push_down(br);
if(bl == br) {
for(int i = l; i <= r; i++) {
if(a[i] == c) res++;
a[i] = c;
}
return res;
}
for(int i = l; i <= R[bl]; i++) {
if(a[i] == c) res++;
a[i] = c;
}
for(int i = L[br]; i <= r; i++) {
if(a[i] == c) res++;
a[i] = c;
}
for(int b = bl + 1; b <= br - 1; b++) {
if(tag[b] == NONE) for(int i = L[b]; i <= R[b]; i++) res += (a[i] == c);
else res += (R[b] - L[b] + 1) * (tag[b] == c);
tag[b] = c;
}
return res;
};
for(int i = 1; i <= n; i++) {
int l, r, c;
cin >> l >> r >> c;
cout << work(l, r, c) << '\n';
}
return 0;
}
数列分块入门 9（普通莫队版本，会 TLE）
#include <bits/stdc++.h>
using namespace std;
using interval = struct { int l, r, id; };
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//=====================================
int n;
cin >> n;
int B = sqrt(n), tot = (n + B - 1) / B;
vector<int> a(n + 1), bel(n + 1), b(n), ans(n);
for(int i = 1; i <= n; i++) bel[i] = (i - 1) / B;
for(int i = 1; i <= n; i++) cin >> a[i], b[i - 1] = a[i];
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto getID = [&](int x) {
return (int)(lower_bound(b.begin(), b.end(), x) - b.begin());
};
vector<int> cnt(b.size());
vector<interval> q(n);
for(int i = 0; i < n; i++) cin >> q[i].l >> q[i].r, q[i].id = i;
sort(q.begin(), q.end(), [&](interval x, interval y) {
if(bel[x.r] == bel[y.r]) return bel[x.l] < bel[y.l];
return bel[x.r] < bel[y.r];
});
int l = 1, r = 0;
for(int i = 0; i < n; i++) {
while(r < q[i].r) cnt[getID(a[++r])]++;
while(r > q[i].r) cnt[getID(a[r--])]--;
while(l < q[i].l) cnt[getID(a[l++])]--;
while(l > q[i].l) cnt[getID(a[--l])]++;
int res = 0;
for(int j = 1; j < cnt.size(); j++)
if(cnt[j] > cnt[res]) res = j;
ans[q[i].id] = b[res];
}
for(int i = 0; i < n; i++) cout << ans[i] << '\n';
return 0;
}
这里空空如也
有帮助，赞一个