{ }codelper
动态内存P0202

每行长度不同的表

有一张存放整数的表。
表的每一行存放的值的个数可以不同，也可以有一个值都没有的行。
一开始表中没有行。
行号从 1 开始数。
命令有六种。
- new k v1 … vk：在表的最下面接上一行存放 k 个值的新行。
k 可以是 0。
- copy i：在表的最下面接上一行与第 i 行值相同的新行。
之后两行各自独立变化。
- add i v：在第 i 行末尾追加一个值 v。
- set i j v：把第 i 行的第 j 个值（从 1 开始数）改成 v。
- del i：删除第 i 行。
它下面的行号依次前移一位。
- print i：在一行中输出第 i 行值的个数 k 和这 k 个值，用一个空格隔开。
行为空时只输出 0。
命令中出现的行号和值的位置一定存在。
第一行给出命令数 q，接下来 q 行每行一条命令。
每个 print 输出一行，最后一行输出剩下的行数和整张表中值的个数，用一个空格隔开。
试着为每一行按需要单独申请内存（C 用 malloc、realloc、free，C++ 用 std::vector<std::vector<int>>）。
copy 新申请一块内存并把值复制进去，del 归还那一行的内存块。

输入
1 ≤ q ≤ 50,000，-10⁹ ≤ v ≤ 10⁹。
所有 new 的 k 合计不超过 100,000。
任何时候表的行数不超过 5,000，整张表的值不超过 500,000 个，copy 复制的值合计不超过 500,000 个，print 输出的值合计不超过 30,000 个。
输出
每个 print 一行，最后一行输出 "行数 值的个数"
样例 1 · stdin
9
new 3 1 2 3
copy 1
set 2 1 9
add 1 4
new 0
add 3 -5
del 2
print 1
print 2
stdout
4 1 2 3 4
1 -5
2 5
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 2 种语言题解

本题只接受 C 和 C++。
为每一行亲自申请和归还内存是这两种语言的事；Python、JavaScript、TypeScript、Java、C#、Craykon 的列表会自己变长，由垃圾回收器清理（这些语言做 copy 时也要另建副本，例如 row[:]、[...row]、new ArrayList<>(row)、new List<int>(row)）。
C 为每行放一个含 int *data、长度、容量的结构体，存放各行的表也用 Row * 申请，所以是两层申请。
扩容时先检查 realloc 返回的指针再保存；del 在 free(data) 之后要挪动重叠的位置，所以用 memmove 而不是 memcpy。
对表做 realloc 时内存块可能搬走，之前拿到的 &t.rows[i] 这类指针要重新取。
最后先逐行 free，再 free 整张表。
C++ 由 std::vector 负责申请、扩容和归还（RAII），像 std::vector<int> dup = rows[i]; 这样复制，会把所有值搬进新的内存块。
四个陷阱：① 在 C 中像 t.rows[n] = t.rows[i]; 这样给结构体赋值，只复制了 data 指针，两行共用一块内存。
对一行 set，另一行也跟着变，最后同一块内存被 free 两次，程序中止。
② memcpy(dst, src, len) 的第三个参数是字节数而不是格子数。
必须是 len * sizeof(int)，只传 len 只会复制前四分之一。
③ 在 C++ 中，auto row = rows[i]; row.push_back(v); 是追加到副本上。
要改原来的行，用 auto &row。
④ 在 C++ 中 row.reserve(k) 之后往 row[j] 写，reserve 只增加容量，大小仍是 0，这一行就保持为空。
用 std::vector<int> row(k) 或 resize(k) 来建出格子。

C++main.cpp · 45 行
#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    // 바깥 vector가 줄들을, 안쪽 vector가 줄마다 값들을 빌려 쥔다. 지워지면 알아서 돌려준다(RAII)    std::vector<std::vector<int>> rows;    int q;    std::cin >> q;    std::string cmd;    while (q--) {        std::cin >> cmd;        int i, j, k, v;        if (cmd == "new") {            std::cin >> k;            std::vector<int> row(k);  // 크기 k: 칸이 k개 생긴다(reserve는 칸을 만들지 않는다)            for (int &x : row) std::cin >> x;            rows.push_back(std::move(row));        } else if (cmd == "copy") {            std::cin >> i;            std::vector<int> dup = rows[i - 1];  // vector 복사는 새 블록을 빌려 값을 모두 옮긴다(깊은 복사)            rows.push_back(std::move(dup));        } else if (cmd == "add") {            std::cin >> i >> v;            rows[i - 1].push_back(v);        } else if (cmd == "set") {            std::cin >> i >> j >> v;            rows[i - 1][j - 1] = v;        } else if (cmd == "del") {            std::cin >> i;            rows.erase(rows.begin() + (i - 1));  // 그 줄의 블록을 돌려주고 뒤를 당긴다        } else {            std::cin >> i;            const auto &row = rows[i - 1];            std::cout << row.size();            for (int x : row) std::cout << ' ' << x;            std::cout << '\n';        }    }    long long cells = 0;    for (const auto &row : rows) cells += row.size();    std::cout << rows.size() << ' ' << cells << '\n';}
Cmain.c · 98 行
#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct {    int *data; /* 이 줄의 값들을 담으려고 빌린 블록 */    int len;   /* 들어 있는 값의 수 */    int cap;   /* 빌린 칸의 수 */} Row; typedef struct {    Row *rows;    int n, cap;} Table; /* 빌리기에 실패하면 멈춘다(받은 포인터를 확인한 다음에 담는다) */static void *grow(void *p, size_t count, size_t size) {    void *q = realloc(p, count * size);    if (q == NULL) {        fprintf(stderr, "out of memory\n");        exit(1);    }    return q;} /* 표 끝에 빈 줄 자리를 하나 만들어 그 주소를 돌려준다.   표의 블록이 옮겨질 수 있으니, 이 함수를 부르기 전에 쥔 Row 포인터는 부른 뒤에 쓰지 않는다 */static Row *append_row(Table *t, int cap) {    if (t->n == t->cap) {        t->cap = t->cap ? t->cap * 2 : 4;        t->rows = grow(t->rows, (size_t)t->cap, sizeof *t->rows);    }    Row *r = &t->rows[t->n++];    r->len = 0;    r->cap = cap > 0 ? cap : 1;    r->data = malloc((size_t)r->cap * sizeof *r->data);    if (r->data == NULL) exit(1);    return r;} static void push(Row *r, int v) {    if (r->len == r->cap) {        r->cap *= 2;        r->data = grow(r->data, (size_t)r->cap, sizeof *r->data);    }    r->data[r->len++] = v;} int main(void) {    Table t = {NULL, 0, 0};    int q, i, j, k, v;    char cmd[8];    if (scanf("%d", &q) != 1) return 0;    while (q--) {        scanf("%7s", cmd);        if (strcmp(cmd, "new") == 0) {            scanf("%d", &k);            Row *r = append_row(&t, k);            for (j = 0; j < k; j++) {                scanf("%d", &v);                push(r, v);            }        } else if (strcmp(cmd, "copy") == 0) {            scanf("%d", &i);            int len = t.rows[i - 1].len;            Row *dst = append_row(&t, len);  /* 먼저 자리를 만들고 */            const Row *src = &t.rows[i - 1]; /* 그다음 원본 주소를 쥔다 */            memcpy(dst->data, src->data, (size_t)len * sizeof *src->data); /* 바이트 수 = 칸 수 × 칸 크기 */            dst->len = len;        } else if (strcmp(cmd, "add") == 0) {            scanf("%d %d", &i, &v);            push(&t.rows[i - 1], v);        } else if (strcmp(cmd, "set") == 0) {            scanf("%d %d %d", &i, &j, &v);            t.rows[i - 1].data[j - 1] = v;        } else if (strcmp(cmd, "del") == 0) {            scanf("%d", &i);            free(t.rows[i - 1].data);            /* 뒤의 줄들을 한 칸씩 당긴다: 겹치는 자리라 memcpy가 아니라 memmove */            memmove(&t.rows[i - 1], &t.rows[i], (size_t)(t.n - i) * sizeof *t.rows);            t.n--;        } else {            scanf("%d", &i);            const Row *r = &t.rows[i - 1];            printf("%d", r->len);            for (j = 0; j < r->len; j++) printf(" %d", r->data[j]);            printf("\n");        }    }    long long cells = 0;    for (i = 0; i < t.n; i++) {        cells += t.rows[i].len;        free(t.rows[i].data); /* 줄마다 빌린 블록을 돌려주고 */    }    free(t.rows); /* 마지막으로 표의 블록을 돌려준다 */    printf("%d %lld\n", t.n, cells);    return 0;}