CONANGSS - Help Conan 8 !! Hurry up !!
English | Vietnamese |
Dù đã tìm đủ mọi cách tự sát nhưng mà không thể nào tự sát được vì quá ngoan,Conan thất vọng tràn trề,quay trở lại với VOJ,nhìn những bài đã Accepted,Conan bỗng nảy ra một ý,tại sao không kết hợp những bài đó với nhau nhỉ,và cuối cùng anh đã quyết định kết hợp hai bài QMAX2 và GSS lại với nhau trở thành problem CONANGSS như sau :
Cho một dãy số n phần tử ( tất cả khởi tạo bằng 0 ),và m câu hỏi (n<=20.000,m<=20.000). Mỗi câu hỏi có dạng:
U u v val tức là tăng cả đoạn (u,v) lên val đơn vị ( val có thể âm )
Q u v ,khi gặp câu hỏi này bạn phải trả lời ra đoạn con có tổng lớn nhất trong đoạn (u,v) (Định nghĩa đoạn con giống bài GSS).
Input
-Dòng đầu ghi 2 số n,m
-m dòng sau mỗi dòng ghi 1 trong 2 loại câu hỏi như trên
Output
Với mỗi câu hỏi dạng Q in ra kết quả
Example
Input:
4 2
U 1 3 2
Q 1 4
Output:
6
Chú ý:Nghiêm cấm for trâu dưới mọi hình thức :))/
/
hide comments
Fish:
2012-02-07 05:54:07
I added
|
|
[Trichromatic] XilinX:
2009-08-08 15:55:38
Needn't use any data structures. O(1) for each update and O(m) for each query will lead to Accepted.
|
Added by: | ConanKudo |
Date: | 2008-07-15 |
Time limit: | 0.100s-6.734s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Own |