#6096. 花神的秒题计划

题目背景

Memphis 等一群蒟蒻出题中，花神凑过来秒题……

题目描述

花花山风景区可以看作一个 $n \times n$ 的地图，每个点有一个高度。滑雪只能从高处往低处滑（严格大于）。
由于地势变动（雪崩、滑坡）和政策保护，地图会发生变化，需要进行以下操作：

• C a b c 表示将点 $(a, b)$ 的高度改为 $c$；
• S a b c d 表示矩形区域 $[a, c] \times [b, d]$ 开始保护，即不能滑雪；
• B a b c d 表示矩形区域 $[a, c] \times [b, d]$ 取消保护，即可以滑雪；
• Q 表示询问当前整个地图中可以滑雪的最长路径长度（每一步必须严格从高到低且相邻四连通）。

输入格式

第一行一个整数 $n$。
接下来 $n$ 行，每行 $n$ 个整数，表示地图的初始高度。
接下来一个整数 $m$，表示操作总数。
接下来 $m$ 行，每行一个命令，格式如上所述。

输出格式

对于每个 Q 操作，输出一行，表示当前地图中的最长滑雪路径长度。

样例

输入

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
5
C 1 1 3
Q
S 1 3 5 5
S 3 1 5 5
Q

输出

24
3

解释

• 第一个 Q 之前，将 $(1,1)$ 的高度从 $1$ 改为 $3$，最长路径为 $25 \to 24 \to 23 \to \cdots \to 2$，长度 $24$。
• 第二次询问前，两个 S 操作分别保护了矩形 $[1,3] \times [5,5]$ 和 $[3,1] \times [5,5]$（即保护了右侧一列和下方一行的一部分），剩余可滑雪区域有限，最长路径为 $10 \to 9 \to 2$，长度 $3$。

数据范围与提示

• $1 \leq n \leq 700$
• $1 \leq m \leq 10^6$
• 其中 Q、S、B 操作数量的总和 $\leq 100$
• 所有数据（包括高度）不超过 $2 \times 10^9$

由于非查询类操作非常多（最多 $10^6$ 个 C），而查询类操作很少，需要高效处理地图修改，并在查询时快速计算最长滑雪路径。