二分+模拟，CF1461D - Divide and Summarize

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1461D - Codeforces

二、解题报告

1、思路分析

我们发现每次分裂操作结果都是固定的

我们从初始序列分裂出两个确定的子序列，两个确定的子序列又分裂出4个确定的子序列

那么也就是说我们最终能够分裂出的子序列的数目是O(n)的

我们预处理出所有的子序列就预处理出了所有可以得到的和（当然这个和要在分裂的过程中维护）

而分裂要求我们得到小于等于mid的部分和大于的部分

所以我们需要对原序列进行排序，模拟的过程通过二分来找到分裂的位置

同时预处理前缀和以便每次分裂前都记录一下当前得到的值

值得注意的是nums[l] = nums[r]的时候说明当前子序列是相同的，我们无法继续向下分裂

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

​

#include 
using PII = std::pair;
using i64 = long long;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
const int P = [](int x) {
    auto isprime = [](int x) {
        if (x  N >> Q;
    std::vector nums(N);
    std::vector pre(N + 1);
    for (int i = 0; i > nums[i];
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i > 1) - nums.begin();
                nxt.insert(nxt.end(), { { l, mid - 1 }, { mid, r } });
            }
        }
        segs = std::move(nxt);
    }
    for (int i = 0, s; i > s;
        if (st.count(1LL * s + P))
            std::cout  _;
    while (_ --)
        solve();
    return 0;
}