CONANGSS - Help Conan 8 !! Hurry up !!

no tags 

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
if (l <= 0 || r > n) exit(1);
in my code, and I received a RE(NZEC), perhaps there are something wrong with the data?

[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.

Edit: seems there's a rejudge. Many "Accepted" solutions (mine included) don't work now.

Last edit: 2009-07-03 03:53:18

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