Friends and Subsequences (Codeforces 689D)
Tags: Others, binary search

Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows? Every one of them has an integer sequences a and b of length n. Being given a query of the form of pair of integers (l, r), Mike can instantly tell the value of  while !Mike can instantly tell the value of .Now suppose a robot (you!) asks them all possible different queries of pairs of integers (l, r) (1 ≤ l ≤ r ≤ n) (so he will make exactly n(n + 1) / 2 queries) and counts how many times their answers coincide, thus for how many pairs  is satisfied.How many occasions will the robot count?

Input: The first line contains only integer n (1 ≤ n ≤ 200 000).The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence a.The third line contains n integer numbers b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) — the sequence b.

Output: Print the only integer number — the number of occasions the robot will count, thus for how many pairs  is satisfied.

Note: The occasions in the first sample case are:1.l = 4,r = 4 since max{2} = min{2}.2.l = 4,r = 5 since max{2, 1} = min{2, 3}.There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.

Sample Inputs:
6
1 2 3 2 1 4
6 7 1 2 3 2

3
3 3 3
1 1 1

Sample Outputs:
2

0

Solution (Python):
from bisect import bisect
HISENTINEL = 10 ** 9 + 1
LOSENTINEL = -HISENTINEL

def main():
    length = int(input())
    a = [int(fld) for fld in input().strip().split()]
    b = [int(fld) for fld in input().strip().split()]
    print(countmaxminsubseq(a, b))

def countmaxminsubseq(a, b):
    (leq, lgt) = getleftbounds(a, b, 0)
    (req, rgt) = getleftbounds(reversed(a), reversed(b), 1)
    req = reverseindex(req)
    rgt = reverseindex(rgt)
    count = 0
    for (i, (leq1, lgt1, req1, rgt1)) in enumerate(zip(leq, lgt, req, rgt)):
        count += (leq1 - lgt1) * (rgt1 - i) + (i - leq1) * (rgt1 - req1)
    return count

def getleftbounds(a, b, bias):
    astack = [(HISENTINEL, -1)]
    bstack = [(LOSENTINEL, -1)]
    (leqarr, lgtarr) = ([], [])
    for (i, (aelt, belt)) in enumerate(zip(a, b)):
        while astack[-1][0] < aelt + bias:
            astack.pop()
        lgt = astack[-1][1]
        while bstack[-1][0] > belt:
            bstack.pop()
        if belt < aelt:
            leq = lgt = i
        elif belt == aelt:
            leq = i
            istack = bisect(bstack, (aelt, -2)) - 1
            lgt = max(lgt, bstack[istack][1])
        else:
            istack = bisect(bstack, (aelt, i)) - 1
            (val, pos) = bstack[istack]
            if val < aelt:
                lgt = leq = max(lgt, pos)
            else:
                leq = pos
                istack = bisect(bstack, (aelt, -2)) - 1
                (val, pos) = bstack[istack]
                lgt = max(lgt, pos)
                leq = max(leq, lgt)
        leqarr.append(leq)
        lgtarr.append(lgt)
        astack.append((aelt, i))
        bstack.append((belt, i))
    return (leqarr, lgtarr)

def reverseindex(rind):
    pivot = len(rind) - 1
    return [pivot - i for i in reversed(rind)]
main()

Solution (Python):
import math
import heapq
import bisect
import functools
import itertools
import collections
import os
import sys
from io import BytesIO, IOBase
from typing import List
MOD0 = 10 ** 9 + 7
MOD1 = 998244353
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
read_str = lambda : input().strip()
read_int = lambda : int(input())
read_ints = lambda : map(int, input().split())
read_list_ints = lambda : list(map(int, input().split()))
read_list_strs = lambda : input().strip().split()

def solve():
    n = read_int()
    a = read_list_ints()
    b = read_list_ints()
    (q_max, q_min) = (collections.deque(), collections.deque())
    idx = ans = 0
    for (i, (x, y)) in enumerate(zip(a, b)):
        while q_max and q_max[-1][0] <= x:
            q_max.pop()
        q_max.append((x, i))
        while q_min and q_min[-1][0] >= y:
            q_min.pop()
        q_min.append((y, i))
        while idx <= i and q_max[0][0] > q_min[0][0]:
            idx += 1
            while q_max and q_max[0][1] < idx:
                q_max.popleft()
            while q_min and q_min[0][1] < idx:
                q_min.popleft()
        if q_max and q_min and (q_max[0][0] == q_min[0][0]):
            ans += min(q_max[0][1], q_min[0][1]) - idx + 1
    print(ans)
solve()

Solution (Python):
import bisect
import copy
import gc
import itertools
from array import array
from fractions import Fraction
import heapq
import math
import operator
import os, sys
import profile
import cProfile
import random
import re
import string
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
from functools import reduce, lru_cache
from io import IOBase, BytesIO
from itertools import count, groupby, accumulate, permutations, combinations_with_replacement, product
from math import gcd
from operator import xor, add
from typing import List
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_int_tuple():
    return tuple(map(int, input().split()))

def read_int():
    return int(input())
if 'AW' in os.environ['COMPUTERNAME']:
    f = open('inputs', 'r')

    def input():
        return f.readline().rstrip('\r\n')

def solve(n, a, b):
    (mx, mn) = (deque(), deque())
    j = res = 0
    for (i, (x, y)) in enumerate(zip(a, b)):
        while mx and a[mx[-1]] <= x:
            mx.pop()
        mx.append(i)
        while mn and b[mn[-1]] >= y:
            mn.pop()
        mn.append(i)
        while j <= i and a[mx[0]] > b[mn[0]]:
            j += 1
            while mx and mx[0] < j:
                mx.popleft()
            while mn and mn[0] < j:
                mn.popleft()
        if mx and mn and (a[mx[0]] == b[mn[0]]):
            res += min(mx[0], mn[0]) - j + 1
    return res

def main():
    for _ in range(1):
        n = read_int()
        a = read_int_list()
        b = read_int_list()
        print(solve(n, a, b))
if __name__ == '__main__':
    main()