Skip to content
TheChatArchiveThe Chat Archive
gpt-4.1-2025-04-14· OpenAIHugging Face LMArena Human Preference 140K

code sqrt split rebuild with full reverse, erase, get query

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Qwenqwen3-235b-a22b’s answer.
  1. User

    code sqrt split rebuild with full reverse, erase, get query

  2. 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_sum thà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é!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.