二分+模拟，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、代码详解

1. ​

复制代码

1. #include <bits/stdc++.h>
2. using PII = std::pair<int, int>;
3. using i64 = long long;
4. std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
6. const int P = [](int x) {
7.     auto isprime = [](int x) {
8.         if (x <= 1) return false;
9.         for (int i = 2; i <= x / i; i ++ )
10.             if (x % i == 0) return false;
11.         return true;
12.     };
13.     while (!isprime(x)) x ++;
14.     return x;
15. }(rnd() % 900000000 + 100000000);
17. void solve() {
18.     /*  直接模拟    */
19.     int N, Q, s;
20.     std::cin >> N >> Q;
21.     std::vector<int> nums(N);
22.     std::vector<i64> pre(N + 1);
23.     for (int i = 0; i < N; i ++ )
24.         std::cin >> nums[i];
25.     std::sort(nums.begin(), nums.end());
27.     for (int i = 0; i < N; i ++ )
28.         pre[i + 1] += nums[i] + pre[i];
29.    
30.     std::vector<std::array<int, 2>> segs { { 0, N - 1 } };  segs.reserve(N);
31.     std::unordered_set<i64> st;
33.     while (segs.size()) {
34.         std::vector<std::array<int, 2>> nxt;
35.         for (auto& [l, r] : segs) {
36.             st.insert(pre[r + 1] - pre[l] + P);
38.             if (nums[l] != nums[r]) {
39.                 int mid = std::upper_bound(nums.begin(), nums.end(), (nums[l] + nums[r]) >> 1) - nums.begin();
40.                 nxt.insert(nxt.end(), { { l, mid - 1 }, { mid, r } });
41.             }
42.         }
43.         segs = std::move(nxt);
44.     }
46.     for (int i = 0, s; i < Q; i ++) {
47.         std::cin >> s;
48.         if (st.count(1LL * s + P))
49.             std::cout << "YES\n";
50.         else
51.             std::cout << "NO\n";
52.     }
53. }
56. int main () {
57.     std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);
58.     int _ = 1;
59.     std::cin >> _;
60.     while (_ --)
61.         solve();
62.     return 0;
63. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。