Binary Indexed Tree Test

Points: 10 (partial)

Time limit: 1.4s

Memory limit: 256M

Problem type

Xyene is doing a contest. He comes across the following problem:

You have an array of $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~ elements, indexed from $1$ ~1~ to $N$ ~N~. There are $M$ ~M~ $(1 \le M \le 500\,000)$ ~(1 \le M \le 500\,000)~ operations you need to perform on it.

Each operation is one of the following:

C x v Change the $x$ ~x~-th element of the array to $v$ ~v~.
S l r Output the sum of all the elements from the $l$ ~l~-th to the $r$ ~r~-th index, inclusive.
Q v Output how many elements are less than or equal to $v$ ~v~ in the array.

At any time, every element in the array is between $1$ ~1~ and $100\,000$ ~100\,000~ (inclusive).

Xyene 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 $N$ ~N~ and $M$ ~M~.

The second line has $N$ ~N~ integers, the original array.

The next $M$ ~M~ 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

Comments

0

31501357 commented on March 18, 2022, 11:05 p.m.

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.

5

BalintR commented on March 19, 2022, 1:53 a.m.

It says in the problem statement.

At any time, every element in the array is between $1$ ~1~ and $100\,000$ ~100\,000~ (inclusive).

2

ross_cleary commented on March 29, 2020, 8:01 p.m.

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.

5

Dingledooper commented on March 29, 2020, 8:11 p.m.

Change while(value <= N) to while(value <= maxvalue).

3

ross_cleary commented on March 29, 2020, 8:34 p.m.

Makes sense, thank you.

2

faraz123 commented on March 29, 2020, 6:39 p.m. ← edited →

At any time, every element in the array is between 1 and 100000 (inclusive).

Is this talking about the test cases themselves or something that needs to be factored in the solution?

4

Cueball1234 commented on Feb. 17, 2018, 5:51 p.m. ← edited →

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.

1

minecraftyugi commented on Nov. 16, 2015, 3:15 a.m.

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.

0

Pimienta commented on Sept. 1, 2021, 5:37 a.m.

It also happen to me

1

kobortor commented on Nov. 16, 2015, 3:19 a.m.

get rid of your exception checking cases.

2

minecraftyugi commented on Nov. 16, 2015, 3:33 a.m. ← edited →

I changed the exceptions to if and else statements, but it didn't change much.

EDIT: calculating values beforehand is always a good idea...

1

pyrexshorts commented on March 8, 2015, 5:13 a.m.

I submit the exact same code, but only one TLE's on cases...

2

FatalEagle commented on March 8, 2015, 5:18 a.m.

Flushing output is not guaranteed to be a constant time on every judge.

1

pyrexshorts commented on March 8, 2015, 4:50 p.m.

I'm not sure what you mean? Does that mean my code is technically correct time-wise or?

3
kobortor commented on March 8, 2015, 4:53 p.m. ← edited →
Flushing means using

cout << endl;

1

bobhob314 commented on March 8, 2015, 5:58 p.m.

kobortor u snake going to level 3 on the same day i went to lvl 2 ;(

3

kobortor commented on March 9, 2015, 1:36 a.m.

And the same day you went to lvl 2 awaykened and jefferyxiao went to lvl 4.

4

awaykened commented on March 9, 2015, 10:40 p.m.

and the day before fataleagle went to lvl5 ;(

7

kobortor commented on March 9, 2015, 10:44 p.m.

To be honest Fataleagle is just straight up OP.