#include <bits/stdc++.h> #include <bits/extc++.h> #define int long long #define endl '\n' using namespace std; using namespace __gnu_pbds; template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve() { int n; cin >> n; ordered_multiset<int> st; vector<int> v(n); for(int i = 0; i < n; i ++ ) { cin >> v[i]; st.insert(v[i]); } int res = 0; int l = 0, r = n - 1; while(l < r) { st.erase(v[l]); st.erase(v[r]); int tmp = min(v[l], v[r]); int x = st.order_of_key(tmp); res = max(res, x + 2); if(v[l] < v[r]) r -- ; else l ++ ; } cout << res << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; cin >> t; while(t -- ) solve(); return 0; }

<think>我们分析给定的代码片段，特别是关于`ordered_multiset`的操作。注意，`ordered_multiset`是通过`__gnu_pbds`库的`tree`实现的，定义为： ```cpp template <typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; ``` 该数据结构支持两种重要操作： 1. `insert(element)`: 插入元素。 2. `erase(element)`: 删除元素（注意：由于是多重集合，可能删除多个？但这里我们看代码用法）。 3. `order_of_key(element)`: 返回小于给定元素的元素个数（或者严格来说，是返回按照排序顺序在给定元素之前的元素数量，由于使用`less_equal`，所以对于相等的元素，它们也会被计入？实际上，`order_of_key`返回的是严格小于该元素的元素个数，即使比较器是`less_equal`，因为内部实现是通过`lower_bound`和`upper_bound`来区分的？） 但是，根据`__gnu_pbds`的文档，`tree_order_statistics_node_update`提供了两个操作： - `find_by_order(k)`: 返回迭代器，指向第k大的元素（从0开始计数）。 - `order_of_key(key)`: 返回在集合中严格小于`key`的元素的数量。 然而，这里使用了`less_equal`作为比较函数，这可能会导致一些问题。实际上，使用`less_equal`作为比较函数在标准中并不常见，因为它可能导致相等的元素被判断为相等，从而在插入时允许重复。但是，`order_of_key`的行为是返回严格小于`key`的元素个数，所以重复元素不会被计入，直到我们查询到该元素本身。 但是，在多重集合中，我们通常希望`order_of_key`能够正确处理重复元素。根据`__gnu_pbds`的文档，当我们使用`less_equal`时，实际上我们创建了一个可以包含重复元素的集合，但是`order_of_key`的行为仍然是：对于给定的`key`，它返回的是严格小于`key`的元素个数。也就是说，它不会包含等于`key`的元素。 然而，在代码中，我们使用`st.order_of_key(tmp)`，其中`tmp`是`min(v[l],v[r])`。我们想要的是在集合中严格小于`tmp`的元素个数。但是，由于集合中可能存在多个等于`tmp`的元素，它们不会被计入。 现在，我们分析代码的时间复杂度。 代码主要步骤： 1. 读取n个元素，插入到`st`中（一个`ordered_multiset`）。插入n个元素，每次插入的时间复杂度为O(log n)，所以总时间为O(n log n)。 2. 初始化后，进行一个循环：循环次数大约是n/2（因为每次循环l或r移动一步，直到l>=r）。在每次循环中： - 删除`v[l]`和`v[r]`（注意：`erase`操作会删除一个元素，但这里可能有多个相同的元素，所以删除的是其中一个？实际上，`erase`在`tree`中删除一个元素时，如果有重复，它只会删除其中一个（具体是哪一个？）实际上，`tree`的`erase`方法如果传入值，它会删除所有等于该值的元素？但是，我们看代码中，在循环开始前，我们插入了所有元素，然后每次删除两个元素（左右各一个）。注意，我们使用的是`st.erase(v[l])`和`st.erase(v[r])`，如果集合中有多个相同的值，那么每次调用`erase(value)`会删除一个元素？还是所有？ 根据`__gnu_pbds`的文档，`tree`的`erase`方法有两个重载： - 如果传入一个值，它会删除所有等于该值的元素（类似于`std::multiset`的`erase`，它会删除所有匹配的元素）？但是，在`std::multiset`中，`erase`传入值会删除所有，而传入迭代器只删除一个。 然而，在`__gnu_pbds`的`tree`中，文档说明：`erase`如果传入一个值，它会删除所有等于该值的元素。但是，这样会导致问题，因为我们在循环中删除一个元素，但如果有多个相同元素，我们可能删除了多个，而代码中我们只打算删除一个。 实际上，在代码中，我们初始化时每个元素插入一次，所以每个元素只有一个。因此，删除操作每次删除一个元素。 但是，如果数组中有重复元素，那么我们在插入时因为使用`less_equal`，所以重复元素会被插入多次。那么，在删除时，`st.erase(value)`会删除所有等于`value`的元素？这显然不是我们想要的，因为每个位置只插入了一次，但是重复值可能出现在多个位置。 例如，假设数组有两个相同的元素x，分别在位置i和j。那么当我们删除位置l（假设l指向i）时，调用`st.erase(v[l])`（即`st.erase(x)`）会删除集合中所有的x。那么当我们删除位置r（假设r指向j）时，再次调用`st.erase(v[r])`（还是x）时，集合中已经没有x了，这样操作是无效的？还是会导致错误？ 实际上，我们需要确认`__gnu_pbds::tree`的`erase`方法的行为：当传入一个值，它会删除所有等于该值的元素，并返回被删除的元素个数。因此，如果数组中有重复元素，那么一次`erase(value)`会删除多个元素（所有等于value的元素），这显然不符合我们的意图（我们只想删除一个元素，即当前位置的元素）。 因此，代码中如果数组有重复元素，那么删除操作会出错。但是，题目没有说明元素是否重复。我们假设元素可能重复，那么这段代码在重复元素的情况下会错误地删除多个元素。 所以，为了正确删除一个元素，我们应该使用迭代器来删除。但是，在代码中，我们并没有保存迭代器。因此，这里可能存在问题。 但是，我们暂时不修改代码，而是按照代码的意图分析时间复杂度。假设我们使用迭代器删除，那么删除一个元素的时间复杂度是O(log n)。因为`tree`是基于红黑树的，删除一个节点的时间复杂度为O(log n)。 所以，每次循环中： st.erase(v[l]); // 假设删除一个元素，时间复杂度O(log n) st.erase(v[r]); // 时间复杂度O(log n) st.order_of_key(tmp); // 时间复杂度O(log n) （因为需要遍历树，路径长度O(log n)） 循环次数：大约n/2次（因为l和r每次移动一步，直到相遇，所以循环次数大约是n/2次） 因此，循环内的总操作次数为：O(n) * [O(log n) + O(log n) + O(log n)] = O(n log n) 加上初始化插入的O(n log n)，总时间复杂度为O(n log n)。 但是，我们需要注意的是，随着元素的删除，集合的大小在减少，每次操作的时间复杂度应该是O(log (当前集合大小))。初始集合大小为n，然后每次删除两个，所以第i次循环时，集合大小大约为n-2i。因此，总的时间复杂度可以表示为： T(n) = sum_{i=0}^{k-1} [3 * log(n-2i)] （其中k=n/2） 因为log(n-2i) <= log(n)，所以T(n) <= 3 * (n/2) * log(n) = O(n log n) 同时，由于对数函数是凹函数，我们可以用积分近似： T(n) ≈ 3 * ∫_{0}^{n/2} log(n-2i) di = (3/2) * ∫_{n}^{n/2} log(x) dx （令x=n-2i，则当i=0时x=n，i=n/2时x=0，但是积分区间应该从n到0？不对，我们换元后积分方向要变） 实际上，我们令x = n-2i，则di = -dx/2，当i=0时，x=n；i=n/2时，x=0（如果n是偶数）或x=1（n为奇数，但忽略）。所以： T(n) = 3 * ∫_{n}^{0} log(x) * (-dx/2) = (3/2) * ∫_{0}^{n} log(x) dx （注意积分上下限交换） 但是，这个积分在0处发散，所以我们需要离散求和。实际上，我们考虑离散情况，使用调和级数的性质，或者直接使用不等式： sum_{i=1}^{m} log(i) = log(m!) ≈ m log m - m + O(log m) 这里，我们求和的是log(j)，j从1到n，但是我们的项是log(n), log(n-2), ... 直到log(2)或log(1)。这个和显然小于n log n，所以总时间复杂度为O(n log n)。 因此，整个算法的时间复杂度为O(n log n)。 但是，我们还需要考虑读取输入等操作，这些是O(n)，所以总时间复杂度为O(n log n)。 结论：给定代码的时间复杂度为O(n log n)。 但是，我们需要注意的是，在`__gnu_pbds`的`tree`中，使用`less_equal`作为比较函数可能会导致一些未定义行为？因为标准要求比较函数必须是严格弱序，而`less_equal`不是严格弱序（因为它不是不对称的：a<=b和b<=a同时成立时，不一定有a==b？实际上，对于相等的情况，它满足自反性，但严格弱序要求不对称性）。实际上，正确的做法是使用`less`，然后通过其他方式支持重复元素（比如将元素与一个唯一标识符配对）。所以，当前代码可能在某些情况下行为不正确。 不过，我们只分析时间复杂度，所以假设每个操作都是O(log n)的。 因此，最终答案是：时间复杂度为O(n log n)。</think>### C++ `ordered_multiset` 时间复杂度分析 在您的代码中，`ordered_multiset` 是通过 `__gnu_pbds::tree` 实现的，底层使用**红黑树**（自平衡二叉搜索树）。以下是关键操作的时间复杂度分析（$n$ 表示集合中元素数量）： #### 1. **基本操作时间复杂度** | 操作 | 时间复杂度 | 说明 | |--------------------|----------------|------| | **插入 (`insert`)** | $O(\log n)$ | 红黑树插入需搜索位置并调整平衡 | | **删除 (`erase`)** | $O(\log n)$ | 需查找元素并调整树结构 | | **`order_of_key`** | $O(\log n)$ | 返回严格小于给定值的元素数量 | #### 2. **代码中具体操作分析** ```cpp ordered_multiset<int> st; // 初始化插入 for(int i = 0; i < n; i++) { st.insert(v[i]); // O(log n) per insertion → O(n log n) total } // 主循环 while(l < r) { st.erase(v[l]); // O(log n) st.erase(v[r]); // O(log n) int x = st.order_of_key(tmp); // O(log n) // ...更新指针... } ``` - **初始化插入**：$n$ 次插入操作，每次 $O(\log n)$ → 总时间 $O(n \log n)$。 - **主循环**：循环约 $n/2$ 次（每次移动左或右指针），每次循环包含： - 2 次删除：$2 \times O(\log n)$ - 1 次 `order_of_key`：$O(\log n)$ - 单次循环总时间：$O(\log n)$ - **主循环总时间**：$\frac{n}{2} \times O(\log n) = O(n \log n)$。 #### 3. **整体时间复杂度** - **总时间复杂度**：$O(n \log n) + O(n \log n) = \boxed{O(n \log n)}$。 - 空间复杂度：$O(n)$（存储所有元素）。 #### 4. **关键说明** 1. **红黑树的平衡性**：红黑树通过约束节点颜色和旋转操作，保证树高度始终为 $O(\log n)$[^1]。 2. **重复元素处理**：使用 `less_equal` 允许重复元素，但 `order_of_key` 仅统计**严格小于**给定值的元素（等于值的元素不计数）[^1]。 3. **删除操作的注意事项**：`st.erase(value)` 会删除**所有匹配值**的元素。若需精确删除单个元素，应使用迭代器（但当前代码未实现）。 #### 5. **优化建议** - **避免重复删除**：若数组中有重复元素，`st.erase(v[l])` 可能误删多个值。建议改用迭代器定位删除： ```cpp auto it = st.find_by_order(position); // O(log n) st.erase(it); // O(1) 分摊时间 ``` - **预分配内存**：如果元素范围已知，可提前预留空间减少动态分配开销。 ### 总结 | 代码部分 | 时间复杂度 | |------------------|------------------| | 初始化插入 | $O(n \log n)$ | | 主循环（删除+查询）| $O(n \log n)$ | | **总复杂度** | $\boxed{O(n \log n)}$ | 如果需要进一步分析特定场景（如大量重复元素）的性能，或与其他容器（如 `unordered_multiset`）对比，请随时告知！