Hello, I have a problem and some variations on it that I would like to share. At the moment, I don't know solutions to all the problems, so any ideas/solutions are welcomed in the comments.
Problem 0: You are given an array $$$A$$$ of $$$n$$$ integers, and $$$q$$$ queries of the form "$$$l$$$ $$$r$$$ $$$x$$$" and each number in $$$A[l...r]$$$ appear either once or twice. For each query you have to print the number of elements $$$A_j$$$ $$$(l \le j \le r)$$$ such that $$$A_j \lt x$$$, and the number $$$A_j$$$ appears exactly once in $$$A[l...r]$$$.
Problem 1: The same as Problem 0, but without the restriction that each number in $$$A[l...r]$$$ appear either once or twice.
Problem 2: The same as Problem 1, but with the following change in the queries: "an odd number of times" instead of "exactly once".
Problem 3: The same as Problem 0, but we have updates of the form "$$$i$$$": swap $$$A_i$$$ and $$$A_{i + 1}$$$.
Problem 3.5: The same as Problem 0, but we have updates of the form "$$$i$$$ $$$j$$$": swap $$$A_i$$$ and $$$A_j$$$.
Problem 4: The same as Problem 1, but we have updates that change single elements (e.g. $$$A_i := x$$$, $$$A_i := A_i + x$$$, or some combination of updates like these).
Problem 5: The same as Problem 2, but we have updates that change single elements.
Problem 6: The same as Problem 1, but we have updates that change the elements of ranges (e.g. $$$A_i := A_i + x$$$ for $$$(l \le i \le r)$$$, $$$A_i := min(A_i, x)$$$ for $$$(l \le i \le r)$$$, or some combination of updates like these).
Problem 7: The same as Problem 2, but we have updates that change the elements of ranges.
Time limit: ~4s
Memory limit: 256MB~512MB.
$$$(1 \le n, q \le 500 \space 000, 1 \le A_i \le 10^9)$$$
I'm not sure how hard/easy these problems are. I'll update the blog with founded solutions in the future.
Some of those problems could be solved offline. For every index you can save all queries for which r = index. Then you can maintain +1 for every i such that there isn't any j for which a[i] = a[j] and i, j <= index, and -1 otherwise. And then you can just query sum of all range [l, index] for every l from queries with r = index. You can update segment tree when moving to index + 1 in logN, so complexity will be O(NlogN).
I think some problems can be solved with "merge sort tree", maybe updates with only one element with merge sort tree with set or map, but TL is tight
An idea for the first three problems:
If all query's range is 1 to n, and the value of x is different. I think the time complexity becomes O(N^2) or O(NQ).
My bad.
In Problem 0 and its descendants, do the numbers appear at most twice in the entire array or is it only guaranteed that they will appear at most twice in all the queried segments?
In the queried segments. Does it matter other than if you want do some preprocessing on the array before the queries?
I think, that TLs for this problems are too tight, seems like only O(log n)/query solutions will fit (although even some O(log n) solutions will not be able to pass TL for n=500000). But your problems are really interesting :)
Thank you! I don't really think 3s is that tight for even $$$Nlog^2N$$$ solutions, is it? I was a lot of times able to squeeze in solutions that does around 2e8 operations when TL was just 1s, so I think 3s shouldn't be that bad. Should I increase the TL to 4s? or maybe change 5e5 to 3e5?
Yes, I think it would be worth lowering the task limits for n and q a bit. In addition, there will be actually more than 2e8 operations, since the O(n log^2 n) estimate omits a constant that is at least 2 (because for each segtree query we visit at most 2 log n nodes). And even 2e8 operations is tight for C++ on Codeforces :)
Problem 0 idea: I think we can use Mo's algorithm to get the answer in $$$O(N*\sqrt{N}*\log_{2}N)$$$. $$$N*\sqrt{N}$$$ is from Mo's algorithm and $$$\log_{2}N$$$ is from Mo's add/remove. Here I used the map to get a count of numbers to get exactly how many elements appear exactly once. Since there are only n elements and q Xs we can combine them and compress them from ($$$1$$$ to $$$10^9$$$) -> ($$$1$$$ to $$$2*10^5$$$) now we can use an array instead of a map and it removes the $$$\log_{2}N$$$ factor. This means we can now solve the problem in $$$O(N*\sqrt{N})$$$. I think this approach can also be used in both problems 1 and 2.
$$$N = 5*10^5$$$ -> $$$N\sqrt{N} ~ 350*10^6$$$ if time is 1seconds it might be hard.
Won't you need something like BIT as well?
Maybe you can use sqrt decomposition (count $$$1$$$s on segment $$$[0,x - 1]$$$ in $$$O(\sqrt n)$$$, updates in $$$O(1)$$$.
Then you can try this ...
Can someone Reccomend some good problems for Range Queries at intermediate level ?
Feel free to try the first one or two problems here.
You can also find a collection of standard problems in the section "Range Queries" at https://cses.fi/problemset.
Problem 0 and 1 in O(nlgn): same idea as distinct value query in range, sort queries by right end point, hold BIT for answers of each left end point for current right end point, iterate from left to right and make most recent occurrence of each value equal 1 in bit and next most recent equal -1, all others equal 0.
Oops wxhtzdy already said :pensive:.
Problem 3-4 O(nlg^2n): think similar to above, but instead you had bit for every single right bound. Realize this each element would be set as 1, -1, or 0 for only 4 consecutive ranges of right bounds. Now, you can think of combinations of bits as 2d range, and use sparse 2d segtree with rectangle additions and queries (can be done similar to poi tetris). For point updates, adjust 1d rectangles along y axis for like 3 x positions, and for queries query 1d rectangles along x-axis. Of course compress and use sparse segtree.
Is there faster datastructure for setting segments parallel y-axis and querying number that intersect certain y in x-range?
Problem 5 O(n^(5/3)): Same as Mazaalai but Mo's with updates (I still cannot think nlgn for problem 2).
Problem 2/5 O(n^2/128 * lgn): Group values by groups of 128. Hold BITS that can get xor of range, and let each element correspond to a bit in binary values. Add then just take xors in range and add popcounts lol.
Do you need a 2D data structure for $$$l \le j \le r$$$ and $$$A_j \le x$$$?
Oh shoot forgot to deal with this :weary:. Guess add a log factor and do similar to my 2nd comment :(.