Nguồn đề bài: http://vn.spoj.com/problems/GSS/ 1. Đề bài GSS SPOJ Cho dãy số a[1], a[2], …, a[n] (|a[i]| <= 15000, n <= 50000). Hàm q(x, y) = max { tổng(a[i]+a[i+1]+…+a[j]), x <= i <= j <= y }. Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính […]
Interval Tree
NKINV spoj – Dãy nghịch thế (cây IT)
Nguồn đề bài: http://vn.spoj.com/problems/NKINV/ 1. Đề bài NKINV spoj Cho một dãy số a1.. aN. Một nghịch thế là một cặp số u, v sao cho u < v và au > av. Nhiệm vụ của bạn là đếm số nghịch thế. Dữ liệu Dòng đầu ghi số nguyên dương N. N dòng sau mỗi dòng ghi […]
ORDERSET spoj – Order statistic set
Nguồn đề bài: http://vn.spoj.com/problems/ORDERSET/ 1. Đề bài ORDERSET spoj Tập hợp thứ tự Bạn cần quản lý một tập hợp động các số, hỗ trợ hai thao tác cơ bản: INSERT(S,x): nếu x không thuộc S, thêm x vào S DELETE(S,x): nếu x thuộc S, xóa x khỏi S và hai loại truy vấn K-TH(S) : trả […]
QMAX2 spoj – Giá trị lớn nhất ver2
Nguồn đề bài: http://vn.spoj.com/problems/QMAX2/ 1. Đề bài QMAX2 spoj Giống bài “Giá trị lớn nhất” ở trên. Input – n: số phần tử của dãy (n <= 50000). – m: số lượng biến đổi và câu hỏi (m <= 100000). +) biến đổi có dạng: 0 x y value +) câu hỏi có dạng : 1 x […]
QMAX spoj – Giá trị lớn nhất
Nguồn đề bài: http://vn.spoj.com/problems/QMAX/ 1. Đề bài QMAX spoj Cho một dãy gồm n phần tử có giá trị ban đầu bằng 0. Cho m phép biến đổi, mỗi phép có dạng (u, v, k): tăng mỗi phần tử từ vị trí u đến vị trí v lên k đơn vị. Cho q câu hỏi, mỗi câu […]
NKLINEUP spoj – Xếp hàng
Nguồn đề bài: http://vn.spoj.com/problems/NKLINEUP/ 1. Đề bài BCLINEUP spoj PTIT Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 50000) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn […]
