3711. T3-[CSP-S 2023] 结构体struct
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 在 `C++` 等高级语言中，除了 `int` 和 `float` 等基本类型外，通常还可以自定义结构体类型。 在本题当中，你需要模拟一种类似 `C++` 的高级语言的结构体定义方式，并计算出相应的内存占用等信息。 在这种语言中，基本类型共有 44 种：`byte`，`short`，`int`，`long`，分别占据 1,2,4,81,2,4,8 字节的空间。 定义一个结构体**类型**时，需要给出**类型名**和**成员**，其中每个成员需要按顺序给出**类型**和**名称**。 类型可以为基本类型，也可以为**先前定义过**的结构体类型。 注意，定义结构体**类型**时不会定义具体元素，即不占用内存。 定义一个**元素**时，需要给出元素的**类型**和**名称**。 元素将按照以下规则占据内存： - 元素内的所有成员将按照**定义时给出的顺序**在内存中排布，对于类型为结构体的成员同理。 - 为了保证内存访问的效率，元素的地址占用需要满足**对齐规则**，即任何类型的**大小**和该类型元素在内存中的**起始地址**均应对齐到该类型对齐要求的**整数倍**。具体而言： 对于基本类型：对齐要求等于其占据空间大小，如 int 类型需要对齐到 44 字节，其余同理。 - 对于结构体类型：对齐要求等于其成员的对齐要求的**最大值**，如一个含有 int 和 short 的结构体类型需要对齐到 44 字节。 以下是一个例子（以 `C++` 语言的格式书写）： ``` struct d { short a; int b; short c; }; d e; ``` 该代码定义了结构体类型 `d` 与元素 `e`。 元素 `e` 包含三个成员 `e.a`，`e.b`，`e.c`，分别占据第 0∼10∼1，4∼74∼7，8∼98∼9 字节的地址。 由于类型 `d` 需要对齐到 44 字节，因此 `e` 占据了第 0∼110∼11 字节的地址，大小为 1212 字节。 你需要处理 nn 次操作，每次操作为以下四种之一： 1. 定义一个结构体类型。具体而言，给定正整数 kk 与字符串 s,t1,n1,...,tk,nks,t1,n1,...,tk,nk，其中 kk 表示该类型的成员数量，ss 表示该类型的类型名，t1,t2,...,tkt1,t2,...,tk 按顺序分别表示每个成员的类型，n1,n2,...,nkn1,n2,...,nk 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求，用一个空格分隔。 2. 定义一个元素，具体而言，给定字符串 tt，nn 分别表示该元素的类型与名称。所有被定义的元素将按顺序，从内存地址为 00 开始依次排开，并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。 3. 访问某个元素。具体而言，给定字符串 ss，表示所访问的元素。与 C++ 等语言相同，采用 . 来访问结构体类型的成员。如 a.b.c，表示 a 是一个已定义的元素，它是一个结构体类型，有一个名称为 b 的成员，它也是一个结构体类型，有一个名称为 c 的成员。你需要输出如上被访问的**最内层**元素的起始地址。 4. 访问某个内存地址。具体而言，给定非负整数 addraddr，表示所访问的地址，你需要判断是否存在一个**基本类型**的元素占据了该地址。若是，则按操作 33 中的访问元素格式输出该元素；否则输出 ERR。 ## 输入格式 第 11 行：一个正整数 nn，表示操作的数量。 接下来若干行，依次描述每个操作，每行第一个正整数 opop 表示操作类型： - 若 op=1op=1，首先输入一个字符串 ss 与一个正整数 kk，表示类型名与成员数量，接下来 kk 行每行输入两个字符串 titi，nini，依次表示每个成员的类型与名称。 - 若 op=2op=2，输入两个字符串 tt，nn，表示该元素的类型与名称。 - 若 op=3op=3，输入一个字符串 ss，表示所访问的元素。 - 若 op=4op=4，输入一个非负整数 addraddr，表示所访问的地址。 ## 输出格式 输出 nn 行，依次表示每个操作的输出结果，输出要求如题目描述中所述。 ## 数据范围 对于全部数据，满足 1\len\le1001\len\le100，1\lek\le1001\lek\le100，0\leaddr\le10180\leaddr\le1018。 所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 1010 个字符的小写字母组成，且都不是 `byte`，`short`，`int`，`long`（即不与基本类型重名）。 所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。 但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体或元素名称相同。 保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。 保证任意结构体大小及定义的元素占据的最高内存地址均不超过 10181018。  特殊性质 AA：没有操作 11； 特殊性质 BB：只有一个操作 11； 特殊性质 CC：所有操作 11 中给出的成员类型均为基本类型； 特殊性质 DD：基本类型只有 `long`。 ```in4 5 1 a 2 short aa int ab 1 b 2 a ba long bb 2 b x 3 x.ba.ab 4 10 ``` ```out4 8 4 16 8 0 4 x.bb ``` ## 说明 结构体类型 `a` 中，`int` 类型的成员 `aa` 占据第 0∼30∼3 字节地址，`short` 类型的成员 `ab` 占据第 4∼54∼5 字节地址。 又由于其对齐要求为 44 字节，可得其大小为 88 字节。 由此可同理计算出结构体类型 `b` 的大小为 1616 字节，对齐要求为 88 字节。 ## 提示 对于结构体类型的对齐要求和大小，形式化的定义方式如下： - 设该结构体内有 kk 个成员，其大小分别为 s1,\dots,sks1,\dots,sk，对齐要求分别为 a1,\dots,aka1,\dots,ak； - 则该结构体的对齐要求为 a=max{a1,\dots,ak}a=max{a1,\dots,ak}； - 再设这些成员排布时的**地址偏移量**分别为 o1,\dots,oko1,\dots,ok，则： o1=0o1=0； - 对于 i=2,\dots,ki=2,\dots,k，oioi 为满足 oi-1+si-1\leoioi-1+si-1\leoi 且 aiai 整除 oioi 的最小值； - 则该结构体的大小 ss 为满足 ok+sk\lesok+sk\les 且 aa 整除 ss 的最小值； 对于定义元素时的内存排布，形式化的定义方式如下： - 设第 ii 个被定义的元素大小为 sisi，对齐要求为 aiai，起始地址为 bibi； - 则 b1=0b1=0，对于 2\lei2\lei，bibi 为满足 bi-1+si-1\lebibi-1+si-1\lebi 且 aiai 整除 bibi 的最小值。