枚举

数据结构题目基本思想：枚举一个查另一个

1221F. Choose a Square

给定 $N$ 个 $(X_i, Y_i, C_{i})$。选取 $a,b$，最大化

$$S(a, b) = a - b + \sum_{\substack{a \le X_i \le b \\ a \le Y_i \le b}} C_i$$

$$S(a, b) = a - b + \sum_{a \leqslant \min\lbrace X_i, Y_{i} \rbrace \leqslant \max\lbrace X_i, Y_{i} \rbrace \leqslant b} C_i$$

考虑代换为

$$S(a, b) = a - b + \sum_{a \leqslant L_{i} \leqslant R_{i} \leqslant b} C_i$$

线段树的键为左端点 $a$，升序枚举 $b$，找到所有 $R_i = b$ 的区间，对线段树区间 $[1, L_i]$ 执行区间加 $C_i$，查询线段树中 $[1, b]$ 区间的最大值。