5182 - NOIP CSP 2023 提高: 第三题 结构体（struct）
时间限制 : 1 秒
内存限制 : 512 MB
【题目背景】 在 C++ 等高级语言中，除了 int 和 float 等基本类型外，通常还可以自定义结构体类型。在本题当中，你需要模拟一种类似 C++ 的高级语言的结构体定义方式，并计算出相应的内存占用等信息。 【题目描述】 在这种语言中，基本类型共有 4 种：byte，short，int，long，分别占据 1, 2, 4, 8字节的空间。 定义一个结构体类型时，需要给出类型名和成员，其中每个成员需要按顺序给出类型和名称。类型可以为基本类型，也可以为先前定义过的结构体类型。注意，定义结构体类型时不会定义具体元素，即不占用内存。定义一个元素时，需要给出元素的类型和名称。元素将按照以下规则占据内存：
• 元素内的所有成员将按照定义时给出的顺序在内存中排布，对于类型为结构体的成员同理。
• 为了保证内存访问的效率，元素的地址占用需要满足对齐规 则，即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言：
– 对于基本类型：对齐要求等于其占据空间大小，如 int 类型需要对齐到 4字节，其余同理。
– 对于结构体类型：对齐要求等于其成员的对齐要求的 .最 .大 .值，如一个含有int 和 short 的结构体类型需要对齐到 4 字节。
以下是一个例子（以 C++ 语言的格式书写）
struct d {
short a;
int b;
short c;
};
d e;
该代码定义了结构体类型 d 与元素 e。元素 e 包含三个成员 e.a, e.b, e.c，分
别占据第 0 ∼ 1，4 ∼ 7，8 ∼ 9 字节的地址。由于类型 d 需要对齐到 4 字节，因此 e 占
据了第 0 ∼ 11 字节的地址，大小为 12 字节。
你需要处理 n 次操作，每次操作为以下四种之一：
1. 定义一个结构体类型。具体而言，给定正整数 k 与字符串 s, t1, n1, . . . , tk, nk，其中 k 表示该类型的成员数量，s 表示该类型的类型名，t1, t2, . . . , tk 按顺序分别表示每个成员的类型，n1, n2, . . . , nk 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求，用一个空格分隔。
2. 定义一个元素，具体而言，给定字符串 t，n 分别表示该元素的类型与名称。所有被定义的元素将按顺序，从内存地址为 0 开始依次排开，并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。
3. 访问某个元素。具体而言，给定字符串 s，表示所访问的元素。与 C++ 等语言相同，采用 . 来访问结构体类型的成员。如 a.b.c，表示 a 是一个已定义的元素，它是一个结构体类型，有一个名称为 b 的成员，它也是一个结构体类型，有
一个名称为 c 的成员。你需要输出如上被访问的最内层元素的起始地址。
4. 访问某个内存地址。具体而言，给定非负整数 addr，表示所访问的地址，你需要判断是否存在一个基本类型的元素占据了该地址。若是，则按操作 3 中的访问元素格式输出该元素；否则输出
输入
第 1 行：一个正整数 n，表示操作的数量。 接下来若干行，依次描述每个操作，每行第一个正整数 op 表示操作类型：
• 若 op = 1，首先输入一个字符串 s 与一个正整数 k，表示类型名与成员数量，接
下来 k 行每行输入两个字符串 ti，ni，依次表示每个成员的类型与名称。
• 若 op = 2，输入两个字符串 t，n，表示该元素的类型与名称。
• 若 op = 3，输入一个字符串 s，表示所访问的元素。
• 若 op = 4，输入一个非负整数 addr，表示所访问的地址。
输出
输出 n 行，依次表示每个操作的输出结果，输出要求如题目描述中所述。
样例
输入
5 1 a 2 short aa int ab 1 b 2 a ba long bb 2 b x 3 x.ba.ab 4 10
输出
8 4 16 8 0 4 x.bb
输入
100 4 0 4 4 2 byte szqir 2 long fweahddll 2 byte dvqu 3 szqir 2 long wqcnqxppvg 3 szqir 4 9 4 33 3 wqcnqxppvg 4 38 4 5 4 33 2 short erhxh 2 short wwsp 4 3 3 szqir 4 42 2 short pxkwnp 4 15 2 int teuwwrw 4 45 3 erhxh 2 int uuycypz 3 uuycypz 4 48 4 35 4 6 3 wqcnqxppvg 2 byte yvgc 3 yvgc 3 teuwwrw 4 25 3 fweahddll 3 wwsp 3 szqir 4 57 3 wwsp 3 fweahddll 4 7 4 22 4 16 4 54 3 pxkwnp 4 7 4 68 2 byte sulvy 3 erhxh 4 1 2 short yuoquzsyr 2 byte okdqtvqv 4 35 2 int xmsvcd 4 33 4 50 4 76 3 szqir 4 71 3 wqcnqxppvg 3 wqcnqxppvg 2 long zuwd 2 short lvvlezc 3 xmsvcd 2 short jad 3 erhxh 4 41 2 long hprwemliyo 3 teuwwrw 4 54 4 38 3 hprwemliyo 4 71 2 short ekqiko 4 42 3 wwsp 2 long iwqssghglm 3 hprwemliyo 2 byte rcjx 4 122 3 pxkwnp 4 60 2 byte krjasjxkp 4 22 4 61 3 erhxh 3 uuycypz 2 int cyyzsusp 4 108 2 int v 4 91 3 hprwemliyo 2 int oqk 3 szqir 2 long rjisljjxo 3 okdqtvqv 3 wqcnqxppvg 4 17 2 byte zdjdvzka 4 9
输出
ERR ERR 0 8 16 0 24 0 fweahddll ERR 24 ERR ERR ERR 32 34 ERR 0 ERR 36 fweahddll 40 ERR 32 44 44 ERR wwsp ERR 24 48 48 40 wqcnqxppvg 8 34 0 ERR 34 8 ERR ERR dvqu ERR 36 ERR ERR 49 32 ERR 50 52 wwsp 56 erhxh yuoquzsyr ERR 0 ERR 24 24 64 72 56 74 32 teuwwrw 80 40 ERR ERR 80 zuwd 88 teuwwrw 34 96 80 104 ERR 36 ERR 105 ERR ERR 32 44 108 cyyzsusp 112 ERR 80 116 0 120 52 24 ERR 128 fweahddll
输入
99 2 long mrbfn 4 1 3 mrbfn 3 mrbfn 3 mrbfn 3 mrbfn 2 byte oosmberlsb 3 mrbfn 3 oosmberlsb 2 byte auhmoewi 4 7 4 3 2 long jplopgx 4 0 4 31 2 int qqgjpu 2 long plfawkhtd 3 auhmoewi 3 plfawkhtd 2 int uwue 2 long muvlnlgqn 4 46 4 46 4 22 2 long inhosie 3 auhmoewi 3 oosmberlsb 2 byte pziz 2 byte anyxdruw 4 12 3 inhosie 4 3 4 38 4 39 4 82 4 83 2 byte jdyh 2 long ceqpfdrlx 2 byte tpy 3 inhosie 2 long cbnapeqnwr 3 mrbfn 3 qqgjpu 3 tpy 3 tpy 4 63 4 101 2 long fzck 3 pziz 2 byte qm 2 long vjslsy 3 jdyh 2 long isr 3 qm 3 isr 2 short tqsjlcgz 3 mrbfn 4 111 3 auhmoewi 2 long wbpatry 2 byte wdmtrievjf 2 byte ng 2 long cjzosekh 3 anyxdruw 2 int kpej 4 65 2 int ialhf 4 168 2 short ezgejozee 3 ceqpfdrlx 2 byte d 4 142 3 cjzosekh 3 muvlnlgqn 4 153 4 95 4 117 2 long ezfylph 2 byte ycytaxof 3 jplopgx 3 d 3 ycytaxof 4 8 2 short rgouqvt 4 196 2 byte nyelxwwdf 3 isr 4 136 2 long djm 2 long btwyo 2 short xnjpfuyas 4 227 2 long rflxy 4 247 4 243 4 129 3 ycytaxof 4 191 4 218
输出
0 mrbfn 0 0 0 0 8 0 8 9 mrbfn mrbfn 16 mrbfn ERR 24 32 9 32 40 48 ERR ERR jplopgx 56 9 8 64 65 ERR 56 mrbfn plfawkhtd plfawkhtd ERR ERR 66 72 80 56 88 0 24 80 80 inhosie ERR 96 64 104 112 66 120 104 120 128 0 ERR 9 136 144 145 152 65 160 anyxdruw 164 ERR 168 72 170 wbpatry 152 48 cjzosekh cbnapeqnwr vjslsy 176 184 16 170 184 oosmberlsb 186 ERR 188 120 wbpatry 192 200 208 ERR 216 ERR ERR tqsjlcgz 184 ERR rflxy
提示
【样例 1 解释】 结构体类型 a 中，int 类型的成员 aa 占据第 0 ∼ 3 字节地址，short 类型的成员ab 占据第 4 ∼ 5 字节地址。又由于其对齐要求为 4 字节，可得其大小为 8 字节。由此可同理计算出结构体类型 b 的大小为 16 字节，对齐要求为 8 字节。
【样例 2 解释】 第二个操作 4 中，访问的内存地址恰好在为了地址对齐而留下的“洞”里，因此没有基本类型元素占据它
【数据范围】 对于全部数据，满足 1 ≤ n ≤ 100，1 ≤ k ≤ 100，0 ≤ addr ≤ 10^18。 所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 10 个字符的小写字母组成，且都不是byte,short,int,long（即不与基本类型重名）。 所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。 但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体或元素名称相同。 保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。 保证任意结构体大小及定义的元素占据的最高内存地址均不超过 10^18。
