FNCS - Editorial

I am getting forbidden error when I try to see setters solution. Looks like I am missing something

The message “Access Denied” is displayed to me when I try to view the Author and Tester’s solutions linked. Please fix?

nishantkumars …linear time complexity is too much for update operation…u need to reduce the complexity…

I’m wondering is there someone who user the limitation in subtask 2 where R - L <= 10?

It would help me if n - m <= 100 for example, but I had no idea how to use the one mentioned above…

I can solve it with complexity O(sqrt(max(N,Q))) per query and O(sqrt(max(N,Q))) per update.

We split all the operations we must perform in sqrt(Q) groups. We solve each group separately. Before starting with the current group we go through all update queries which happened before the group and update the array (in reality - just the updates in the previous group; others have already been counted). Then we extract all numbers which we will need to update in the current group and put 0 in their place in the array (there are at most sqrt(Q) such numbers). Then we answer all the queries in the group without looking at the updates in the group (this can be done in constant time per query if we precompute arrays with preffix sums).

What is left is the ammount updates in our group give. We transform each query [L,R] into two queries [0,R] and [0,L-1]. We go through the sum intervals from left to right. When we are at interval P we will answer queries [0,P]. Assume we have an array which can add number to interval in O(sqrt(N)) and get value at some index in O(1). So, for each sum interval (from left to right) we can add 1 to it and now when we are at interval P we will know how many intervals cover each number ( = how many times we must add the number to the query result). The remaining is simple - just go through all the numbers affected by updates in our group (which are at most sqrt(Q)) and add them with the correct count from the array above.

Array which can add number to interval in O(sqrt(N)) and get value at index in O(1) again is done with sqrt-decomposition.

I guess it won’t be very usefull, but here is my solution - CodeChef: Practical coding for everyone

2 Likes

As for authur’s solution,I wonder what the i is ? if it is the index of the bucket,how can we know occurrences of pos in range [1,x] , considering the array B is just one dimension,but you must deal with the pos and the x.I need HELP!!!

1 Like

"We can precompute this factor in O(N*sqrt(N)) space and time.

Thus, we can update this structure in O(sqrt(N)) by traversing through all the chunks and applying +(yfactor)-(prevfactor) at every chunk"

what does this mean???please someone elaborate this

Please explain in detail cant get your solution??

As we are undating only blocks …how would we get correct sum in case of incomplete block since we are not updating the actual functions with the given index ???
please explain…

Can you please elaborate on “No update version”? I am unable to understand the use of segment tree in that.

Can someone, please, post the test data for Task #2 (i.e. first test of the Sub-Task3)? This is the only test that I’m receiving WA. I’ve already tried many, many things and many, many random tests but I’m not able to find my mistake… I would really appreciate this specific test. Thanks a lot.

you can solve this problem with sqrt-decomposition on queries + persistent segment tree :slight_smile:
My solution: CodeChef: Practical coding for everyone

Anyone whose solution is failing for first test case of third subtask: Use unsigned long long instead of long long int whenever computing sum.

i tried an O(q log(n)sqrt(q)) solution that i couldn’t get to run in time. To know how many times a particular x occurs in range of functions [m,n], i used a persistent segment tree with pre-computation nlogn .
After every sqrt(q) queries i updated my prefix sum array.For each query i just visited all the updates within that chunk of queries. So, query was O(sqrt(q)log(n)) , while update was O(1).

yes, just keep a segment tree for the value of all functions so that you can query the sum of functions [m,n]. Also store the index of all functions starting from any given index in the original array.
On updating index x, you only need to update the functions that start from either x-1,x-2…,x-10 and ending at or after x. There can be O(n) such functions for a given x, but since x is unique total complexity will stay qlogn.

1 Like

Great, thanks for an answer, I misunderstood the x will be distinct part, I thought elements in A are distinct and it didn’t help me, suprisingly :smiley:

Although I didn’t use ‘all x are distinct’ constraint, I used the R-L<=10 part to keep a vector of vectors where vector[i] stores occurrences of index i in the intervals array. Then I divided the queries into square root(q) segments and for each segment, I applied brute force. For all queries of type 2 in a segment, I iterated over all queries of type 1 before it and checked which queries of type 1 affect the current type 2 query. For this, I binary searched in the vector[i] part of the index x of type 1 query to find no. of occurrences of this index in range [m,n] of type 2 query.

1 Like

I feel that, if x are not distinct it won’t fit, I need to think more abouot this. Thanks for you answer :wink:

Yeah you’re right about the distinct x part. Used it without knowing it!

1 ≤ Q,N ≤ 10^5. Worst case O(Q * N). Let’s say half of the queries are update queries. Then you would already have around 5 * 10^9 operations. That’s not something your computer can do in 2.5 seconds.