为什么
  • 板块P1001 A+B Problem
  • 楼主Spir1t
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/7/11 11:16
  • 上次更新2023/11/3 10:35:34
查看原帖
为什么
747009
Spir1t楼主2023/7/11 11:16

为什么40分

#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
private:
    vector<int> arr;
    vector<int> tree;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            build(leftChild, start, mid);
            build(rightChild, mid + 1, end);

            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            if (idx <= mid) {
                update(leftChild, start, mid, idx, val);
            } else {
                update(rightChild, mid + 1, end, idx, val);
            }

            tree[node] = tree[leftChild] + tree[rightChild];
        }
    }

    int query(int node, int start, int end, int left, int right) {
        if (start > right || end < left) {
            return 0;
        } else if (start >= left && end <= right) {
            return tree[node];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node;
            int rightChild = 2 * node + 1;

            int sumLeft = query(leftChild, start, mid, left, right);
            int sumRight = query(rightChild, mid + 1, end, left, right);

            return sumLeft + sumRight;
        }
    }

public:
    SegmentTree(vector<int>& arr) {
        this->arr = arr;
        this->tree.resize(4 * arr.size());
        build(1, 0, arr.size() - 1);
    }

    void update(int idx, int val) {
        update(1, 0, arr.size() - 1, idx, val);
    }

    int query(int left, int right) {
        return query(1, 0, arr.size() - 1, left, right);
    }
};

int main() {
    int a, b;
    cin >> a >> b;

    vector<int> arr(max(a, b), 0);
    SegmentTree tree(arr);

    tree.update(a - 1, a);
    tree.update(b - 1, b);

    int result = tree.query(0, arr.size() - 1);
    cout << result << endl;

    return 0;
}
2023/7/11 11:16
加载中...