进程通信

GitHub跳转原题关系图 Canvas 关系图返回列表

用按长度排序的空闲区间维护 best-fit 分配器，并记录每个进程接口的循环写入位置。

OJ: shumeng

题目 ID: CSP202603C

难度:未知

标签:模拟有序集合区间合并数据结构

日期: 2026-07-31 16:22

形式化题目

把内存看作从地址 $0$ 开始、容量足够大的连续空间，初始全部空闲。依次处理 $q$ 个操作：

new p L：为进程 $p$ 新建编号递增的接口与队列，按 best-fit 原则分配一段长度为 $L$ 的内存，输出分配区间的左端点 $a$ ；
send p：进程 $p$ 向它对接的所有接口各发送一个对象，对象在各自队列内按 $a\to b\to a\to\cdots$ 循环存放，输出本次所有写入地址之和；
delete p i：删除进程 $p$ 的第 $i$ 个接口，释放其内存区间，其余编号大于 $i$ 的接口编号依次减一。

思路

空闲区间的两种视角

分配需要“长度最短且靠左”的区间，释放需要“按地址合并相邻区间”，两者排序依据不同，因此用两个有序结构同时维护空闲区间：

free_by_left（map<左端点, 右端点>）：支持按地址找到相邻区间并合并；
free_by_size（set<(长度, 左端点)>）：用 lower_bound 直接找到长度至少为 $L$ 的最短区间。

text

1
2分配:  set 找 best-fit 区间 -> map 取区间 -> 左端取 L 个地址 -> 剩余放回
释放:  加入 [a,b] -> 与左右相邻空闲区间合并 -> 两个结构同步更新

队列的循环写入

每个接口只需记住区间端点 [a,b] 和最近一次写入位置 last。发送时如果 last 还是初始值或已经到 b，就写回 a；否则 last+1。

删除操作

释放内存区间后调用区间合并，同时从进程的接口列表中删掉对应项即可，编号自动前移的效果由 vector::erase 天然完成。

代码

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 内存被看作 [0, INF] 的一段连续空间，初始全部空闲。
const long long INF = 4000000000000000000LL;

// 一个进程接口对应的队列：占用的内存区间 [left, right] 与最近一次写入位置
struct QueueInfo {
    long long left;
    long long right;
    long long last; // 最近一次发送时对象写入的地址，-1 表示尚未发送过
};

// 空闲区间按左端点排序，用于按地址合并相邻区间
map<long long, long long> free_by_left;
// 空闲区间按 (长度, 左端点) 排序，用于找 best-fit 区间
set<pair<long long, long long> > free_by_size;

// 从两个有序结构中删除左端点为 left 的空闲区间。
void erase_free(long long left) {
    map<long long, long long>::iterator it = free_by_left.find(left);
    long long right = it->second;
    free_by_size.erase(make_pair(right - left + 1, left));
    free_by_left.erase(it);
}

// 插入空闲区间 [left, right]，并把它与左右相邻的区间合并。
void add_free(long long left, long long right) {
    map<long long, long long>::iterator it = free_by_left.lower_bound(left);
    // 先尝试与左侧相邻的区间合并
    if (it != free_by_left.begin()) {
        map<long long, long long>::iterator previous = it;
        --previous;
        if (previous->second + 1 >= left) {
            left = previous->first;
            right = max(right, previous->second);
            erase_free(previous->first);
        }
    }

    // 再向右吃掉所有与当前区间相邻的区间
    it = free_by_left.lower_bound(left);
    while (it != free_by_left.end() && it->first <= right + 1) {
        right = max(right, it->second);
        map<long long, long long>::iterator next = it;
        ++next;
        erase_free(it->first);
        it = next;
    }
    free_by_left[left] = right;
    free_by_size.insert(make_pair(right - left + 1, left));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<vector<QueueInfo> > queues(n + 1); // queues[p] 保存进程 p 的接口队列
    free_by_left[0] = INF;                    // 初始只有一个覆盖全部内存的空闲区间
    free_by_size.insert(make_pair(INF + 1, 0));

    for (int operation = 0; operation < q; operation++) {
        string type;
        cin >> type;
        if (type == "new") {
            int process, length;
            cin >> process >> length;
            // best-fit：长度不小于 L 且最短、最靠左的空闲区间
            set<pair<long long, long long> >::iterator it =
                free_by_size.lower_bound(make_pair((long long)length, LLONG_MIN));
            long long left = it->second;
            long long right = free_by_left[left];
            erase_free(left);
            if (left + length <= right) { // 取走 L 个地址后还有剩余，重新加回
                add_free(left + length, right);
            }

            QueueInfo queue;
            queue.left = left;
            queue.right = left + length - 1;
            queue.last = -1;
            queues[process].push_back(queue);
            cout << left << '\n';
        } else if (type == "send") {
            int process;
            cin >> process;
            long long answer = 0;
            // 进程 p 的所有队列各写入一个对象，地址从 last 向右循环推进
            for (int i = 0; i < (int)queues[process].size(); i++) {
                QueueInfo &queue = queues[process][i];
                if (queue.last == -1 || queue.last == queue.right) {
                    queue.last = queue.left; // 首次写入或绕回左端点
                } else {
                    queue.last++;
                }
                answer += queue.last;
            }
            cout << answer << '\n';
        } else { // delete 操作
            int process, index;
            cin >> process >> index;
            QueueInfo queue = queues[process][index - 1];
            add_free(queue.left, queue.right); // 释放整个区间并合并
            queues[process].erase(queues[process].begin() + index - 1);
        }
    }
    return 0;
}

复杂度

时间：new 和 delete 每次进行常数次 $O(\log q)$ 级有序结构操作；send 需要遍历该进程的全部接口。总时间复杂度为 $O((q+n)\log q+\text{总发送接口数})$ 。
空间：空闲区间与接口总数均为 $O(q)$ ，空间复杂度 $O(q)$ 。

总结

同时需要“按地址合并”和“按长度选择”的结构，分别维护两种排序键可以让两个操作都保持对数复杂度。同步删除/插入时注意 map 与 set 必须保持一致，否则后续操作会读到错误区间。

题目来自第 41 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

某一天，西西艾弗岛上的居民们迎来了一个天大的好消息：他们终于有了自己的操作系统。这个操作系统有一个特性：其内部每个进程都具有动态链接接口并对外广播信息的功能。小 C 的团队负责开发该功能与内存间交互的必要环节，同时维护支持内存调度与分配的子系统。

这套系统刚开发完毕，运行稳定性未知，于是小 C 团队邀请了你来当模拟测试员。他们希望你能够帮忙模拟出这套系统的运作流程，对于各种可能情况给出其具体行为，从而帮助他们完善这套系统。由于你们的合作刚处于起步阶段，小 C 为你提供了一个简化后的模型。

初始建构

首先认为有一段存储容量为 $10^{100}$ （保证足够大）的初始为空的全局内存，内存地址从左到右依次编号 $0,1,2\cdots$ 。为了简化模型，视这段内存的每一个字节可以存储一个对象，且我们并不关心对象具体内容。因此本题中只需用 $e_i\in\{0,1\},x_i\in\{0,1\}$ 两个状态变量代表 $i$ 号地址处是否被占用以及是否有对象被存储；其中 $e_i=1$ 代表地址 $i$ 被占用， $e_i=0$ 代表未被占用； $x_i=1$ 代表有对象存储， $x_i=0$ 代表没有。初始时所有 $e_i,x_i$ 均为 $0$ 。

接下来考虑有 $n$ 个准备进行对象传输的进程，依次编号 $1,2,\cdots,n$ ，一开始没有任何接口与它们对接。初始状态下系统中各对象的逻辑关系可以用下图表示（例 $n=2$ ）：

通信行为

将系统内各对象的行为以操作的形式封装，接下来定义小 C 的模型中所有可能发生的操作：

new p L：建立一个只负责接收进程 $p$ 所发出对象的新接口，同时建立在进程 $p$ 与该接口之间进行消息传递的队列，队列存储容量为 $L$ 。

设在该操作之前进程 $p$ 共对接了 $k$ 个接口，新建的接口会被编号为 $k+1$ 。注意，新建的接口与队列具有对应关系，且它们均独属于进程 $p$ 。
接下来分配器会响应，根据最优适应原则存储队列。具体来说：
- 分配器首先会识别内存中所有极长的未被占用的连续地址段，它们从左到右可以写成若干个非空区间的形式 $[l_1,r_1],[l_2,r_2],\cdots,[l_{t-1},r_{t-1}],[l_t,r_t]$ 。其中 $r_t=10^{100}$ 。从左到右第 $i$ 段的长度为 $r_i-l_i+1$ 。
  - 接下来它会在这些段中寻找长度 $\geq L$ 且尽可能短的段（若有多个满足条件的段，则取左端点 $l$ 最小的段） $[l,r]$ ；
  - 将连续地址段 $[l,l+L-1]$ 分配给接口 $k+1$ ，用于存储队列中的信息。这段长度为 $L$ 的内存空间每个位置此刻起均视为被占用，也即 $\forall j\in[l,l+L-1]$ ，令 $e_j=1$ 。

下例中，进程 $1,2$ 在操作执行前均已对接各自的 $1$ 号接口，分别占用内存区域 $[2,4]$ 与 $[9,11]$ ；进行一次 new 1 3 操作后，进程 $1$ 对接了自身的 $2$ 号接口，并在内存区域 $[5,7]$ 建立了对应的队列：

send p：进程 $p$ 同时向所有其对接的接口发送一个对象。具体来说，设 $p$ 对接了 $k$ 个接口，则 $\forall i\in[1,k]$ ，均进行如下操作：

找到与 $p$ 对接的编号为 $i$ 的接口对应的队列，其在内存中占用的地址区间为 $[a,b]$ 。
如果队列为空（即接口建立以来进程 $p$ 从未向该接口发送过任何对象），则将对象存储在 $a$ 处，令 $x_a=1$ 。
否则进程 $p$ 向该接口发送过至少一个对象。记最近一次发送时，对象被存储在了位置 $t\in[a,b]$ 处。若 $t<b$ ，则该次发送将对象存储在地址 $t+1$ 处，令 $x_{t+1}=1$ ；否则 $t=b$ ，此时将对象存储在地址 $a$ 处，令 $x_a=1$ 。注意该操作可能不对某个地址的属性 $x$ 造成改动。

在上例的基础上，进行一次 send 1 操作， $1$ 号进程会在两个队列分别占有的 $4,5$ 号地址处各存储一个对象：

额外说明：如果在此之后连续执行 $4$ 次 send 2 操作，则队列 $2-1$ 会依次在地址 $10,11,9,10$ 存储对象。

delete p i：设进程 $p$ 对接了 $k$ 个接口，该操作保证 $1\leq i\leq k$ 。该操作使编号为 $i$ 的接口及队列均被删除，删除时遵循如下流程：

找到与进程 $p$ 对接的编号为 $i$ 的接口对应的队列，其在内存中占用的地址区间为 $[a,b]$ 。
$\forall i\in[a,b]$ ，将 $e_i$ 与 $x_i$ 均置为 $0$ ，视为删除所有存储在其中的对象，并将各个地址的占用状态取消。
将与进程 $p$ 所对接的其余编号大于 $i$ 的接口的编号均减去 $1$ ，接口与队列的对应关系不变。例如一次操作前进程 $p$ 对接了 $4$ 个接口，则通过操作删除 $2$ 号接口及队列后，原先编号为 $3,4$ 的接口与队列的编号会被依次更新为 $2,3$ 。

在上例的基础上，进行一次 delete 1 1 操作，则 $1$ 号进程原先对应的 $1$ 号队列及其内部的对象均会被删除：

以上便是小 C 给出的简化模型的所有基本事件定义。

题目描述

现在小 C 给出了一个长度为 $q$ 的操作序列，每个操作都为上述三种之一。你需要严格按照顺序模拟这些操作的运行。

小 C 为了检查模拟程序运行的过程是否正确，要求你进行如下反馈输出：

每次执行完 new p L 操作，你需要输出进程 $p$ 所对接的新接口相应队列在内存中存储的地址。设其存储在区间 $[a,b]$ ，你只需输出 $a$ 。
每次执行完 send p 操作，在进程 $p$ 向其对接的 $k$ 个接口均发送一个对象后，你需要输出该操作中 $k$ 个新发送的对象所存储的地址的和。

为了让你们之间的合作能更进一步，请你完成小 C 的模拟任务吧！

输入格式

从标准输入读入数据。

第一行用空格隔开的两个整数 $n,q$ ，依次代表进程数量与操作数量。

接下来 $q$ 行，每行为一个操作。操作格式如题目背景所描述。单词与数字、数字与数字之间由一个空格隔开。

输出格式

输出到标准输出。

请你对于每一个 new 操作与 send 操作，按照题目要求输出一行一个整数。

input1

1
2
3
4
5
6
7
8
9
10
11
12
13
142 13
new 1 2
new 1 3
send 1
delete 1 1
new 1 4
send 1
new 2 3
send 2
delete 1 2
new 1 3
send 1
delete 1 1
send 1

output1

样例 1 解释

读入数据自初始状态起进行完前 $9$ 次操作后变为操作解释中的状态。

每次新建操作的初始地址依次为 $0,2,5,9,5$ ；

每次发送操作所存储的所有对象所在地址和依次为 $2,8,9,9,6$ 。

样例 2

见题目文件区的 2.in 和 2.ans。

样例 3

见题目文件区的 3.in 和 3.ans。

子任务

保证操作均有意义。即不会建立空队列，不会在进程 $x$ 没有对接任何接口时发送对象，不会删除不存在的队列与接口。特别注意：向某长度为 $l$ 的队列发送超过 $l$ 个对象的行为是有意义的。

记所有 new 操作中的参数 $L$ 的最大值为 $L_{m}$ 。

对于前 $40\%$ 的测试数据，保证不存在 delete 操作；
对于前 $80\%$ 的测试数据，保证 $L_m\leq 10,q\leq 800$ ；

对于所有测试数据，保证 $1\leq n\leq 100,1\leq q\leq 8000,1\leq L_m\leq 5\times 10^5$ ，除操作名称外所有输入数据均为非负整数。

进程通信

目录

形式化题目

思路

空闲区间的两种视角

队列的循环写入

删除操作

代码

复杂度

总结