Doremy's Drying Plan (Hard Version)
Contest: Codeforces Round 906 (Div. 1)
Difficulty rating: 2600
Tags: data structures, dp

The only differences between the two versions of this problem are the constraint on $$$k$$$, the time limit and the memory limit. You can make hacks only if all versions of the problem are solved.

Doremy lives in a rainy country consisting of $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$.

The weather broadcast predicted the distribution of rain in the next $$$m$$$ days. In the $$$i$$$-th day, it will rain in the cities in the interval $$$[l_i, r_i]$$$. A city is called dry if it will never rain in that city in the next $$$m$$$ days.

It turns out that Doremy has a special power. She can choose $$$k$$$ days, and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$2 \le m \le 2\cdot 10^5$$$, $$$2 \le k \le \min(10, m)$$$) — the number of cities, the number of days, and the number of days of rain that Doremy can prevent.

Then, $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the rain coverage on day $$$i$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output one integer — the maximum number of dry cities.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, if Doremy prevents

- rain $$$1,2$$$, then city $$$2$$$ will be dry;
- rain $$$2,3$$$, then no city will be dry;
- rain $$$1,3$$$, then no city will be dry;

So there is at most $$$1$$$ dry city.

In the second test case, if Doremy prevents

- rain $$$1,2$$$, then city $$$1,2$$$ will be dry;
- rain $$$2,3$$$, then city $$$4,5$$$ will be dry;
- rain $$$1,3$$$, then city $$$1,5$$$ will be dry.

So there are at most $$$2$$$ dry cities.

In the third test case, it is optimal to prevent rain $$$1,2,4,5$$$.

In the forth test case, there is always a day of rain that wets all the cities and cannot be prevented.

Example input:
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 4
1 5
6 10
2 2
3 7
5 8
1 4
100 6 5
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 3
9 20
3 3
10 11
11 13
6 18

Example output:
1
2
6
0
1000
17

Editorial:
$$$k$$$ is bigger in this version. However, it is still small, which leads us to a DP approach.
Let $$$dp_{i,j}$$$ be the number of uncovered positions in $$$[1,i]$$$, and the last uncovered position is $$$i$$$, and the number of deleted intervals is $$$j$$$.
For transition, we need to get all the intervals that covers position $$$i$$$. We've mentioned this in the editorial of the easy version.
Let's iterate the last uncovered position $$$t$$$, and calculate the number of intervals that need to be deleted in this transition. Let it be $$$d_t$$$ and it is the number of interval $$$[l,r]$$$ such that $$$t < l \le i \le r$$$. Check this for example:

And the transition goes:
$$$$$$ dp_{i,j} \gets 1 + \max_{t=0}^{i-1} dp_{t,j-d_t} $$$$$$
The time complexity is $$$O(n^2k)$$$ now. We need to speed the transition up.
Note that $$$d_t$$$ is increasing while $$$t$$$ is decreasing, and $$$d_t$$$ is at most $$$k$$$. It actually splits the transition interval $$$[0,i-1]$$$ into at most $$$k+1$$$ intervals $$$[s_0,s_1],[s_1+1,s_2],\cdots,[s_{l-1} + 1,s_l]$$$ such that $$$0=s_0 \le s_1 < s_2 < \cdots < s_l = i - 1$$$ and for $$$t$$$ in the same interval, $$$d_t$$$ is the same.
So the sparse table can be used for transition.
Time complexity $$$O(nk^2)$$$. Memory complexity $$$O(kn\log n)$$$.