原题时间限制 600ms
momo_li: 这是我印象深刻的一个 trick。
首先考虑单组询问怎么做。
定义 表示已经考虑完了第一列宝石前 个，第二个宝石前 个，最大的总获利。
初始 则转移显然，枚举直接卖第一列、第二列，或者加工即可。
直接优化较难，数据较为复杂。考虑同时处理所有询问。
注意到，如果将状态 看做点，三种转移看成边，则整个转移网形成了一个图。并且，只存在如下三种边：
每组讯问等价于从 走到 的最长路。
注意到只能向右上走，考虑分治。
设我们正在处理的矩形长 ，宽 中较小者，将其切半。
对于完全被左矩形（上矩形）包含的询问，递归处理。
对于完全被右矩形（下矩形）包含的询问，递归处理。
对于横跨中间的询问，注意到最长路一定在某个纵（横）坐标穿过中心（即，从 走到 ，或从 走到 ，另一方向同理）。
考虑枚举这条边，对于这条边的左（下、左下）端点，处理出其到矩形左下角区域内所有点的最长路；对于这条边的右（上、右上）端点，处理出其到矩形右上角区域内所有点的最长路。
对于所有要处理的询问，若该边在询问矩形范围内，则依据已处理的最长路算出贡献。
若某一矩形内没有询问，则返回。
由于该图为 DAG，最长路仍可用 DP 解决，所以总时间复杂度为 ，可以通过。