#1767. tree
tree
tree
题目描述
标题: tree - Problem - QOJ.ac
#10376. tree
The problem was used in the following contests:
这是一道交互题。
Scape 家的后院种了许多二叉树,树上的每个结点最多只有一个父结点、一个左儿子和一个右儿子。作为他家的园丁,你需要帮他维护这些二叉树。
结点有两种状态:正常状态以及枯萎状态。这些二叉树共有 n 个结点,分别编号为 1 到 n。初始时有 n 棵二叉树,分别编号为 1 到 n,二叉树 i 上只有结点 i 这一个结点,且所有结点都处于正常状态。
接下来可能发生以下的 3 种事件:
- Scape 要求你把二叉树 x 和二叉树 y 连接成一棵新的二叉树。设二叉树 x 中序遍历得到的序列为 a1,a2,...,an,二叉树 y 中序遍历得到的序列为 b1,b2,...,bm,那么新的二叉树中序遍历得到的序列应为 a1,a2,...,an,b1,b2,...,bm。
- Scape 要求你把二叉树 x 分离成两棵新的二叉树。设二叉树 x 中序遍历得到的序列为 a1,a2,...,an,那么新的两棵二叉树中序遍历得到的序列应分别为 a1,a2,...,ak 和 ak+1,ak+2,...,an。
- Mythological 打算来观赏二叉树 x。为了使这棵树变得更美观,Scape 要求你使这棵树的所有结点都变为正常状态,且所有结点的深度不能超过 maxdep。一个结点的深度即为祖先结点的个数加 1,根结点深度为 1。
为了对这些树进行调整,你给每棵树分配了两个手下,我们称之为某棵树的 1 号手下或者 2 号手下,初始时他们都站在负责的树的唯一一个结点上。每次你可以让某个手下移动到一个相邻的结点,这时你可以命令他把该结点的某个儿子修改为某个结点(原来的儿子的子树会分离出去;新的儿子的父结点也会同时修改为当前结点)。由于某种神秘力量的影响,修改某个结点的儿子后该结点的所有祖先结点(包括自己)都会变为枯萎状态。最后他会给该结点浇上水,如果此时该结点的所有儿子(忽略空儿子)都处于正常状态的话,这个结点就会变为正常状态。
简要题意:要求用二叉树维护若干个序列。交互库会对每棵树提供两个指针,分别指向树上的某个结点。允许修改某个指针指向结点的儿子、更新某个指针指向结点的子树信息和以及把某个指针移动到相邻结点。需要通过这些指针完成合并、分裂、查询操作。
任务介绍
你需要实现以下的四个函数:
-
init(n, maxdep, maxcnt)- 该函数只会在初始调用一次,你可以在此时进行初始化的操作。
-
join(x, y, &id1, &id2)- 表示 Scape 要求你把二叉树 x 和二叉树 y 连接成一棵新的二叉树。设此时存在的二叉树最大的编号为 tot,那么新的二叉树编号为 tot+1。事件结束后不存在编号为 x 和 y 的二叉树,并且也不能再指挥给它们分配的手下。
- 连接两棵二叉树后,需要决定给二叉树 tot+1 分配的两个手下的位置,只能从分配给二叉树 x,y 的 4 个手下当前所处的位置中选择。二叉树 id+1 的 1 号手下位于手下 id1 的位置,2 号手下位于手下 id2 的位置。请对 id1,id2 分别赋值,值为 1,2 分别表示是二叉树 x 的 1,2 号手下;值为 3,4 分别表示是二叉树 y 的 1,2 号手下。
-
split(x, k, &p1, &p2, &p3, &p4)- 表示 Scape 要求你把二叉树 x 分离成两棵新的二叉树。设此时存在的二叉树最大的编号为 tot,那么新的二叉树编号为 tot+1 和 tot+2。二叉树 x 中序遍历的前 k 个结点会构成二叉树 tot+1,剩余的结点会构成二叉树 tot+2。事件结束后不存在编号为 x 的二叉树,并且也不能再指挥给它分配的手下。
- 你需要对 p1,p2,p3,p4 赋值来指定给两棵新的二叉树分配的手下的位置。p1,p2 分别表示二叉树 tot+1 上的 1,2 号手下所处的结点编号;p3,p4 分别表示二叉树 tot+2 上的 1,2 号手下所处的结点编号。
- 保证 1≤k<size(x)。
-
visit(x)- 表示 Mythological 打算观赏二叉树 x。你需要按 Scape 的要求调整这棵树的形态,并且返回调整过后这棵树的根结点的编号。
你可以调用 move() 来指挥你的手下,但是该函数的总调用次数不能超过 2×106 次,并且在每次事件中(即交互库调用 join()/split()/visit() 函数到该函数结束的这段时间内)move() 函数的调用次数不能超过 maxcnt 。
-
move(k, id, x, c, y)- 把分配给二叉树 k 的 id 号手下(id 为 1 或 2)移动到结点 x。结点 x 要么是该手下原来所处位置(即不移动),要么是其相邻结点。
- 之后手下会把该结点的儿子 c(c=0 表示左儿子,c=1 表示右儿子)改为结点 y(y=0 表示空结点),然后给该结点浇水。
- 如果不希望修改 x 的两个儿子,请把 c 和 y 设置为 −1,这样不会导致 x 的祖先结点变为枯萎状态。
实现细节
你只能提交一个源文件实现上述的函数,并且遵循下面的命名和接口。源代码中需要包含头文件 tree.h。
void init(int n, int maxdep, int maxcnt);
void join(int x, int y, int &id1, int &id2);
void split(int x, int k, int &p1, int &p2, int &p3, int &p4);
int visit(int x);
void move(int k, int id, int x, int c, int y);
下发文件中附有样例程序。
评测方式
交互库将读入如下格式的输入数据:
第一行为四个整数 n,m,maxdep,maxcnt,m 表示事件的个数。读入此行后交互库会调用一次 init() 函数。
接下来 m 行,每行描述一次事件。若为事件 join,输入三个整数 1 x y;若为事件 split,输入三个整数 2 x k;若为事件 visit,输入两个整数 3 x。读入每行后交互库会调用对应的函数。
交互库会在每次调用 visit() 函数后进行某些输出,如果输出与数据的输出文件一致且 move() 函数的调用次数未超过上限,则视为通过该测试点。如果你在调用 move() 函数时传入了非法的参数或者返回值不合法,交互库会马上退出。
通过访问输入输出文件、攻击评测系统或攻击评测库等方式所得分数无效。
子任务
- 子任务 1(15分):保证 1≤n,m≤1000,maxdep=2×105,maxcnt=2×106。
- 子任务 2(25分):保证 1≤n,m≤30000,maxdep=2×105,maxcnt=2×106。
- 子任务 3(15分):保证 1≤n,m≤105,split 和 visit 事件的总个数不超过 10000,maxdep=2×105,maxcnt=2×106。
- 子任务 4(15分):保证 1≤n,m≤2×105,没有 split 事件,visit 事件的个数不超过 20000,maxdep=60,maxcnt=250。
- 子任务 5(30分):保证 1≤n,m≤2×105,split 和 visit 事件的总个数不超过 20000,maxdep=60,maxcnt=250。
请注意最终测评使用的 tree.h 与下发的文件并不一致。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 9 200000 200000
3 3
1 4 1
2 5 1
3 6
1 7 6
1 2 8
2 9 2
1 3 10
3 12
3
4
124576086
样例 2
1000 1000 200000 200000
3 51
1 219 200
1 311 171
1 324 87
2 1002 1
1 540 941
3 453
2 1003 1
3 762
1 579 108
3 7
3 211
3 537
2 1001 1
3 570
3 768
1 718 516
1 987 360
3 267
1 633 612
1 902 156
1 70 1013
2 1006 1
2 1016 1
1 73 781
1 981 799
1 790 554
3 817
1 605 344
3 387
2 1012 1
3 407
3 965
1 71 413
3 332
1 284 702
2 1015 1
1 470 249
2 1028 1
3 127
3 649
2 1022 1
1 759 722
1 314 629
1 824 820
1 128 294
1 1036 704
1 511 482
2 1021 1
2 1041 1
2 1027 1
3 843
2 1038 1
1 1032 749
2 1039 1
2 1040 2
1 532 843
2 1024 1
3 974
1 841 397
2 1053 1
1 1030 963
1 321 561
3 465
3 1011
2 1031 1
3 13
1 322 529
1 407 954
3 177
1 519 893
1 657 85
3 445
1 143 403
1 346 28
1 487 5
2 1023 1
2 1020 1
2 1062 1
3 931
1 953 694
1 572 247
2 1070 1
1 255 765
3 850
2 1050 1
1 93 742
2 1078 1
3 111
2 1085 1
2 1066 1
1 263 865
1 984 35
3 113
1 45 473
1 317 384
1 393 924
3 586
2 1014 1
2 1037 1
3 405
3 283
1 374 831
3 463
1 958 410
1 698 185
1 194 847
1 95 258
1 202 663
1 771 364
2 1107 1
2 1106 1
1 849 539
3 840
1 618 993
2 1061 1
3 86
1 921 46
1 465 1109
3 796
2 1071 1
1 1110 276
3 179
3 183
3 365
2 1093 1
2 1055 1
3 919
2 1079 1
2 1113 1
3 852
1 625 739
1 210 367
2 1069 1
3 281
1 1098 727
2 1130 1
2 1065 1
1 950 365
2 1117 1
1 772 239
1 112 660
2 1141 1
3 730
1 164 892
1 857 1099
1 780 754
3 375
3 701
2 1146 1
2 1009 1
3 696
1 1096 451
3 14
1 566 797
1 48 14
1 844 1097
2 1142 1
1 301 714
3 443
1 588 674
3 1018
1 1068 992
3 104
1 405 4
1 351 483
3 990
2 1153 1
2 1152 2
1 19 683
2 1154 1
1 316 971
1 983 1018
1 1127 176
3 369
3 29
1 373 205
2 1159 1
2 1172 1
1 10 318
1 338 382
1 816 664
1 717 503
2 1103 1
2 1178 1
1 697 1019
1 999 1118
1 418 1151
2 1188 1
2 1155 1
1 876 1119
1 735 880
2 1162 1
3 715
3 333
2 1145 1
2 1186 1
2 1158 1
2 1082 1
2 1167 1
2 1147 1
2 1112 1
1 559 266
1 288 1101
3 858
2 1165 1
1 870 12
2 1180 1
1 68 52
2 1067 1
3 507
1 283 969
3 1054
1 852 500
1 1060 267
2 1092 1
1 406 1139
2 1133 1
3 1116
2 1105 1
1 484 328
3 53
1 300 55
2 1058 1
1 538 1232
1 241 982
3 568
2 1170 1
3 475
2 1160 2
2 1193 1
3 1148
2 1236 1
2 1138 1
2 1222 1
1 1177 49
2 1212 2
2 1181 1
1 380 978
2 1226 1
3 356
1 327 320
1 64 656
3 926
3 471
2 1211 1
2 1161 1
1 943 1217
1 1239 1087
1 855 622
1 617 285
1 431 1257
2 1263 1
1 1198 1125
3 549
2 1270 1
1 31 339
1 372 682
2 1194 1
1 417 91
2 1277 1
1 158 1241
1 331 15
3 455
1 730 180
2 1120 1
1 265 756
3 1104
2 1116 1
1 402 1253
1 744 401
3 434
3 898
3 1283
2 1095 1
3 606
1 187 445
1 329 385
2 1215 1
1 525 933
3 75
1 1131 226
3 309
3 1115
1 872 104
1 833 325
3 462
2 1274 1
1 686 79
3 449
2 1302 1
2 1293 1
1 218 675
1 368 357
2 1281 1
3 315
1 783 611
3 815
1 246 599
1 666 139
2 1285 1
1 1273 1200
2 1104 1
1 1049 277
2 1231 1
1 118 83
3 481
2 1322 1
3 535
2 1298 1
3 44
1 462 211
3 1203
2 1297 1
3 336
1 778 523
1 1034 909
3 1324
1 867 627
1 1247 350
2 1331 1
3 251
2 1316 1
2 1319 1
1 476 768
2 1308 1
2 1249 1
1 708 1048
3 1052
1 733 838
3 655
3 1086
1 866 506
1 1144 589
2 1311 1
1 570 400
2 1250 1
3 307
1 1011 313
3 369
2 1258 1
3 903
1 534 598
2 1313 1
1 658 34
3 236
1 326 801
1 189 302
1 502 96
1 715 135
1 869 1294
2 1312 1
2 1337 1
2 1357 1
1 635 58
2 1307 1
3 696
2 1129 1
1 259 920
2 1332 1
3 777
1 232 67
2 1377 1
3 531
3 942
1 886 1088
1 986 659
3 17
2 1365 1
3 430
2 1360 1
2 1333 1
2 1173 1
3 274
2 1179 1
1 940 518
2 1327 1
2 1347 1
1 411 1318
3 850
2 1288 1
1 596 949
2 1346 1
2 1282 1
3 630
1 851 1187
3 942
2 1348 1
2 1296 1
1 791 77
1 1279 225
1 597 137
2 1354 1
1 1334 116
2 1102 1
2 1400 1
2 1171 1
2 1383 1
2 1289 1
3 342
1 1382 810
1 1184 1299
2 1223 1
2 1292 1
1 148 1235
2 1094 1
1 998 296
1 111 422
2 1414 1
3 1199
1 1254 846
1 775 1429
2 1403 1
3 453
2 1267 1
3 122
2 1330 1
3 434
1 1283 945
2 1380 1
1 44 1221
2 1408 1
1 434 1434
2 1418 1
1 606 1269
1 264 166
3 834
1 547 388
3 584
2 1447 1
2 1450 1
2 1442 2
1 347 84
3 175
3 42
2 1280 1
3 712
1 435 8
3 420
1 74 18
3 1243
2 1435 2
2 1459 1
1 179 254
3 1044
1 888 240
1 748 621
3 905
2 1460 1
1 272 395
1 680 1364
3 1454
1 1345 964
3 394
1 345 798
2 1415 1
1 356 430
3 774
1 1326 394
2 1351 1
3 520
1 235 736
3 133
1 1284 671
2 1473 1
1 1278 1492
1 628 129
3 50
3 662
3 695
2 1265 1
2 1264 2
1 514 13
1 1197 103
2 1453 1
3 461
2 1479 1
3 1304
2 1471 1
1 396 864
3 437
3 433
1 1260 425
2 1461 1
2 1430 1
1 1168 65
1 804 481
3 1238
1 1157 1373
2 1472 1
3 428
2 1517 1
3 1484
2 1474 1
1 1209 437
2 1395 1
2 1372 1
1 88 492
2 1493 1
2 1218 1
2 1502 1
3 1353
2 1484 2
3 1370
1 155 1464
2 1485 1
1 1427 918
2 1455 1
1 43 661
1 1405 1266
1 499 877
2 1468 1
3 17
1 47 1533
1 457 826
1 81 57
3 24
3 1538
2 1551 1
1 105 1300
2 1515 1
2 1516 1
1 315 191
2 1482 1
1 163 423
1 569 362
3 1234
2 1483 2
3 654
3 308
3 493
3 192
1 832 646
2 1362 1
2 1496 1
2 1539 1
2 1489 1
1 546 968
1 595 236
3 1301
3 475
1 408 1480
3 162
1 441 903
1 654 299
1 17 1089
3 1115
2 1518 1
2 1571 1
1 253 146
1 1206 1556
3 467
1 223 861
2 1413 1
1 280 711
2 1576 1
3 794
3 977
2 1567 1
2 1510 1
3 1359
2 1542 1
2 1466 1
1 1025 509
1 764 587
3 290
1 86 1340
1 906 433
2 1604 1
3 827
2 1587 1
3 354
2 1555 1
3 668
3 192
3 195
1 1532 614
2 1497 1
1 198 1370
3 935
1 796 905
1 298 644
2 1478 1
1 769 961
3 1470
1 23 973
2 1565 1
3 917
3 494
1 1577 428
3 1545
2 1550 1
1 278 574
1 590 1081
1 603 667
3 814
1 468 763
2 1552 1
3 1114
1 186 1091
3 932
1 22 684
2 1620 1
1 732 438
1 291 424
3 292
1 1199 1404
2 1639 1
1 1554 1462
3 1301
3 1407
3 673
3 1559
2 1547 1
3 567
2 1384 1
2 1588 1
1 16 1148
1 1524 593
2 1530 1
2 1456 1
2 1580 1
3 1499
2 1617 1
1 813 251
1 260 1248
2 1545 1
2 1627 1
1 162 1202
3 645
1 1505 976
3 788
1 117 190
1 553 1052
3 565
3 348
3 1314
1 948 376
2 1650 1
3 323
1 1443 1662
2 1581 1
1 245 896
1 1305 1140
1 1137 1486
1 1057 1343
2 1607 1
3 762
2 1603 1
1 789 340
3 1323
3 290
2 1602 1
2 1678 1
3 898
3 1526
1 222 1601
2 1605 1
2 1511 1
1 805 782
2 1361 1
2 1503 1
1 1488 641
2 1668 1
1 562 274
2 1477 1
1 899 1407
1 1210 1240
1 1655 392
1 466 120
3 1406
3 845
3 370
3 199
1 1591 1213
2 1642 1
2 1638 1
3 1290
3 792
2 1525 1
1 962 1387
3 1691
1 531 53
1 1707 1652
1 923 898
2 1688 1
1 1203 450
1 1268 398
2 1705 1
1 1687 1295
1 624 817
2 1586 1
3 615
3 480
3 1175
1 1309 1276
2 1708 1
3 928
3 757
1 527 54
3 755
3 147
3 1529
3 881
2 1701 1
3 1457
2 1659 1
2 1716 1
3 480
1 1328 1544
1 1033 1609
3 1646
2 1722 1
1 149 700
3 1727
1 505 1353
1 504 1371
3 427
2 1629 1
2 1704 1
2 1718 1
2 1660 1
3 802
3 221
3 181
3 1420
3 213
3 719
1 1077 807
1 221 472
2 1740 1
1 889 1755
1 645 436
1 335 1540
1 130 1686
1 1397 273
3 1615
2 1761 1
1 594 1115
1 1029 1245
1 1228 72
2 1546 1
2 1676 1
1 452 643
1 1391 24
3 1303
1 1163 213
2 1563 1
3 1063
3 1661
3 575
2 1683 1
1 1216 655
3 427
3 1640
3 349
1 1703 421
2 1672 1
3 1754
1 934 443
3 1090
3 1522
2 1779 1
1 825 665
3 610
2 1765 1
1 183 1237
3 1469
1 1169 1637
2 1438 1
2 1726 1
3 1771
3 648
3 282
2 1759 1
2 1762 1
1 1243 856
2 1616 1
3 319
1 848 1789
2 1564 1
1 282 586
1 1251 975
3 653
3 1246
1 508 1291
3 1522
3 1339
1 1763 549
3 390
2 1675 1
3 819
2 1758 2
1 600 1710
1 713 69
1 1509 228
1 1647 1076
1 262 353
2 1780 1
2 1754 1
1 134 429
1 637 1183
1 1132 1775
1 459 960
3 358
2 1799 1
1 990 1134
1 1715 1714
3 747
2 1667 1
2 1693 1
1 689 980
1 412 1441
3 140
3 151
1 1422 647
1 632 62
2 1828 1
1 1794 1164
2 1717 1
2 1782 1
2 1786 1
3 710
1 560 734
1 1262 1838
2 1628 1
2 1834 1
3 1557
2 1847 1
2 1615 1
1 550 1830
1 1845 370
1 257 1732
3 1124
2 1739 1
1 1842 1220
3 208
2 1760 1
1 486 1393
1 289 1592
1 275 1385
2 1769 1
1 184 1776
3 850
2 1865 1
1 1854 607
1 1379 1737
2 1721 1
2 1725 1
1 1735 196
2 1649 1
2 1579 1
3 1634
3 1007
1 1000 802
3 1195
1 127 777
3 613
2 1802 2
3 323
1 512 1054
1 755 1549
3 319
3 1425
3 750
2 1767 1
2 1666 1
2 1813 1
2 1874 1
1 1042 1126
1 541 1501
1 1527 1646
1 75 1791
1 38 1753
3 1425
1 234 1401
1 1593 911
1 1583 1805
2 1790 1
2 1807 1
3 1287
2 1665 1
2 1886 1
3 133
1 1 414
1 281 585
1 216 1770
1 927 415
3 1888
1 1350 474
3 449
1 1720 1768
2 1907 1
3 1673
1 863 41
1 706 1862
3 1026
1 1271 1884
3 609
2 1815 1
2 1922 1
2 1837 1
1 1448 662
3 1738
2 1816 1
2 1914 1
3 1925
2 1808 1
3 161
1 496 1751
1 925 1192
1 1323 141
2 1772 1
1 699 1190
1 685 836
2 1917 1
1 453 427
1 1926 1242
1 871 1869
2 1900 1
2 1901 1
1 1598 1893
1 746 1010
2 1948 1
2 1866 1
1 875 1047
3 1694
2 1923 1
2 1905 1
1 1793 931
1 1643 912
3 1436
3 989
2 1940 1
1 1261 1149
3 721
2 1859 1
2 1919 1
1 1809 1166
2 1938 1
1 387 1916
2 1955 1
2 1943 1
3 304
3 1792
3 803
1 1883 1585
2 1766 1
1 1964 1623
3 623
3 1437
1 1185 229
2 1624 2
3 897
3 231
2 1677 1
2 1939 1
2 1612 1
1 935 513
1 1937 907
2 1773 1
2 1962 2
1 1083 497
1 997 1543
1 195 1953
1 126 507
3 1425
1 1498 1870
1 862 1996
1 1367 1954
2 1944 1
1 1613 910
3 1804
3 1423
1 297 1651
1 250 464
3 11
2 1904 1
3 1860
3 634
2 1698 2
1 636 1711
2 1783 1
3 854
3 766
3 1915
3 107
2 1931 1
2 1873 1
1 11 1841
2 1995 1
1 1424 786
1 1594 1252
3 1320
3 323
2 1537 1
1 890 829
2 1985 1
3 76
1 1897 269
51
453
762
7
211
537
570
768
267
817
387
407
965
332
127
649
843
974
465
200
13
177
445
931
850
111
113
586
405
283
463
840
86
796
179
183
365
919
852
281
730
375
701
696
14
443
941
104
990
369
29
715
333
858
507
704
214899739
53
568
475
857
356
926
471
549
455
45267449
434
898
202
606
75
309
963
462
449
315
815
481
535
44
255
336
83
251
294
655
953
307
369
903
236
696
777
531
942
17
430
274
850
630
942
342
697
453
122
434
834
584
175
42
712
420
241
511
905
851
394
774
520
133
50
662
695
461
79
437
433
971
428
-582680832
374
534
17
24
964
397
654
308
493
192
682
475
162
963
467
794
977
139
290
827
354
668
192
195
935
876
917
494
10033980
814
156
932
292
682
180
673
65
567
622
645
788
565
348
265
323
762
118
290
898
940
730
845
370
199
317
792
266
615
480
674
928
757
755
147
58
881
981
480
659
253
427
802
221
181
410
213
719
46200468
686
470
43
575
427
697
349
130900620
407
481
610
158
364
648
282
319
653
365
481
277
390
819
358
747
140
151
710
325
843
208
850
5134010
324
351
613
323
319
886
750
886
46
133
119467200
449
17
516
609
53
8
161
326
45
989
721
304
296
803
623
473
897
231
886
362
983
11
143
634
854
766
65567158
107
484
323
76