CF1210G Mateusz and Escape Room

Mateusz 喜欢旅行！然而，在他第 $42$ 次造访 Saint Computersburg 时，已经没有太多景点可供参观了。因此，他决定和朋友们一起去密室逃脱！ 团队已经完美地解开了所有谜题。现在只剩下最后一个谜题——一个巨大的圆形桌子！桌子上有 $n$ 个天平，均匀分布在圆周上。每个天平恰好与另外两个天平相邻：对于每个 $i \in \{1, 2, \dots, n-1\}$，第 $i$ 个天平和第 $(i+1)$ 个天平相邻，第一个天平和第 $n$ 个天平也相邻。 第 $i$ 个天平最初有 $a_i$ 个沉重的硬币。Mateusz 可以进行若干次操作——每次操作可以从某个天平取出一个硬币，并将其放到任意一个相邻的天平上。 谜题的解答条件是：每个天平上的硬币数量都在特定范围内。具体来说，每个天平有参数 $l_i$ 和 $r_i$。如果每个硬币都只在一个天平上，并且对于每个 $i$，第 $i$ 个天平上的硬币数量不少于 $l_i$ 且不多于 $r_i$，那么谜题就算解开了，Mateusz 的团队就会获胜！ Mateusz 希望用最短的时间解开谜题。因此，他想知道，满足所有条件所需的最少操作次数是多少？

第一行包含一个整数 $n$（$3 \le n \le 35\,000$），表示圆上的天平数量。 接下来的 $n$ 行描述每个天平。第 $i$ 行包含三个整数 $a_i, l_i, r_i$（$0 \le a_i \le 35\,000$，$0 \le l_i \le r_i \le 35\,000$）。 保证一定存在解，即 $\sum_{i=1}^n l_i \le \sum_{i=1}^n a_i \le \sum_{i=1}^n r_i$。

输出一个整数，表示解开谜题所需的最少操作次数。

由 ChatGPT 4.1 翻译