gpt-4.1-2025-04-14· OpenAI
LMArena Human Preference 140K
code sqrt split rebuild with full reverse, erase, get query
- User
code sqrt split rebuild with full reverse, erase, get query
- Assistant
Dưới đây là template Sqrt Decomposition (Sqrt Split) với Rebuild hỗ trợ đầy đủ các thao tác:
- Reverse một đoạn
[l, r] - Erase phần tử tại vị trí
pos - Get giá trị tại vị trí
pos - Query tổng đoạn
[l, r](bạn có thể thay đổi sang min/max/any aggregate khác nếu muốn)
Tất cả các thao tác đều chạy trung bình
O(√N)nhờ chia block và rebuild khi cần thiết.
C++ Template Sqrt Split Rebuild
#include <bits/stdc++.h> using namespace std; const int BLOCK_SIZE = 400; // sqrt(1e5) ~ 316, chọn lớn hơn để giảm số block struct Block { vector<int> a; bool rev = false; // lazy reverse void push() { if (rev) { std::reverse(a.begin(), a.end()); rev = false; } } }; vector<Block> blocks; void rebuild() { vector<int> all; for (auto &b : blocks) { b.push(); all.insert(all.end(), b.a.begin(), b.a.end()); } blocks.clear(); for (int i = 0; i < (int)all.size(); i += BLOCK_SIZE) { Block b; b.a.assign(all.begin() + i, all.begin() + min(i + BLOCK_SIZE, (int)all.size())); blocks.push_back(b); } } pair<int, int> find_pos(int pos) { int idx = 0; while (idx < (int)blocks.size()) { int sz = blocks[idx].a.size(); if (pos < sz) return {idx, pos}; pos -= sz; idx++; } return {-1, -1}; // not found } // Reverse [l, r] (0-based, inclusive) void reverse_range(int l, int r) { if (l > r) return; int n = 0; for (auto &b : blocks) n += b.a.size(); if (r >= n) r = n - 1; if (l > r) return; int li, lj, ri, rj; tie(li, lj) = find_pos(l); tie(ri, rj) = find_pos(r); if (li == ri) { blocks[li].push(); reverse(blocks[li].a.begin() + lj, blocks[li].a.begin() + rj + 1); } else { blocks[li].push(); reverse(blocks[li].a.begin() + lj, blocks[li].a.end()); for (int i = li + 1; i < ri; ++i) { blocks[i].rev ^= 1; } blocks[ri].push(); reverse(blocks[ri].a.begin(), blocks[ri].a.begin() + rj + 1); // Swap blocks in the middle while (li + 1 < ri) { swap(blocks[li + 1], blocks[ri - 1]); li++; ri--; } } } // Erase at position pos (0-based) void erase(int pos) { int bi, bj; tie(bi, bj) = find_pos(pos); blocks[bi].push(); blocks[bi].a.erase(blocks[bi].a.begin() + bj); if (blocks[bi].a.empty()) { blocks.erase(blocks.begin() + bi); } if (blocks.size() > 0 && blocks[bi % blocks.size()].a.size() > 2 * BLOCK_SIZE) { rebuild(); } } // Get value at position pos (0-based) int get(int pos) { int bi, bj; tie(bi, bj) = find_pos(pos); blocks[bi].push(); return blocks[bi].a[bj]; } // Query sum on [l, r] (0-based, inclusive) long long query_sum(int l, int r) { if (l > r) return 0; int n = 0; for (auto &b : blocks) n += b.a.size(); if (r >= n) r = n - 1; if (l > r) return 0; int li, lj, ri, rj; tie(li, lj) = find_pos(l); tie(ri, rj) = find_pos(r); long long res = 0; if (li == ri) { blocks[li].push(); for (int i = lj; i <= rj; ++i) res += blocks[li].a[i]; } else { blocks[li].push(); for (int i = lj; i < (int)blocks[li].a.size(); ++i) res += blocks[li].a[i]; for (int i = li + 1; i < ri; ++i) { if (blocks[i].rev) { for (int j = (int)blocks[i].a.size() - 1; j >= 0; --j) res += blocks[i].a[j]; } else { for (int j = 0; j < (int)blocks[i].a.size(); ++j) res += blocks[i].a[j]; } } blocks[ri].push(); for (int i = 0; i <= rj; ++i) res += blocks[ri].a[i]; } return res; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<int> a(n); for (int &x : a) cin >> x; // Build blocks for (int i = 0; i < n; i += BLOCK_SIZE) { Block b; b.a.assign(a.begin() + i, a.begin() + min(i + BLOCK_SIZE, n)); blocks.push_back(b); } while (q--) { string op; cin >> op; if (op == "reverse") { int l, r; cin >> l >> r; // 0-based reverse_range(l, r); } else if (op == "erase") { int pos; cin >> pos; // 0-based erase(pos); } else if (op == "get") { int pos; cin >> pos; // 0-based cout << get(pos) << '\n'; } else if (op == "sum") { int l, r; cin >> l >> r; // 0-based cout << query_sum(l, r) << '\n'; } // Rebuild if too many blocks if ((int)blocks.size() > 2 * (n / BLOCK_SIZE + 2)) rebuild(); } }
Giải thích
- Block: Mỗi block lưu một đoạn con của mảng, có thể bị đảo ngược (lazy reverse).
- Rebuild: Khi block quá to hoặc quá nhiều block, ta gom lại thành các block đều nhau.
- find_pos: Tìm block và vị trí trong block ứng với chỉ số toàn cục.
- reverse_range: Đảo ngược đoạn
[l, r](có thể nằm trong 1 hoặc nhiều block). - erase: Xóa phần tử tại vị trí
pos. - get: Lấy giá trị tại vị trí
pos. - query_sum: Tính tổng đoạn
[l, r].
Bạn có thể thay đổi hàm
query_sumthành min/max hoặc các aggregate khác tùy ý.
Nếu cần thêm các thao tác như insert, update, hãy hỏi tiếp nhé! - Reverse một đoạn
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.