算法1

(差分约束) $O(kE)$

看到这类左右不等式关系的，觉得可以用差分约束搞一搞啊，10万个点，建图也不是问题，SPFA的玄学时间复杂度，竟然还挺快的，400ms。。。

Golang 代码

package main
import (
    "os"
    "bufio"
    "strings"
    "strconv"
    "fmt"
)
func main() {
    sc := bufio.NewScanner(os.Stdin)
    buf := make([]byte, 1024*1024)
    sc.Buffer(buf, len(buf))
    sc.Scan()
    cases, _ := strconv.Atoi(sc.Text())
    for cases > 0 {
        cases--
        sc.Scan()
        n, _ := strconv.Atoi(sc.Text())
        if n == 1 {
            fmt.Println(1)
            continue
        }
        head, next, to, w := make([]int, n+1), make([]int, n<<1+1), make([]int, n<<1+1), make([]int, n<<1+1)
        cnt := 0
        add := func(a, b, c int) {
            cnt++
            next[cnt], to[cnt], w[cnt], head[a] = head[a], b, c, cnt
        }
        sc.Scan()
        str := strings.Fields(sc.Text())
        for i := 0; i < n; i++ {
            l, _ := strconv.Atoi(str[(i-1+n)%n])
            mid, _ := strconv.Atoi(str[(i+n)%n])
            r, _ := strconv.Atoi(str[(i+1)%n])
            if mid <= l && mid <= r {
                add(n, i, 1)
            } else { 
                if mid > l {
                    add((i-1+n)%n, i, 1)
                }
                if mid > r {
                    add((i+1)%n, i, 1)
                }
            }
        }
        spfa := func() int {
            dist := make([]int, n+1)
            q := []int{n}
            inq := make([]bool, n+1)
            for len(q) > 0 {
                cur := q[len(q)-1]
                q = q[:len(q)-1]
                inq[cur] = false
                for i := head[cur]; i != 0; i = next[i] {
                    tot := to[i]
                    if dist[tot] < dist[cur] + w[i] {
                        dist[tot] = dist[cur] + w[i]
                        if !inq[tot] {
                            q = append(q, tot)
                            inq[tot] = true
                        }
                    }
                }
            }
            ans := 0
            for i := 0; i < n; i++ {
                ans += dist[i]
            }
            return ans
        }
        fmt.Println(spfa())
    }
}