A sequel to my last blog, a contest that I worked so hard for.

The link to the contest

Writing this contest is the most productive thing I've done over the last month or so. It was originally made for a school contest, but apparently it got cancelled, so I am left with several unused problems (and a bad mood). Some of the problems might take inspiration from other problems (only a bit), some are completely original.

I truly wish every participant will have a great time solving the problems. The difficulty is around Div.2. If this blog gains enough traction, I might do an editorial!

Given $$$n$$$ numbers of a permutation of $$$[0, 1, ..., n-1]$$$ $$$p_1, p_2, ..., p_n$$$.

Define a function $$$g(l, r, k)$$$ as follows:

• Define an array $$$c$$$ as: $$$c_i = \operatorname{MEX}(p[l+i:r+i])$$$ for $$$1\le i\le k$$$, where $$$p[x:y]$$$ denotes the subarray from $$$x$$$ to $$$y$$$.
• Return the sum of $$$\min(k,10^4)$$$ largest numbers from array $$$c$$$.

You are given $$$q$$$ queries of form $$$(l, r, k)$$$, print out $$$g(l, r, 1)+g(l, r, 2)+...+g(l, r, k)$$$.

Constraints:

$$$n, q \le 10^5$$$

$$$1 \le l \le r \lt n, r+k \le n$$$

Huge inspirations from 2163D2 - Diadrash (Hard Version)