Transformación del problema

El problema se puede reformular como:

Determinar la centidad de subintervalos donde se cumple que Max - Min = r - l

Solución por fuerza bruta

Aprvoechando la propiedad anterior, podemos iterar todos los posibles intervalos y verificar si cumplen con la condición.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 50005;
int elementos[MAXN], logaritmo[MAXN];
int maximo[MAXN][17], minimo[MAXN][17];
int tam;

void inicializar() {
    memset(minimo, 0x3f, sizeof(minimo));
    logaritmo[0] = -1;
    for(int idx = 1; idx <= tam; idx++) {
        logaritmo[idx] = logaritmo[idx>>1] + 1;
        minimo[idx][0] = maximo[idx][0] = elementos[idx];
    }
    for(int nivel = 1; nivel <= 16; nivel++) {
        for(int pos = 1; pos + (1 << nivel-1) <= tam; pos++) {
            maximo[pos][nivel] = max(maximo[pos][nivel-1], maximo[pos+(1<<nivel-1)][nivel-1]);
            minimo[pos][nivel] = min(minimo[pos][nivel-1], minimo[pos+(1<<nivel-1)][nivel-1]);
        }
    }
}

int consultar(int inicio, int fin, bool esMax) {
    int longitud = fin - inicio + 1;
    int nivel = logaritmo[longitud];
    if(esMax)
        return max(maximo[inicio][nivel], maximo[fin-(1<<nivel)+1][nivel]);
    else
        return min(minimo[inicio][nivel], minimo[fin-(1<<nivel)+1][nivel]);
}

int main() {
    scanf("%d", &tam);
    for(int i = 1; i <= tam; i++)
        scanf("%d", &elementos[i]);
    
    inicializar();
    long long resultado = 0;
    
    for(int largo = 1; largo <= tam; largo++) {
        for(int inicio = 1; inicio + largo - 1 <= tam; inicio++) {
            int fin = inicio + largo - 1;
            resultado += (consultar(inicio, fin, true) - consultar(inicio, fin, false) == largo - 1);
        }
    }
    
    printf("%lld\n", resultado);
    return 0;
}

Complejidad temporal O(n²), insuficiente para el límite de tiempo de 750ms.

Solución divide y vencerás

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int LIMITE = 50005, OFFSET = 100005;
typedef long long tipo_largo;

int cantidad, valores[LIMITE];
tipo_largo total;
int contador[OFFSET<<1];
int minimos[LIMITE], maximos[LIMITE];

void procesar(int izq, int der) {
    if(izq == der) {
        total++;
        return;
    }
    
    int medio = (izq + der) >> 1;
    
    // Calcular mínimos y máximos hacia atrás desde medio
    minimos[medio] = maximos[medio] = valores[medio];
    for(int i = medio - 1; i >= izq; i--) {
        minimos[i] = min(valores[i], minimos[i+1]);
        maximos[i] = max(valores[i], maximos[i+1]);
    }
    
    // Calcular mínimos y máximos hacia adelante desde medio+1
    minimos[medio+1] = maximos[medio+1] = valores[medio+1];
    for(int i = medio + 2; i <= der; i++) {
        minimos[i] = min(valores[i], minimos[i-1]);
        maximos[i] = max(valores[i], maximos[i-1]);
    }
    
    // Caso: máximo en lado izquierdo
    int ptr1 = medio + 1, ptr2 = medio + 1;
    for(int pos_izq = medio; pos_izq >= izq; pos_izq--) {
        while(ptr1 <= der && maximos[ptr1] < maximos[pos_izq]) 
            contador[minimos[ptr1] + ptr1 + OFFSET]++, ptr1++;
        while(ptr2 < ptr1 && minimos[ptr2] > minimos[pos_izq]) 
            contador[minimos[ptr2] + ptr2 + OFFSET]--, ptr2++;
        
        total += contador[maximos[pos_izq] + pos_izq + OFFSET];
        
        int limite_der = maximos[pos_izq] - minimos[pos_izq] + pos_izq;
        if(limite_der > medio && limite_der < ptr2) total++;
    }
    
    for(int i = ptr2; i < ptr1; i++)
        contador[minimos[i] + i + OFFSET] = 0;
    
    // Caso: máximo en lado derecho
    int izq1 = medio, izq2 = medio;
    for(int pos_der = medio + 1; pos_der <= der; pos_der++) {
        while(izq1 >= izq && maximos[izq1] < maximos[pos_der])
            contador[minimos[izq1] - izq1 + OFFSET]++, izq1--;
        while(izq2 > izq1 && minimos[izq2] > minimos[pos_der])
            contador[minimos[izq2] - izq2 + OFFSET]--, izq2--;
        
        total += contador[maximos[pos_der] - pos_der + OFFSET];
        
        int limite_izq = minimos[pos_der] - maximos[pos_der] + pos_der;
        if(limite_izq <= medio && limite_izq > izq2) total++;
    }
    
    for(int i = izq2; i > izq1; i--)
        contador[minimos[i] - i + OFFSET] = 0;
    
    procesar(izq, medio);
    procesar(medio + 1, der);
}

int main() {
    scanf("%d", &cantidad);
    for(int i = 1; i <= cantidad; i++)
        scanf("%d", &valores[i]);
    
    procesar(1, cantidad);
    printf("%lld\n", total);
    return 0;
}

Complejidad O(n log n), solución aceptable.

Segment tree con pilas monótonas

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_ELEM = 50005;
typedef long long entero_largo;

entero_largo respuesta;
int total_elementos, datos[MAX_ELEM];

struct nodo_segmento {
    int inicio, fin, valor_min, cuenta, etiqueta_suma;
} arbol[4*MAX_ELEM];

void actualizar_arriba(int indice) {
    arbol[indice].valor_min = min(arbol[indice*2].valor_min, arbol[indice*2+1].valor_min);
    int izq = arbol[indice].valor_min==arbol[indice*2].valor_min ? arbol[indice*2].cuenta : 0;
    int der = arbol[indice].valor_min==arbol[indice*2+1].valor_min ? arbol[indice*2+1].cuenta : 0;
    arbol[indice].cuenta = izq + der;
}

void construir(int nodo, int ini, int fin) {
    arbol[nodo].etiqueta_suma = 0;
    arbol[nodo].inicio = ini;
    arbol[nodo].fin = fin;
    
    if(ini == fin) {
        arbol[nodo] = {ini, fin, ini, 1, 0};
        return;
    }
    
    int mitad = (ini + fin) >> 1;
    construir(nodo*2, ini, mitad);
    construir(nodo*2+1, mitad+1, fin);
    actualizar_arriba(nodo);
}

void aplicar_cambio(int nodo, int valor) {
    arbol[nodo].valor_min += valor;
    arbol[nodo].etiqueta_suma += valor;
}

void propagar(int nodo) {
    if(arbol[nodo].etiqueta_suma == 0) return;
    aplicar_cambio(nodo*2, arbol[nodo].etiqueta_suma);
    aplicar_cambio(nodo*2+1, arbol[nodo].etiqueta_suma);
    arbol[nodo].etiqueta_suma = 0;
}

void modificar_rango(int nodo, int ini, int fin, int delta) {
    if(arbol[nodo].inicio >= ini && arbol[nodo].fin <= fin) {
        aplicar_cambio(nodo, delta);
        return;
    }
    
    propagar(nodo);
    int mitad = (arbol[nodo].inicio + arbol[nodo].fin) >> 1;
    if(ini <= mitad) modificar_rango(nodo*2, ini, fin, delta);
    if(fin > mitad) modificar_rango(nodo*2+1, ini, fin, delta);
    actualizar_arriba(nodo);
}

int pila_max[MAX_ELEM], tope_max, pila_min[MAX_ELEM], tope_min;

void resolver() {
    construir(1, 1, total_elementos);
    
    for(int posicion = 1; posicion <= total_elementos; posicion++) {
        // Mantener pila de máximos
        while(tope_max && datos[posicion] > datos[pila_max[tope_max]]) {
            modificar_rango(1, pila_max[tope_max-1]+1, pila_max[tope_max], 
                           datos[posicion] - datos[pila_max[tope_max]]);
            tope_max--;
        }
        
        // Mantener pila de mínimos
        while(tope_min && datos[posicion] < datos[pila_min[tope_min]]) {
            modificar_rango(1, pila_min[tope_min-1]+1, pila_min[tope_min],
                           datos[pila_min[tope_min]] - datos[posicion]);
            tope_min--;
        }
        
        respuesta += arbol[1].cuenta;
        pila_max[++tope_max] = pila_min[++tope_min] = posicion;
    }
}

int main() {
    scanf("%d", &total_elementos);
    for(int i = 1; i <= total_elementos; i++)
        scanf("%d", &datos[i]);
    
    resolver();
    printf("%lld\n", respuesta);
    return 0;
}

Las pilas monótonas almacenan índices, no valores directamente. Es crucial manejar correctamente los límites durante las actualizaciones del árbol de segmentos.