PROBLEM LINK:
Author: Mark Kornejchik
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
persistent segment tree, sqrt decomposition
(Note: I can’t find wikipedia articles for persistent segment tree, but this seems like a good tutorial to read. You can also google “persistent segment tree” for this topic. The editorial assumes familiarity with persistent segment tree.)
PROBLEM:
There are n intervals [l_i,r_i] where 1\le l_i\le r_i\le n. You have Q queries, where each query is given CNT distinct points x_1,x_2,\dots,x_{CNT}(1\le x_i\le n), and you need to output the number of good intervals. An interval is good if it crosses an odd number of query points. An interval [l,r] cross a point x if l\le x\le r.
QUICK EXPLANATION:
For a query of CNT points:
- if CNT\ge \sqrt{\frac{n}{\log n}}, then we use an O(n)-time brute force: we can count, for each interval [l_i,r_i], the number of points that it crosses, in a total time of O(n). Then we simply report the answer.
- if CNT<\sqrt{\frac{n}{\log n}}, then we use the following O(CNT^2\log n) algorithm: first we sort the points by ascending order, say they are x_1,x_2,\dots,x_{CNT}. We then enumerate the first and the last point x_i,x_j that’s crossed by the interval, ensuring that j-i is even(so there are odd points crossed); and look up how many intervals satisfy this condition. For an interval [l,r], this condition is equivalent to x_{i-1}+1\le l\le x_i and x_j\le r\le x_{j+1}-1, which can be maintained in a data structure to support O(\log n)-time queries.
EXPLANATION:
subtask 1
This subtask can be solved by straightforward brute force in O(N\cdot sum(CNT))=O(N^2) time.
subtask 2
a special case: CNT=1
In this special case, each query is a point x\in[1,N], and we’d like to find the number of intervals which crosses x. However, we’ll consider the following form of query, which will be useful later: given L_1,R_1,L_2,R_2, how many intervals [l_i,r_i] are there such that L_1\le l_i\le R_1 and L_2\le r_i\le R_2?
To answer such query, let’s build a persistent segment tree. The x-th root is a segment tree, and for a node which represents [L,R] in this tree, it stores the number of intervals with l_i\le x and r_i\in[L,R]. It can be constructed by the following pseudocode:
sort the intervals such that l_1<=l_2<=...<=l_n
j = 1
for i = 1 to n
(root of i-th tree) = (root of (i-1)-th tree)
while (l_j <= i)
insert r_j into (root of i-th tree)
j = j + 1
Let f(a,L_2,R_2) be the number of intervals with l_i\le a and L_2\le r_i\le R_2. We can query f(a,L_2,R_2) in O(\log n) time: we simply query the sum of [L_2,R_2] in the a-th tree. Then we can answer the above query (L_1,R_1,L_2,R_2): the answer is simply f(R_1,L_2,R_2)-f(L_1-1,L_2,R_2).
the solution
We set a parameter S=O(\sqrt{\frac{n}{\log n}}).
If CNT\le S, then we sort the points as x_1 < x_2 < \dots < x_{CNT}, and enumerate L,R such that 1\le L\le R\le CNT and R-L is even. We can find the number of intervals such that [l_i,r_i]\cap \{x_1,\dots,x_{CNT}\}=\{x_j:j\in [L,R]\}. This is simply done by a query (x_{L-1}+1,x_L,x_R,x_{R+1}-1). This takes O(CNT^2\log n)=O(CNT\sqrt{n\log n}) time.
If CNT>S, the query can be answered by brute force: we let s[i] equal to the number of x_j's such that x_j\le i, and the number of points [l_i,r_i] crosses is just s[r_i]-s[l_i-1]. This takes O(n)=O(CNT\sqrt{n\log n}) time.
The total time complexity is O(n\sqrt{n\log n}).
ALTERNATIVE SOLUTION:
Please feel free to share your approaches 
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
