首先抛出一个问题：为什么需要二级配置器？
因为当我们动态分配内存的时候，分配的内存往往不仅仅是我们需要的那些，还会产生一些额外的开销，比如首尾的cookies，debug模式下产生的额外开销，和内存对齐所产生的pad。这些附加信息，降低了空间的利用率。

于是就设置了二级空间配置器，当开辟小等于128bytes内存时，就视为开辟小块内存，调用二级空间配置器。否则调用一级空间配置器。

一级空间配置器

在一级空间配置器中，最重要的函数有：

• allocate：用于分配空间，申请失败，调用oom_alloc尝试重新申请
• deallocate：用于释放空间
• reallocate：调整已经存在的空间大小，如果调整失败，调用oom_alloc尝试重新申请

其实对应的标准库函数就是malloc，free和realloc。

题意

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。$(n, k \in [1, 100000])$

Solution

用优先队列+延迟删除有点麻烦，可以考虑直接用 multiset 做，本质都是一样的，维护两个大小相同或差一的集合（自动排序）$l 和 r$，$l$ 维护小于等于中位数的值，$r$ 维护大于等于中位数的值，$multiset$ 的优秀特性可以在 $log$ 时间复杂度内进行增删操作。具体细节较多，时间复杂度 $O(nlog(k))$。

快排的思想，选定一个基准数，将大于 $mid$ 的数放到右边，小于的放到左边，然后比较 $mid$ 和 $k$ 的位置，递归重复操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#pragma GCC optimize("Ofast")
#include <cstdio>

inline int read() {
<!--more--> 
  int x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w ^= 1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return w & 1 ? x : -x;
}

int kth_element(int* a, int l, int r, int k) {
  int mid = l - 1;
  for (int i = l; i < r; ++i) {
    if (a[i] < a[r] && a[i] ^ a[++mid]) a[i] ^= a[mid] ^= a[i] ^= a[mid];
  }
  if (a[++mid] ^ a[r]) a[mid] ^= a[r] ^= a[mid] ^= a[r];
  if (mid == k) return a[mid];
  return (mid >= k) ? kth_element(a, l, mid - 1, k)
                    : kth_element(a, mid + 1, r, k);
}

int a[2000006];

int main() {
  int n, k;
  n = read();
  k = read();
  for (int i = 0; i < n; ++i) a[i] = read();
  // random_shuffle(a, a + n);
  printf("%d\n", kth_element(a, 0, n - 1, n - k));
  return 0;
}

题目

$n$ 个物体，每个物品都有 $k$ 个属性，实际上就是 $a[n][k]$ 的数组，满足 $a[i][0]+a[j][0]=a[i][1]+a[j][1]=…=a[i][k−1]+a[j][k−1]$ 的物体 $i$ 和物体 $j$ 称为一对完美对，求完美对对数。

Solution

题目

给你长度为 $n$ 的序列，你有一种能力可以将序列中的任意一个数变为相反数，在你不超过 $k$ 次使用能力的情况下，长度为 $len$ 的子区间的和的绝对值的最大值是多少？

Solution

用两个multiset维护区间前k大的负数，扫一遍就好了，细节略多。

题意

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

Solution

直接对所有的数排序，然后优先队列维护一个k个数组都有值存在且对当前来说长度最小的滑动窗口，同时维护答案即可。

题意

一共有 $n$ 个数，第 $i$ 个数是 $x_i$ 可以取 $[l_i , r_i]$ 中任意的一个值。设 $S = \sum{ {x_i}^2}$，求 $S$ 种类数。（0 ~ n,l,r ~ 100）

Solution

$dp[i][j]$ 表示前 $i$ 个数能不能组成 $j$，可以得到转移方程：$dp[i][j]=dp[i-1][j-x^2]$，最后统计 $dp[n]$ 层组成的 $j$ 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程：dp[i]=dp[i-1] << (j*j)，复杂度 $10^{10}/64$。