P4169-CDQ分治/K-D tree（三维偏序）-天使玩偶 这是一篇两种做法都有的题解 题外话 我写吐了…… 本着不看题解的原则，没写（不会）K-D tree，就写了个cdq分治的做法。下面是我的写题步骤： 想着树状数组维护不了区间最值，于是写了线段树，因为一个**的错误调了几个小时； cdq只写了两个方向。显然是错的，因为没考虑修改。所以挂了； 加上另外两个方向，...

对树状数组的理解加深了！ 转化题意 动态维护一个单调不降和一个单调不增序列，每次修改后输出两序列取最小值后的最大值和其最大位置。 思路 首先，阅读原题，知道最后答案一定是某个战士的温度，所以我们将温度离散化。 再次阅读，发现冰系是一个（以温度为自变量的）单调不降序列，每次修改一个战士就是修改一段后缀。火系相反，修改前缀。 深度阅读，发现题目其实就是求两个序列的交点。于是转化成上述...