So, the first idea that is coming into mind is prefix sums. Let's define two values $$$l_i=max(0,a_i−a_i+1)$$$ and $$$r_i=max(0,a_i+1−a_i)$$$. The value $$$l_i$$$ means the amount of fall damage when we are going to the right from the column $$$i$$$ to the column $$$i$$$+$$$1$$$, and $$$r_i$$$ means the amount of fall damage when we are going to the left from the column $$$i$$$+$$$1$$$ to the column $$$i$$$. Then let's build prefix sums on these two arrays. Now let $$$p_{l_i}$$$ be the sum of all li on a prefix [0;i) (i. e. $$$p_{l_0}$$$=0), and $$$p_{r_i}$$$ be the sum of all $$$r_i$$$ on a $$$prefix [0;i)$$$. Then if $$$s<t$$$ in a query, the answer is $$$pl_{t−1}$$$ − $$$pl_{s−1}$$$, otherwise (if $$$s>t$$$) the answer is $$$pr_{s−1}$$$ − $$$pr_{t−1}$$$.

Time complexity: $$$O(n)$$$.

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = [0] + [max(0, a[i] - a[i + 1]) for i in range(n - 1)]
r = [0] + [max(0, a[i] - a[i - 1]) for i in range(1, n)]
for i in range(n - 1):
    l[i + 1] += l[i]
    r[i + 1] += r[i]
for _ in range(m):
    s, t = map(int, input().split())
    if s < t:
        print(l[t - 1] - l[s - 1])
    else:
        print(r[s - 1] - r[t - 1])

From the condition about the fact that each vertex equally respects all its ancestors, we can understand that each vertex is either always a candidate for deletion or it can never be deleted. That is because when we delete some vertex all new vertices which become sons of it's parent are also disrespecting it.

Now we can iterate over all vertices and if it respects it's parent, we will remember that it's parent can not be deleted. And so we will get the answer.

from collections import defaultdict
from sys import stdin


def input(): return stdin.readline().strip()

N = int(input())

child = defaultdict(list)
respect = [0]*N

root = 0

for ch in range(N):
    p, c = map(int, input().split())
    p -= 1
    respect[ch] = c
    if p == -2:
        root = ch
        continue
    child[p].append(ch)

stack = [root]

ans = []

while stack:
    v = stack.pop()
    ok = respect[v]
    for ch in child[v]:
        stack.append(ch)
        if respect[ch] == 0:
            ok = False
    if ok:
        ans.append(v + 1)
if not ans:
    print(-1)
else:
    print(*sorted(ans))

We only need two segments to check if the answer is $$$YES$$$.

The claim is that if the answer exists, we can take the segment with the minimum right boundary and the segment with the maximum left boundary (let's denote these boundaries as $$$r_{1}$$$ and $$$l_{2}$$$). Therefore, if $$$r_{1}<l_{2}$$$, it is obvious that this pair of segments is suitable for us. Otherwise, all pairs of segments intersect because they have common points in the range $$$l_{2}…r_{1}$$$ .

To keep track of the maximum left and minimum right boundaries, we can use max heap and min heap respectively. Since we might lose track of some segments, we can keep the count of a segment using its boundaries.

import sys
from collections import defaultdict
from heapq import heappush, heappop
input = lambda: sys.stdin.readline().rstrip()

q = int(input())

# to keep track of deleted and duplicate segments
sgt_count = defaultdict(int)
mxheap = [] # to store the largest l value
mnheap = [] # to store the smallest r value

for _ in range(q):
    operation, l, r = input().split()
    l, r = int(l), int(r)

    if operation == '+':
        heappush(mxheap, (-l, r))
        heappush(mnheap, (r, l))
        sgt_count[(l, r)] += 1
    else:
        sgt_count[(l, r)] -= 1

    # remove segments from max heap if they no longer exists on sgt_count
    while mxheap:
            neg_left, right = mxheap[0]
            if sgt_count[(-neg_left, right)]:
                break

            else:
                heappop(mxheap)
    
    # remove segments from min heap if they no longer exists on sgt_count
    while mnheap:
        right, left = mnheap[0]
        if sgt_count[(left, right)]:
            break

        else:
            heappop(mnheap)

    # compare the smallest r value with the largest l value
    if mxheap and mnheap and -mxheap[0][0] > mnheap[0][0]:
        print('YES')
    else:
        print('NO')