Good Subsegments
Contest: Codeforces Round 493 (Div. 1)
Difficulty rating: 3000
Tags: data structures

A permutation $$$p$$$ of length $$$n$$$ is a sequence $$$p_1, p_2, \ldots, p_n$$$ consisting of $$$n$$$ distinct integers, each of which from $$$1$$$ to $$$n$$$ ($$$1 \leq p_i \leq n$$$) .

Let's call the subsegment $$$[l,r]$$$ of the permutation good if all numbers from the minimum on it to the maximum on this subsegment occur among the numbers $$$p_l, p_{l+1}, \dots, p_r$$$.

For example, good segments of permutation $$$[1, 3, 2, 5, 4]$$$ are:

- $$$[1, 1]$$$,
- $$$[1, 3]$$$,
- $$$[1, 5]$$$,
- $$$[2, 2]$$$,
- $$$[2, 3]$$$,
- $$$[2, 5]$$$,
- $$$[3, 3]$$$,
- $$$[4, 4]$$$,
- $$$[4, 5]$$$,
- $$$[5, 5]$$$.

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$.

You need to answer $$$q$$$ queries of the form: find the number of good subsegments of the given segment of permutation.

In other words, to answer one query, you need to calculate the number of good subsegments $$$[x \dots y]$$$ for some given segment $$$[l \dots r]$$$, such that $$$l \leq x \leq y \leq r$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 120000$$$) — the number of elements in the permutation.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ separated by spaces ($$$1 \leq p_i \leq n$$$).

The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 120000$$$) — number of queries.

The following $$$q$$$ lines describe queries, each line contains a pair of integers $$$l$$$, $$$r$$$ separated by space ($$$1 \leq l \leq r \leq n$$$).

Output format:
Print a $$$q$$$ lines, $$$i$$$-th of them should contain a number of good subsegments of a segment, given in the $$$i$$$-th query.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Example input:
5
1 3 2 5 4
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

Example output:
1
2
5
6
10
1
3
4
7
1
2
4
1
3
1

Editorial:
Let's look at two solutions for all array, and each of them can be upgraded to subquadratic time for queries on subsegments.
First solution is Divide&Conquer.
Let's take a middle of the array and find number of segments, that contain it.
If minimum and maximum are at one side of middle, then by the end on the half where they are, you can restore the entire segment and check that it is correct (and remember it somewhere).
Else let them be on different sides.
Then let maximum will be at the right (other case are symmetric and you can solve them similarly), so we need $$$r - l = \max - \min$$$, but we already know $$$r$$$ and $$$\max$$$ , so we can get $$$r - \max = l - \min$$$.
Then let's partite the elements into equivalence classes, where we broke into classes by $$$r - \max$$$ if element on the left and $$$l - \min$$$ if element on the right (where the $$$\max$$$ and $$$\min$$$ is the minimum and maximum on the segment to the middle $$$m$$$), then the segment $$$l \leq m < r$$$ (where the maximum on the left) is good if and only if when in the interval $$$[l \dots m]$$$ there are no numbers less than minimum on the interval $$$(m, \dots r]$$$ and the interval $$$(m, \dots r]$$$ has no numbers larger than maximum on the interval $$$[l \dots m]$$$, and $$$l$$$ and $$$r$$$ are in the same class.
Then, for one segment end, some interval of elements from its class is suitable (these intervals can be selected, for example, by stack or a binary search).
Also you need (don't forget it!) to go recursively to the left half and to the right half :)
And then you can apply the Mo's algorithm!
Let's move the left and right ends, run through the classes where this end lies, and add/subtract from the answer the size of the intersection of the interval of this class that fits this end and the interval of this class that current segment now contains, so this part works for $$$O(n \sqrt{n} \log {n})$$$ (but operations are not so heavy, so it is working fast).
Also you need to not forget about the segments where the minimum and maximum contained at one side of the middle, they can be processed, for example, by passing with a sweep line with a fenwick tree, this part works in $$$O(n \log {n})$$$.
So we can upgrade D&C idea to $$$O(n \sqrt{n} \log {n})$$$.

But let's look at the geometric interpretation of the problem.
Let good segments be points $$$(l, r)$$$ on the plane!
Then the query is just the sum on the rectangle $$$[1 \dots l] [r \dots n]$$$.
To solve the problem on the whole array, let's move the right end of the query, and for each left we will store $$$r - l - (\max - \min)$$$, this can be stored in the segment tree (and you can recalculate it with stacks), and then you can note that values always are $$$ \leq 0$$$, so you can simply store in the segment tree the maximum and number of maximums, and at each time add this value to the answer.
In order to generalize this idea for a complete solution, let's split the field $$$N \times N$$$ into squares $$$K \times K$$$

(Colors are not important, they are just for convenience).
Then let's go with the same sweep line from left to right, but we will store everything not in the segment tree, but in the sqrt decomposition.
And we will store for a piece of size $$$K$$$ by $$$y$$$-coordinate the number of (good segments) points that we have already met in it.
So we can cut off from the original query

The lower part, leaving a horizontal strip of size $$$\leq K$$$.

We made it in $$$O(n \cdot k + n \cdot \frac{n}{k})$$$.
With similar sweep line from top to bottom, and not from left to right, we can cut off the left part, leaving as a query a rectangle with sides $$$< K$$$.

Then you can create $$$< K$$$ events of the form: "Add the sum on the vertical segment to the answer to $$$i$$$-th query", and these events can be processed by a sweep line from left to right with the segment tree , so you can solve this part in $$$O(n \cdot k \cdot \log{n})$$$.
So we can get a solution in $$$O(n \cdot \frac{n}{k} + n \cdot k \cdot \log{n})$$$, and choosing $$$k = \sqrt{\frac{n}{\log{n}}}$$$ allows to solve the task in $$$O(n \cdot \sqrt{n \cdot \log{n}})$$$.