Manhattan Subarrays (Codeforces 1550C)
Tags: Greedy, geometry

Suppose you have two points $$$p = (x_p, y_p)$$$ and $$$q = (x_q, y_q)$$$. Let's denote the Manhattan distance between them as $$$d(p, q) = |x_p - x_q| + |y_p - y_q|$$$.Let's say that three points $$$p$$$, $$$q$$$, $$$r$$$ form a bad triple if $$$d(p, r) = d(p, q) + d(q, r)$$$.Let's say that an array $$$b_1, b_2, \dots, b_m$$$ is good if it is impossible to choose three distinct indices $$$i$$$, $$$j$$$, $$$k$$$ such that the points $$$(b_i, i)$$$, $$$(b_j, j)$$$ and $$$(b_k, k)$$$ form a bad triple.You are given an array $$$a_1, a_2, \dots, a_n$$$. Calculate the number of good subarrays of $$$a$$$. A subarray of the array $$$a$$$ is the array $$$a_l, a_{l + 1}, \dots, a_r$$$ for some $$$1 \le l \le r \le n$$$.Note that, according to the definition, subarrays of length $$$1$$$ and $$$2$$$ are good.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the number of good subarrays of array $$$a$$$.

Note: In the first test case, it can be proven that any subarray of $$$a$$$ is good. For example, subarray $$$[a_2, a_3, a_4]$$$ is good since it contains only three elements and:   $$$d((a_2, 2), (a_4, 4)) = |4 - 3| + |2 - 4| = 3$$$ $$$<$$$ $$$d((a_2, 2), (a_3, 3)) + d((a_3, 3), (a_4, 4)) = 3 + 1 + 2 + 1 = 7$$$;  $$$d((a_2, 2), (a_3, 3))$$$ $$$<$$$ $$$d((a_2, 2), (a_4, 4)) + d((a_4, 4), (a_3, 3))$$$;  $$$d((a_3, 3), (a_4, 4))$$$ $$$<$$$ $$$d((a_3, 3), (a_2, 2)) + d((a_2, 2), (a_4, 4))$$$; In the second test case, for example, subarray $$$[a_1, a_2, a_3, a_4]$$$ is not good, since it contains a bad triple $$$(a_1, 1)$$$, $$$(a_2, 2)$$$, $$$(a_4, 4)$$$:   $$$d((a_1, 1), (a_4, 4)) = |6 - 9| + |1 - 4| = 6$$$;  $$$d((a_1, 1), (a_2, 2)) = |6 - 9| + |1 - 2| = 4$$$;  $$$d((a_2, 2), (a_4, 4)) = |9 - 9| + |2 - 4| = 2$$$; So, $$$d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 4))$$$.

Sample Inputs:
3
4
2 4 1 3
5
6 9 1 9 6
2
13 37

Sample Outputs:
10
12
3

Solution (Python):
import random
import math
from collections import defaultdict
import itertools
from sys import stdin, stdout
import sys
import operator
from decimal import Decimal
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def check(a, b, c):
    if b > a and b > c:
        return True
    elif b < a and b < c:
        return True

def main():
    for _ in range(int(input())):
        n = int(input())
        a = list(map(int, input().split()))
        ans = n + n - 1
        prev = 0
        for i in range(1, n - 1):
            if check(a[i - 1], a[i], a[i + 1]) == True:
                ans += 1
                if prev == 1:
                    if check(a[i - 2], a[i], a[i + 1]) == True and check(a[i - 2], a[i - 1], a[i + 1]) == True:
                        ans += 1
                prev = 1
            else:
                prev = 0
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    tot = 2 * n - 1
    for i in range(n - 2):
        tot += (arr[i] - arr[i + 1]) * (arr[i + 1] - arr[i + 2]) < 0
    for i in range(n - 3):
        tot += (arr[i + 1] - arr[i + 3]) * (arr[i + 3] - arr[i + 2]) > 0 and (arr[i + 1] - arr[i]) * (arr[i] - arr[i + 2]) > 0
    print(tot)

Solution (Python):
answers = []

def solve(n, arr):
    if n == 1:
        print(1)
        return
    if n == 2:
        print(3)
        return
    ans = 3
    for i in range(n - 3):
        ans += 2
        if arr[i] == arr[i + 1]:
            continue
        if arr[i] > arr[i + 1]:
            if arr[i + 1] >= arr[i + 2]:
                continue
            ans += 1
            if arr[i + 2] <= arr[i]:
                continue
            if arr[i + 2] > arr[i]:
                if arr[i + 3] >= arr[i + 2]:
                    continue
                if arr[i + 3] > arr[i + 1]:
                    ans += 1
        else:
            if arr[i + 1] <= arr[i + 2]:
                continue
            ans += 1
            if arr[i + 2] >= arr[i]:
                continue
            if arr[i + 2] < arr[i]:
                if arr[i + 3] <= arr[i + 2]:
                    continue
                if arr[i + 3] < arr[i + 1]:
                    ans += 1
    f = n - 3
    ans += 2
    one = arr[n - 3]
    sec = arr[n - 2]
    thi = arr[n - 1]
    if one > sec and thi > sec:
        ans += 1
    if one < sec and thi < sec:
        ans += 1
    print(ans)
T = int(input())
while T:
    n = int(input())
    arr = [int(x) for x in input().split()]
    solve(n, arr)
    T -= 1
for ans in answers:
    print(ans)