Which ones are suitable? If the length of the segment is less than $$$k-1$$$, obviously the segment is bad. If the left border on the right of $$$r - k + 1$$$ or the right border on the left of $$$l + k - 1$$$, then the segment is also bad. It is not difficult to notice that these conditions are enough. It is still not difficult to understand that there is no segment whose length is not less than $$$k - 1$$$ and conditions 2 and 3 are satisfied simultaneously. This gives us the opportunity to count them individually. Lets $$$S$$$ is the size of the set. $$$K1$$$ — the number of left borders which is placed on the right of $$$r - k + 1$$$. $$$K2$$$ — the number of right borders which is placed on left of $$$l + k - 1$$$. Then the answer is $$$S - K1 - K2$$$. There is such a trick, the so-called “sqrt decomposition on queries”. If you need any non-dynamic structure in the task (static list, prefix sums, etc.), you can build it completely a new once per square root steps, and process non-added requests separately (their number is not greater than the root). In this task, you need to do the same, but in the role of a static structure, we will have sqrt decomposition. We have a list of segments sorted in descending order of length. We divide it into blocks of size $$$B$$$. In each block we will keep a list of right and left borders, also in sorted form. In all blocks where the length of each segment is not less than $$$k - 1$$$, we calculate the answer using a bin search. And in a block where the length of the segments is only partially suitable, and there is only one such block, we will consider it stupid.

General solution: Processing the $$$i$$$-th request: If type 1 or 2, then we remember this request (add to the list of not added requests). Otherwise: we’ll go over the list of not added requests + we consider the answer in our structure. If $$$i$$$ is divisible by $$$K$$$, then we rebuild the sqrt decomposition and clear the list of not added ones.

Time complexity; Time complexity depends on the constants $$$B$$$ and $$$K$$$. The total sqrt decomposition rebuild time works for $$$O ((n / K) * n * log).$$$ The total response time for $$$O (n * (n / B) * log)$$$. If you make $$$B$$$ and $$$K$$$ equal $$$sqrt (N * log)$$$, then the solution works for $$$O (n * sqrt (N * log)).$$$