is doing a contest. He comes across the following problem:
You have an array of
elements, indexed from
to
. There are
operations you need to perform on it.
Each operation is one of the following:
C x v
Change the-th element of the array to
.
S l r
Output the sum of all the elements from the-th to the
-th index, inclusive.
Q v
Output how many elements are less than or equal toin the array.
At any time, every element in the array is between and
(inclusive).
knows that one fast solution uses a Binary Indexed Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?
Input Specification
The first line has and
.
The second line has integers, the original array.
The next lines each contain an operation in the format described above.
Output Specification
For each S
or Q
operation, output the answer on its own line. Note that you may need to use 64-bit integers to store the answer.
Sample Input
10 10
4 8 4 5 6 3 2 2 8 1
C 7 6
Q 7
S 2 3
S 1 4
C 4 9
S 2 3
Q 6
C 3 9
S 6 7
Q 6
Sample Output
8
12
21
12
7
9
6
Comments
Someone should have told me that the largest element in the array is at most 100000, would have saved a lot of time implementing an order statistic tree.
It says in the problem statement.
Can someone take a look at my code, I am wrong answering on the first three cases and I don't know what the problem is.
Change
while(value <= N)
towhile(value <= maxvalue)
.Makes sense, thank you.
Is this talking about the test cases themselves or something that needs to be factored in the solution?
TLE
I know my solution is O(Mlog(N)), but it still seems I am TLEing. Could someone please tell me why this is happening? Thank you!
Edit: Turns out upper_bound and lower_bound are slow.
I'm just wondering, is my algorithm for solving the question wrong? I'm TLEing on 3 test cases, but I can't seem to figure out what's causing the problem.
It also happen to me
get rid of your exception checking cases.
I changed the exceptions to if and else statements, but it didn't change much.
EDIT: calculating values beforehand is always a good idea...
I submit the exact same code, but only one TLE's on cases...
Flushing output is not guaranteed to be a constant time on every judge.
I'm not sure what you mean? Does that mean my code is technically correct time-wise or?
Flushing means using
kobortor u snake going to level 3 on the same day i went to lvl 2 ;(
And the same day you went to lvl 2 awaykened and jefferyxiao went to lvl 4.
and the day before fataleagle went to lvl5 ;(
To be honest Fataleagle is just straight up OP.