Cập Nhật Đoạn, Truy Vấn Điểm

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Java, Python

Cho mảng $a$ gồm $n$ số nguyên (đánh số từ $0$ ). Ban đầu mảng được khởi tạo bằng $0$ . Cài đặt cấu trúc dữ liệu hỗ trợ hai thao tác:

Cập nhật đoạn: thêm $v$ vào tất cả các phần tử $a [l], a [l + 1], \dots, a [r]$ .
Truy vấn điểm: trả về giá trị $a [i]$ hiện tại.

Hàm cần cài đặt

Đây là bài toán signature grader. Bạn chỉ cần cài đặt ba hàm sau, không cần viết main() hay đọc/ghi dữ liệu.

Ngôn ngữ hỗ trợ: C/C++, Python, và Java.

C++

void init(int n);
void update(int l, int r, long long v);
long long query(int i);

Python

def init(n: int) -> None: ...
def update(l: int, r: int, v: int) -> None: ...
def query(i: int) -> int: ...

Java

public class Solution {
    public void init(int n) { ... }
    public void update(int l, int r, long v) { ... }
    public long query(int i) { ... }
}

Mô tả

init(n): Khởi tạo cấu trúc với $n$ phần tử, tất cả bằng $0$ .
update(l, r, v): Cộng $v$ vào $a [l], a [l + 1], \dots, a [r]$ .
query(i): Trả về giá trị hiện tại của $a [i]$ .

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
Tổng số thao tác $u p d a t e$ và $q u e r y$ : $\leq 2 \cdot 10^{5}$
$0 \leq l \leq r < n$
$| v | \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 5 U 0 2 3 Q 1 U 1 4 2 Q 2 Q 4	3 5 2	Sau $U (0, 2, 3)$ : $a = [3, 3, 3, 0, 0]$ . $a [1] = 3$ . Sau $U (1, 4, 2)$ : $a = [3, 5, 5, 2, 2]$ . $a [2] = 5$ , $a [4] = 2$ .

Bình luận

Không có bình luận tại thời điểm này.