{"id":734,"date":"2021-08-07T11:33:22","date_gmt":"2021-08-07T03:33:22","guid":{"rendered":"https:\/\/nocriz.com\/?p=734"},"modified":"2021-10-02T02:57:36","modified_gmt":"2021-10-01T18:57:36","slug":"%e6%9d%ad%e7%94%b5%e5%a4%9a%e6%a0%a1%e7%ac%ac%e5%85%ad%e5%9c%ba1006-1007-1008%e9%a2%98%e8%a7%a3%ef%bc%8cstd","status":"publish","type":"post","link":"https:\/\/nocriz.com\/?p=734","title":{"rendered":"\u676d\u7535\u591a\u6821\u7b2c\u516d\u573a1006 1007 1008\u9898\u89e3\uff0cstd"},"content":{"rendered":"\n

\u9898\u662f\u6211\u51fa\u7684\uff0cstd\u662f\u6211\u5199\u7684\u30021006\u662f\u539f\u521b\u5957\u8def\u30021008\u662f\u539f\u521b\u8d2a\u5fc3\u30021007\u662f\u4eceCF\u4e0a\u7684\u9898\u52a0\u5f3a\u4e86\u4e00\u4e0b\u5b50\u51fa\u7684\u3002<\/p>\n\n\n\n\n\n\n\n\n\n1006<\/title>\n<\/head>\n<body><h2 id=\"1006\">1006<\/h2>\n<p>\u6b64\u9898\u7b97\u6cd5\u590d\u6742\u5ea6\u4e3a <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"35.06ex\" height=\"2.497ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -750 15496.4 1103.5\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.8ex;\"><defs><path id=\"MJX-11-TEX-I-1D442\" d=\"M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z\"><\/path><path id=\"MJX-11-TEX-N-28\" d=\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"><\/path><path id=\"MJX-11-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-11-TEX-N-6C\" d=\"M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z\"><\/path><path id=\"MJX-11-TEX-N-6F\" d=\"M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z\"><\/path><path id=\"MJX-11-TEX-N-67\" d=\"M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z\"><\/path><path id=\"MJX-11-TEX-N-2061\" d=\"\"><\/path><path id=\"MJX-11-TEX-N-29\" d=\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"><\/path><path id=\"MJX-11-TEX-N-2C\" d=\"M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z\"><\/path><path id=\"MJX-11-TEX-N-3D\" d=\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"><\/path><path id=\"MJX-11-TEX-N-6D\" d=\"M41 46H55Q94 46 102 60V68Q102 77 102 91T102 122T103 161T103 203Q103 234 103 269T102 328V351Q99 370 88 376T43 385H25V408Q25 431 27 431L37 432Q47 433 65 434T102 436Q119 437 138 438T167 441T178 442H181V402Q181 364 182 364T187 369T199 384T218 402T247 421T285 437Q305 442 336 442Q351 442 364 440T387 434T406 426T421 417T432 406T441 395T448 384T452 374T455 366L457 361L460 365Q463 369 466 373T475 384T488 397T503 410T523 422T546 432T572 439T603 442Q729 442 740 329Q741 322 741 190V104Q741 66 743 59T754 49Q775 46 803 46H819V0H811L788 1Q764 2 737 2T699 3Q596 3 587 0H579V46H595Q656 46 656 62Q657 64 657 200Q656 335 655 343Q649 371 635 385T611 402T585 404Q540 404 506 370Q479 343 472 315T464 232V168V108Q464 78 465 68T468 55T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z\"><\/path><path id=\"MJX-11-TEX-N-61\" d=\"M137 305T115 305T78 320T63 359Q63 394 97 421T218 448Q291 448 336 416T396 340Q401 326 401 309T402 194V124Q402 76 407 58T428 40Q443 40 448 56T453 109V145H493V106Q492 66 490 59Q481 29 455 12T400 -6T353 12T329 54V58L327 55Q325 52 322 49T314 40T302 29T287 17T269 6T247 -2T221 -8T190 -11Q130 -11 82 20T34 107Q34 128 41 147T68 188T116 225T194 253T304 268H318V290Q318 324 312 340Q290 411 215 411Q197 411 181 410T156 406T148 403Q170 388 170 359Q170 334 154 320ZM126 106Q126 75 150 51T209 26Q247 26 276 49T315 109Q317 116 318 175Q318 233 317 233Q309 233 296 232T251 223T193 203T147 166T126 106Z\"><\/path><path id=\"MJX-11-TEX-N-78\" d=\"M201 0Q189 3 102 3Q26 3 17 0H11V46H25Q48 47 67 52T96 61T121 78T139 96T160 122T180 150L226 210L168 288Q159 301 149 315T133 336T122 351T113 363T107 370T100 376T94 379T88 381T80 383Q74 383 44 385H16V431H23Q59 429 126 429Q219 429 229 431H237V385Q201 381 201 369Q201 367 211 353T239 315T268 274L272 270L297 304Q329 345 329 358Q329 364 327 369T322 376T317 380T310 384L307 385H302V431H309Q324 428 408 428Q487 428 493 431H499V385H492Q443 385 411 368Q394 360 377 341T312 257L296 236L358 151Q424 61 429 57T446 50Q464 46 499 46H516V0H510H502Q494 1 482 1T457 2T432 2T414 3Q403 3 377 3T327 1L304 0H295V46H298Q309 46 320 51T331 63Q331 65 291 120L250 175Q249 174 219 133T185 88Q181 83 181 74Q181 63 188 55T206 46Q208 46 208 23V0H201Z\"><\/path><path id=\"MJX-11-TEX-I-1D465\" d=\"M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z\"><\/path><path id=\"MJX-11-TEX-I-1D466\" d=\"M21 287Q21 301 36 335T84 406T158 442Q199 442 224 419T250 355Q248 336 247 334Q247 331 231 288T198 191T182 105Q182 62 196 45T238 27Q261 27 281 38T312 61T339 94Q339 95 344 114T358 173T377 247Q415 397 419 404Q432 431 462 431Q475 431 483 424T494 412T496 403Q496 390 447 193T391 -23Q363 -106 294 -155T156 -205Q111 -205 77 -183T43 -117Q43 -95 50 -80T69 -58T89 -48T106 -45Q150 -45 150 -87Q150 -107 138 -122T115 -142T102 -147L99 -148Q101 -153 118 -160T152 -167H160Q177 -167 186 -165Q219 -156 247 -127T290 -65T313 -9T321 21L315 17Q309 13 296 6T270 -6Q250 -11 231 -11Q185 -11 150 11T104 82Q103 89 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-11-TEX-N-2208\" d=\"M84 250Q84 372 166 450T360 539Q361 539 377 539T419 540T469 540H568Q583 532 583 520Q583 511 570 501L466 500Q355 499 329 494Q280 482 242 458T183 409T147 354T129 306T124 272V270H568Q583 262 583 250T568 230H124V228Q124 207 134 177T167 112T231 48T328 7Q355 1 466 0H570Q583 -10 583 -20Q583 -32 568 -40H471Q464 -40 446 -40T417 -41Q262 -41 172 45Q84 127 84 250Z\"><\/path><path id=\"MJX-11-TEX-I-1D438\" d=\"M492 213Q472 213 472 226Q472 230 477 250T482 285Q482 316 461 323T364 330H312Q311 328 277 192T243 52Q243 48 254 48T334 46Q428 46 458 48T518 61Q567 77 599 117T670 248Q680 270 683 272Q690 274 698 274Q718 274 718 261Q613 7 608 2Q605 0 322 0H133Q31 0 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q146 66 215 342T285 622Q285 629 281 629Q273 632 228 634H197Q191 640 191 642T193 659Q197 676 203 680H757Q764 676 764 669Q764 664 751 557T737 447Q735 440 717 440H705Q698 445 698 453L701 476Q704 500 704 528Q704 558 697 578T678 609T643 625T596 632T532 634H485Q397 633 392 631Q388 629 386 622Q385 619 355 499T324 377Q347 376 372 376H398Q464 376 489 391T534 472Q538 488 540 490T557 493Q562 493 565 493T570 492T572 491T574 487T577 483L544 351Q511 218 508 216Q505 213 492 213Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D442\" xlink:href=\"#MJX-11-TEX-I-1D442\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(763,0)\"><use data-c=\"28\" xlink:href=\"#MJX-11-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1152,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-11-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1918.7,0)\"><use data-c=\"6C\" xlink:href=\"#MJX-11-TEX-N-6C\"><\/use><use data-c=\"6F\" xlink:href=\"#MJX-11-TEX-N-6F\" transform=\"translate(278,0)\"><\/use><use data-c=\"67\" xlink:href=\"#MJX-11-TEX-N-67\" transform=\"translate(778,0)\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3196.7,0)\"><use data-c=\"2061\" xlink:href=\"#MJX-11-TEX-N-2061\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(3363.3,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-11-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3963.3,0)\"><use data-c=\"29\" xlink:href=\"#MJX-11-TEX-N-29\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(4352.3,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-11-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(4797,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-11-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(5674.8,0)\"><use data-c=\"3D\" xlink:href=\"#MJX-11-TEX-N-3D\"><\/use><\/g><g data-mml-node=\"munder\" transform=\"translate(6730.6,0)\"><g data-mml-node=\"mo\"><use data-c=\"6D\" xlink:href=\"#MJX-11-TEX-N-6D\"><\/use><use data-c=\"61\" xlink:href=\"#MJX-11-TEX-N-61\" transform=\"translate(833,0)\"><\/use><use data-c=\"78\" xlink:href=\"#MJX-11-TEX-N-78\" transform=\"translate(1333,0)\"><\/use><\/g><g data-mml-node=\"TeXAtom\" transform=\"translate(1894,-176.7) scale(0.707)\" data-mjx-texclass=\"ORD\"><g data-mml-node=\"mo\"><use data-c=\"28\" xlink:href=\"#MJX-11-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(389,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-11-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(961,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-11-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1239,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-11-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(1729,0)\"><use data-c=\"29\" xlink:href=\"#MJX-11-TEX-N-29\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(2118,0)\"><use data-c=\"2208\" xlink:href=\"#MJX-11-TEX-N-2208\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(2785,0)\"><use data-c=\"1D438\" xlink:href=\"#MJX-11-TEX-I-1D438\"><\/use><\/g><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(11350.7,0)\"><use data-c=\"6D\" xlink:href=\"#MJX-11-TEX-N-6D\"><\/use><use data-c=\"61\" xlink:href=\"#MJX-11-TEX-N-61\" transform=\"translate(833,0)\"><\/use><use data-c=\"78\" xlink:href=\"#MJX-11-TEX-N-78\" transform=\"translate(1333,0)\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(13211.7,0)\"><use data-c=\"28\" xlink:href=\"#MJX-11-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(13600.7,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-11-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(14172.7,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-11-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(14617.4,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-11-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(15107.4,0)\"><use data-c=\"29\" xlink:href=\"#MJX-11-TEX-N-29\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">O(n \\log n),n = \\max_{(x,y) \\in E} \\max(x,y)<\/script>\u200b\u200b\u3002\u8003\u8651\u4f7f\u7528\u96c6\u5408\u5bf9\u79f0\u5dee\u5377\u79ef\u7684\u65b9\u6cd5\u8fdb\u884c\u8ba1\u7b97\u3002\u6211\u4eec\u8003\u8651\u96c6\u5408\u5bf9\u79f0\u5dee\u5377\u79ef\uff0c\u6bcf\u6b21\u53ea\u80fd\u5904\u7406\u4e00\u4e2a<mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"50.16ex\" height=\"2.262ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -750 22170.9 1000\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.566ex;\"><defs><path id=\"MJX-12-TEX-N-5B\" d=\"M118 -250V750H255V710H158V-210H255V-250H118Z\"><\/path><path id=\"MJX-12-TEX-I-1D465\" d=\"M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z\"><\/path><path id=\"MJX-12-TEX-N-D7\" d=\"M630 29Q630 9 609 9Q604 9 587 25T493 118L389 222L284 117Q178 13 175 11Q171 9 168 9Q160 9 154 15T147 29Q147 36 161 51T255 146L359 250L255 354Q174 435 161 449T147 471Q147 480 153 485T168 490Q173 490 175 489Q178 487 284 383L389 278L493 382Q570 459 587 475T609 491Q630 491 630 471Q630 464 620 453T522 355L418 250L522 145Q606 61 618 48T630 29Z\"><\/path><path id=\"MJX-12-TEX-N-32\" d=\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"><\/path><path id=\"MJX-12-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-12-TEX-N-2C\" d=\"M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z\"><\/path><path id=\"MJX-12-TEX-N-2B\" d=\"M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z\"><\/path><path id=\"MJX-12-TEX-N-2212\" d=\"M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z\"><\/path><path id=\"MJX-12-TEX-N-31\" d=\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"><\/path><path id=\"MJX-12-TEX-N-5D\" d=\"M22 710V750H159V-250H22V-210H119V710H22Z\"><\/path><path id=\"MJX-12-TEX-I-1D466\" d=\"M21 287Q21 301 36 335T84 406T158 442Q199 442 224 419T250 355Q248 336 247 334Q247 331 231 288T198 191T182 105Q182 62 196 45T238 27Q261 27 281 38T312 61T339 94Q339 95 344 114T358 173T377 247Q415 397 419 404Q432 431 462 431Q475 431 483 424T494 412T496 403Q496 390 447 193T391 -23Q363 -106 294 -155T156 -205Q111 -205 77 -183T43 -117Q43 -95 50 -80T69 -58T89 -48T106 -45Q150 -45 150 -87Q150 -107 138 -122T115 -142T102 -147L99 -148Q101 -153 118 -160T152 -167H160Q177 -167 186 -165Q219 -156 247 -127T290 -65T313 -9T321 21L315 17Q309 13 296 6T270 -6Q250 -11 231 -11Q185 -11 150 11T104 82Q103 89 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mo\"><use data-c=\"5B\" xlink:href=\"#MJX-12-TEX-N-5B\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(278,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-12-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(1072.2,0)\"><use data-c=\"D7\" xlink:href=\"#MJX-12-TEX-N-D7\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(2072.4,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(3079.7,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-12-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(3524.4,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-12-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(4318.6,0)\"><use data-c=\"D7\" xlink:href=\"#MJX-12-TEX-N-D7\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(5318.8,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(6548.3,0)\"><use data-c=\"2B\" xlink:href=\"#MJX-12-TEX-N-2B\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(7548.5,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(8778,0)\"><use data-c=\"2212\" xlink:href=\"#MJX-12-TEX-N-2212\"><\/use><\/g><g data-mml-node=\"mn\" transform=\"translate(9778.2,0)\"><use data-c=\"31\" xlink:href=\"#MJX-12-TEX-N-31\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(10278.2,0)\"><use data-c=\"5D\" xlink:href=\"#MJX-12-TEX-N-5D\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(10778.5,0)\"><use data-c=\"D7\" xlink:href=\"#MJX-12-TEX-N-D7\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(11778.7,0)\"><use data-c=\"5B\" xlink:href=\"#MJX-12-TEX-N-5B\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(12056.7,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-12-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(12768.9,0)\"><use data-c=\"D7\" xlink:href=\"#MJX-12-TEX-N-D7\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(13769.1,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(14776.4,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-12-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(15221.1,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-12-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(15933.3,0)\"><use data-c=\"D7\" xlink:href=\"#MJX-12-TEX-N-D7\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(16933.5,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(18163,0)\"><use data-c=\"2B\" xlink:href=\"#MJX-12-TEX-N-2B\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(19163.2,0)\"><g data-mml-node=\"mn\"><use data-c=\"32\" xlink:href=\"#MJX-12-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(533,363) scale(0.707)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-12-TEX-I-1D45B\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(20392.7,0)\"><use data-c=\"2212\" xlink:href=\"#MJX-12-TEX-N-2212\"><\/use><\/g><g data-mml-node=\"mn\" transform=\"translate(21392.9,0)\"><use data-c=\"31\" xlink:href=\"#MJX-12-TEX-N-31\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(21892.9,0)\"><use data-c=\"5D\" xlink:href=\"#MJX-12-TEX-N-5D\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">[x\\times2^n,x\\times2^n+2^n-1] \\times [y\\times2^n,y\\times2^n+2^n-1]<\/script>\u200b\u200b\u200b\u200b\u200b \u7684\u5757\u3002\u6211\u4eec\u5c31\u5148\u628a\u6240\u6709\u6700\u5927\u7684\u5168\u5728\u692d\u5706\u5185\u7684\u5757\u5904\u7406\u4e86\uff0c\u518d\u628a\u6b21\u5927\u7684\u5757\u5904\u7406\u4e86\uff0c\u4f9d\u6b21\u7c7b\u63a8\u2026\u2026<\/p>\n<p>\u4f46\u662f\u8fd9\u4e2a\u7b97\u6cd5\u662f\u4e24\u4e2alog\u7684\uff0c\u8fd8\u4e0d\u591f\u5feb\u3002\u8003\u8651\u4f18\u5316\u8fd9\u4e2a\u7b97\u6cd5\uff0c\u65b9\u6cd5\u5c31\u662f\u4ece\u5e95\u5411\u4e0a\u8fdb\u884cFWT\u7684\u540c\u65f6\uff0c\u8fdb\u884c\u5230\u54ea\u4e00\u5c42\u5c31\u628a\u54ea\u4e00\u5c42\u9700\u8981\u8ba1\u7b97\u7684\u5757\u5904\u7406\u4e86\u3002\u5728\u7b97\u51fa\u4e58\u79ef\u4e4b\u540e\u4e0d\u9700\u8981\u6025\u4e8e\u8fdb\u884c\u53cd\u5411\u7684FWT\uff0c\u800c\u662f\u7d2f\u52a0\u5728\u7ed3\u679c\u6570\u7ec4\u4e0a\u3002<\/p>\n<p>\u6b64\u9898\u590d\u6742\u5ea6\u5206\u6790\u4e2d\u6709\u4e00\u70b9\u662f\u8981\u8bc1\u660e\u6240\u6709\u5757\u7684\u8fb9\u957f\u4e4b\u548c\u662f <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"9.847ex\" height=\"2.262ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -750 4352.3 1000\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.566ex;\"><defs><path id=\"MJX-20-TEX-I-1D442\" d=\"M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z\"><\/path><path id=\"MJX-20-TEX-N-28\" d=\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"><\/path><path id=\"MJX-20-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-20-TEX-N-6C\" d=\"M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z\"><\/path><path id=\"MJX-20-TEX-N-6F\" d=\"M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z\"><\/path><path id=\"MJX-20-TEX-N-67\" d=\"M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z\"><\/path><path id=\"MJX-20-TEX-N-2061\" d=\"\"><\/path><path id=\"MJX-20-TEX-N-29\" d=\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D442\" xlink:href=\"#MJX-20-TEX-I-1D442\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(763,0)\"><use data-c=\"28\" xlink:href=\"#MJX-20-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1152,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-20-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1918.7,0)\"><use data-c=\"6C\" xlink:href=\"#MJX-20-TEX-N-6C\"><\/use><use data-c=\"6F\" xlink:href=\"#MJX-20-TEX-N-6F\" transform=\"translate(278,0)\"><\/use><use data-c=\"67\" xlink:href=\"#MJX-20-TEX-N-67\" transform=\"translate(778,0)\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3196.7,0)\"><use data-c=\"2061\" xlink:href=\"#MJX-20-TEX-N-2061\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(3363.3,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-20-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3963.3,0)\"><use data-c=\"29\" xlink:href=\"#MJX-20-TEX-N-29\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">O(n \\log n)<\/script> \u7684\uff0c\u8fd9\u4e00\u4e8b\u5b9e\u53ef\u4ee5\u4ee5\u9650\u5236\u51fd\u6570\u4e3a\u5355\u8c03\u51fd\u6570\u4e3a\u6761\u4ef6\u8bc1\u660e\uff0c\u800c\u692d\u5706\u7684\u8fb9\u754c\u53ef\u4ee5\u62c6\u5206\u6210\u56db\u4e2a\u5355\u8c03\u51fd\u6570\u3002\u8bc1\u660e\u7684\u601d\u8def\u662f\u8bc1\u660e\u6bcf\u4e2ax\u5750\u6807\u7684\u6a2a\u5750\u6807\u5757\u5bf9\u5e94\u7684y\u5750\u6807\u5757\u4e00\u5b9a\u662f\u5e38\u6570\u4e2a\u52a0\u4e0a\u4e00\u4e9b\u4e2a\u5757\uff0c\u800c\u5bf9\u4e8e\u540c\u4e00\u5927\u5c0f\u7684\u5757\uff0c\u201c\u52a0\u4e0a\u7684\u5757\u201d\u7684\u603b\u957f\u4e0d\u80fd\u8d85\u8fc7 <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"1.357ex\" height=\"1.025ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -442 600 453\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.025ex;\"><defs><path id=\"MJX-14-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D45B\" xlink:href=\"#MJX-14-TEX-I-1D45B\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">n<\/script>\u3002\u7531\u4e8e\u957f\u5ea6\u4e3a <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"4.626ex\" height=\"2.036ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -694 2044.7 900\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.466ex;\"><defs><path id=\"MJX-15-TEX-N-6C\" d=\"M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z\"><\/path><path id=\"MJX-15-TEX-N-6F\" d=\"M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z\"><\/path><path id=\"MJX-15-TEX-N-67\" d=\"M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z\"><\/path><path id=\"MJX-15-TEX-N-2061\" d=\"\"><\/path><path id=\"MJX-15-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"6C\" xlink:href=\"#MJX-15-TEX-N-6C\"><\/use><use data-c=\"6F\" xlink:href=\"#MJX-15-TEX-N-6F\" transform=\"translate(278,0)\"><\/use><use data-c=\"67\" xlink:href=\"#MJX-15-TEX-N-67\" transform=\"translate(778,0)\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(1278,0)\"><use data-c=\"2061\" xlink:href=\"#MJX-15-TEX-N-2061\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1444.7,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-15-TEX-I-1D45B\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">\\log n<\/script>\u79cd\uff0c\u56e0\u6b64\u7ed3\u8bba\u6210\u7acb\u3002<\/p>\n<h2 id=\"1007\">1007<\/h2>\n<p>\u9996\u5148\uff0c\u6211\u4eec\u53d1\u73b0\u64cd\u4f5c\u662f\u53ef\u9006\u7684\uff0c\u8fd9\u5c31\u610f\u5473\u7740\u6211\u4eec\u4ece\u59cb\u81f3\u7ec8\u53ea\u9700\u8981\u64cd\u4f5c\u7b2c\u4e00\u4e2a\u56fe\u5373\u53ef\u3002\u800c\u540e\u6211\u4eec\u53d1\u73b0\u9898\u76ee\u4e2d\u7684\u56fe\u5fc5\u987b\u6bcf\u4e2a\u8054\u901a\u5757\u90fd\u6ee1\u8db3\u53ef\u4ee5\u4e24\u4e2a\u56fe\u53ef\u4ee5\u76f8\u7b49\uff0c\u6574\u4e2a\u56fe\u624d\u53ef\u4ee5\u76f8\u7b49\u3002<\/p>\n<p>\u8003\u8651\u4e00\u4e2a\u8054\u901a\u5757\uff0c\u9996\u5148\u8fd9\u4e2a\u8054\u901a\u5757\u5728\u4e24\u4e2a\u56fe\u4e2d\u7684\u6570\u5b57\u7684multiset\u5fc5\u987b\u662f\u4e00\u6837\u7684\u3002\u800c\u540e\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u9898\u76ee\u4e2d\u7684\u4ea4\u6362\u65b9\u5f0f\u53ef\u4ee5\u6362\u4e2a\u65b9\u5f0f\u7406\u89e3\uff1a\u5c06\u4e24\u4e2a\u8282\u70b9\u7684\u6570\u5b57\u548c\u989c\u8272\u90fd\u4ea4\u6362\uff0c\u518d\u90fd\u7ffb\u8f6c\u3002\u8fd9\u6837\u7684\u64cd\u4f5c\u548c\u539f\u5148\u7684\u64cd\u4f5c\u7ed3\u679c\u4f1a\u662f\u4e00\u6837\u7684\u3002<\/p>\n<p>\u8fd9\u6837\u7684\u60c5\u51b5\u4e0b\uff0c\u4e00\u4e2a\u6570\u5b57\u5982\u679c\u88ab\u4ea4\u6362\u4e86\u5947\u6570\u6b21\uff0c\u4ed6\u7684\u989c\u8272\u5c31\u4f1a\u7ffb\u8f6c\uff0c\u5982\u679c\u88ab\u4ea4\u6362\u4e86\u5076\u6570\u6b21\uff0c\u5219\u4e0d\u4f1a\u7ffb\u8f6c\u3002\u800c\u540e\u6211\u4eec\u5206\u60c5\u51b5\u8ba8\u8bba\uff1a<\/p>\n<ol start=\"\">\n<li>\u56fe\u662f\u4e00\u4e2a\u4e8c\u5206\u56fe\u3002\u90a3\u4e48\u6211\u4eec\u628a\u8fd9\u4e2a\u56fe\u9ed1\u767d\u67d3\u8272\uff0c\u6211\u4eec\u53d1\u73b0\u5bf9\u4e8e\u4e00\u4e2a\u6570\u5b57\uff0c\u5982\u679c\u6211\u4eec\u77e5\u9053\u8fd9\u4e2a\u6570\u5b57\u521d\u59cb\u7684\u9ed1\u767d\u67d3\u8272\u7684\u989c\u8272\u548c\u8282\u70b9\u7684\u989c\u8272\uff0c\u6211\u4eec\u628a\u8fd9\u4e2a\u6570\u5b57\u4ea4\u6362\u5230\u4efb\u4f55\u4e00\u4e2a\u4f4d\u7f6e\u540e\uff0c\u5bf9\u5e94\u7684\u8282\u70b9\u7684\u989c\u8272\u5c31\u662f\u5df2\u77e5\u7684\u4e86\u3002\u800c\u4e14\uff0c\u7531\u4e8e\u56fe\u662f\u8054\u901a\u7684\uff0c\u6570\u5b57\u662f\u53ef\u4ee5\u4efb\u610f\u6392\u5217\u5230\u6240\u6709\u8282\u70b9\u4e0a\u7684\u3002\u90a3\u4e48\u8fd9\u65f6\u6761\u4ef6\u5c31\u662f\u5c06\u6570\u5b57\u6309\u7167(\u8282\u70b9\u989c\u8272^\u6570\u5b57\u989c\u8272)\u5206\u6210\u4e24\u4e2a\u53ef\u91cd\u96c6\u5408\uff0c\u9898\u76ee\u4e2d\u4e24\u4e2a\u56fe\u7684\u8fd9\u4e24\u4e2a\u53ef\u91cd\u96c6\u5408\u5fc5\u987b\u662f\u4e00\u6837\u7684\u3002<\/li>\n<li>\u56fe\u4e0d\u662f\u4e00\u4e2a\u4e8c\u5206\u56fe\u3002\u8fd9\u65f6\u5019\u8054\u901a\u5757\u91cc\u4f1a\u6709\u4e00\u4e2a\u5947\u73af\u3002\u6b64\u65f6\u7684\u6761\u4ef6\u662f\u8f93\u5165\u4e24\u4e2a\u56fe\u91cc\u6240\u6709\u6570\u5b57\u7684\u53ef\u91cd\u96c6\u5408\u5fc5\u987b\u76f8\u540c\uff0c\u4e14\u989c\u8272\u4e2a\u6570\u7684\u5947\u5076\u6027\u4e0d\u80fd\u6539\u53d8\u3002\u8fd9\u662f\u7531\u4e8e\u6211\u4eec\u53ef\u4ee5\u628a\u56fe\u770b\u6210\u4e00\u4e2a\u4e8c\u5206\u56fe\u52a0\u4e0a\u4e00\u4e9b\u591a\u4f59\u7684\u8fb9\uff0c\u6211\u4eec\u53ef\u4ee5\u5bf9\u4e8e\u4efb\u4f55\u4e00\u4e2a\u5947\u73af\u6784\u9020\u4e00\u4e2a\u65b9\u6848\u4f7f\u5f97\u6240\u6709\u7684\u6570\u5b57\u4e0d\u52a8\uff0c\u4e14\u53ea\u6709\u4e24\u4e2a\u4f4d\u7f6e\u7684\u989c\u8272\u7ffb\u8f6c\uff0c\u4e0d\u8bba\u90a3\u4e24\u4e2a\u4f4d\u7f6e\u5f00\u59cb\u989c\u8272\u5982\u4f55\u3002\u65b9\u6848\u5c31\u662f\uff1a\u5bf9\u4e8e\u5947\u73af\u4e0a\u7684\u70b9\u987a\u5e8f\u7f16\u53f7\u4e3a1\u5230n\uff0c\u5148\u8fdb\u884cn-1\u6b21\u64cd\u4f5c\u5c061\u4e0a\u7684\u6570\u5b57\u4ea4\u6362\u5230n\u53f7\u8282\u70b9\uff0c\u518d\u8fdb\u884c\u4e00\u6b21\u64cd\u4f5c\u4ea4\u63621\u53f7\u548cn\u53f7\u8282\u70b9\u4e0a\u7684\u6570\u5b57\uff0c\u518d\u7528n-2\u6b21\u64cd\u4f5c\u5c06n\u53f7\u8282\u70b9\u4e0a\u7684\u6570\u5b57\u4ea4\u6362\u5230\u4e8c\u53f7\u8282\u70b9\u3002<\/li>\n\n<\/ol>\n<h2 id=\"1008\">1008<\/h2>\n<p>\u8003\u8651\u8303\u56f4\u4e3ak\u7684\u72d9\u51fb\u624b\uff0c\u53ef\u4ee5\u653b\u51fb\u7684\u8303\u56f4\u662f\u4e00\u4e2a\u6b63\u65b9\u4f53\u3002\u90a3\u6211\u4eec\u4e0d\u59a8\u91cd\u65b0\u9648\u8ff0\u4e00\u4e0b\u9898\u9762\uff0c\u79f0\u72d9\u51fb\u624b\u4ece <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"7.227ex\" height=\"2.262ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -750 3194.3 1000\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.566ex;\"><defs><path id=\"MJX-16-TEX-N-28\" d=\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"><\/path><path id=\"MJX-16-TEX-I-1D465\" d=\"M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z\"><\/path><path id=\"MJX-16-TEX-N-2C\" d=\"M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z\"><\/path><path id=\"MJX-16-TEX-I-1D466\" d=\"M21 287Q21 301 36 335T84 406T158 442Q199 442 224 419T250 355Q248 336 247 334Q247 331 231 288T198 191T182 105Q182 62 196 45T238 27Q261 27 281 38T312 61T339 94Q339 95 344 114T358 173T377 247Q415 397 419 404Q432 431 462 431Q475 431 483 424T494 412T496 403Q496 390 447 193T391 -23Q363 -106 294 -155T156 -205Q111 -205 77 -183T43 -117Q43 -95 50 -80T69 -58T89 -48T106 -45Q150 -45 150 -87Q150 -107 138 -122T115 -142T102 -147L99 -148Q101 -153 118 -160T152 -167H160Q177 -167 186 -165Q219 -156 247 -127T290 -65T313 -9T321 21L315 17Q309 13 296 6T270 -6Q250 -11 231 -11Q185 -11 150 11T104 82Q103 89 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-16-TEX-I-1D467\" d=\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"><\/path><path id=\"MJX-16-TEX-N-29\" d=\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mo\"><use data-c=\"28\" xlink:href=\"#MJX-16-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(389,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-16-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(961,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-16-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1405.7,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-16-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(1895.7,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-16-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(2340.3,0)\"><use data-c=\"1D467\" xlink:href=\"#MJX-16-TEX-I-1D467\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(2805.3,0)\"><use data-c=\"29\" xlink:href=\"#MJX-16-TEX-N-29\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">(x,y,z)<\/script>\u200b \u53ef\u4ee5\u653b\u51fb\u7684\u8303\u56f4\u662f\u6240\u6709\u6ee1\u8db3 <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"47.589ex\" height=\"2.181ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -759 21034.4 964\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.464ex;\"><defs><path id=\"MJX-17-TEX-I-1D465\" d=\"M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z\"><\/path><path id=\"MJX-17-TEX-N-2264\" d=\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"><\/path><path id=\"MJX-17-TEX-V-2032\" d=\"M79 43Q73 43 52 49T30 61Q30 68 85 293T146 528Q161 560 198 560Q218 560 240 545T262 501Q262 496 260 486Q259 479 173 263T84 45T79 43Z\"><\/path><path id=\"MJX-17-TEX-N-2B\" d=\"M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z\"><\/path><path id=\"MJX-17-TEX-N-32\" d=\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"><\/path><path id=\"MJX-17-TEX-I-1D458\" d=\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"><\/path><path id=\"MJX-17-TEX-N-2C\" d=\"M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z\"><\/path><path id=\"MJX-17-TEX-I-1D466\" d=\"M21 287Q21 301 36 335T84 406T158 442Q199 442 224 419T250 355Q248 336 247 334Q247 331 231 288T198 191T182 105Q182 62 196 45T238 27Q261 27 281 38T312 61T339 94Q339 95 344 114T358 173T377 247Q415 397 419 404Q432 431 462 431Q475 431 483 424T494 412T496 403Q496 390 447 193T391 -23Q363 -106 294 -155T156 -205Q111 -205 77 -183T43 -117Q43 -95 50 -80T69 -58T89 -48T106 -45Q150 -45 150 -87Q150 -107 138 -122T115 -142T102 -147L99 -148Q101 -153 118 -160T152 -167H160Q177 -167 186 -165Q219 -156 247 -127T290 -65T313 -9T321 21L315 17Q309 13 296 6T270 -6Q250 -11 231 -11Q185 -11 150 11T104 82Q103 89 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-17-TEX-I-1D467\" d=\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D465\" xlink:href=\"#MJX-17-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(849.8,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(1905.6,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D465\" xlink:href=\"#MJX-17-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(605,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-17-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(3032.8,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(4088.6,0)\"><use data-c=\"1D465\" xlink:href=\"#MJX-17-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(4882.8,0)\"><use data-c=\"2B\" xlink:href=\"#MJX-17-TEX-N-2B\"><\/use><\/g><g data-mml-node=\"mn\" transform=\"translate(5883,0)\"><use data-c=\"32\" xlink:href=\"#MJX-17-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(6383,0)\"><use data-c=\"1D458\" xlink:href=\"#MJX-17-TEX-I-1D458\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(6904,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-17-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(7348.7,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-17-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(8116.5,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(9172.2,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D466\" xlink:href=\"#MJX-17-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(523,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-17-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(10217.5,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(11273.2,0)\"><use data-c=\"1D466\" xlink:href=\"#MJX-17-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(11985.5,0)\"><use data-c=\"2B\" xlink:href=\"#MJX-17-TEX-N-2B\"><\/use><\/g><g data-mml-node=\"mn\" transform=\"translate(12985.7,0)\"><use data-c=\"32\" xlink:href=\"#MJX-17-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(13485.7,0)\"><use data-c=\"1D458\" xlink:href=\"#MJX-17-TEX-I-1D458\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(14006.7,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-17-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(14451.4,0)\"><use data-c=\"1D467\" xlink:href=\"#MJX-17-TEX-I-1D467\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(15194.1,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(16249.9,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D467\" xlink:href=\"#MJX-17-TEX-I-1D467\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(498,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-17-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(17270.1,0)\"><use data-c=\"2264\" xlink:href=\"#MJX-17-TEX-N-2264\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(18325.9,0)\"><use data-c=\"1D467\" xlink:href=\"#MJX-17-TEX-I-1D467\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(19013.1,0)\"><use data-c=\"2B\" xlink:href=\"#MJX-17-TEX-N-2B\"><\/use><\/g><g data-mml-node=\"mn\" transform=\"translate(20013.4,0)\"><use data-c=\"32\" xlink:href=\"#MJX-17-TEX-N-32\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(20513.4,0)\"><use data-c=\"1D458\" xlink:href=\"#MJX-17-TEX-I-1D458\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">x \\le x' \\le x+2k, y \\le y' \\le y+2k,z \\le z' \\le z+2k<\/script>\u200b \u7684 <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"9.11ex\" height=\"2.283ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -759 4026.7 1009\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.566ex;\"><defs><path id=\"MJX-18-TEX-N-28\" d=\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"><\/path><path id=\"MJX-18-TEX-I-1D465\" d=\"M52 289Q59 331 106 386T222 442Q257 442 286 424T329 379Q371 442 430 442Q467 442 494 420T522 361Q522 332 508 314T481 292T458 288Q439 288 427 299T415 328Q415 374 465 391Q454 404 425 404Q412 404 406 402Q368 386 350 336Q290 115 290 78Q290 50 306 38T341 26Q378 26 414 59T463 140Q466 150 469 151T485 153H489Q504 153 504 145Q504 144 502 134Q486 77 440 33T333 -11Q263 -11 227 52Q186 -10 133 -10H127Q78 -10 57 16T35 71Q35 103 54 123T99 143Q142 143 142 101Q142 81 130 66T107 46T94 41L91 40Q91 39 97 36T113 29T132 26Q168 26 194 71Q203 87 217 139T245 247T261 313Q266 340 266 352Q266 380 251 392T217 404Q177 404 142 372T93 290Q91 281 88 280T72 278H58Q52 284 52 289Z\"><\/path><path id=\"MJX-18-TEX-V-2032\" d=\"M79 43Q73 43 52 49T30 61Q30 68 85 293T146 528Q161 560 198 560Q218 560 240 545T262 501Q262 496 260 486Q259 479 173 263T84 45T79 43Z\"><\/path><path id=\"MJX-18-TEX-N-2C\" d=\"M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z\"><\/path><path id=\"MJX-18-TEX-I-1D466\" d=\"M21 287Q21 301 36 335T84 406T158 442Q199 442 224 419T250 355Q248 336 247 334Q247 331 231 288T198 191T182 105Q182 62 196 45T238 27Q261 27 281 38T312 61T339 94Q339 95 344 114T358 173T377 247Q415 397 419 404Q432 431 462 431Q475 431 483 424T494 412T496 403Q496 390 447 193T391 -23Q363 -106 294 -155T156 -205Q111 -205 77 -183T43 -117Q43 -95 50 -80T69 -58T89 -48T106 -45Q150 -45 150 -87Q150 -107 138 -122T115 -142T102 -147L99 -148Q101 -153 118 -160T152 -167H160Q177 -167 186 -165Q219 -156 247 -127T290 -65T313 -9T321 21L315 17Q309 13 296 6T270 -6Q250 -11 231 -11Q185 -11 150 11T104 82Q103 89 103 113Q103 170 138 262T173 379Q173 380 173 381Q173 390 173 393T169 400T158 404H154Q131 404 112 385T82 344T65 302T57 280Q55 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-18-TEX-I-1D467\" d=\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"><\/path><path id=\"MJX-18-TEX-N-29\" d=\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mo\"><use data-c=\"28\" xlink:href=\"#MJX-18-TEX-N-28\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(389,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D465\" xlink:href=\"#MJX-18-TEX-I-1D465\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(605,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-18-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(1238.5,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-18-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(1683.1,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D466\" xlink:href=\"#MJX-18-TEX-I-1D466\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(523,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-18-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(2450.6,0)\"><use data-c=\"2C\" xlink:href=\"#MJX-18-TEX-N-2C\"><\/use><\/g><g data-mml-node=\"msup\" transform=\"translate(2895.2,0)\"><g data-mml-node=\"mi\"><use data-c=\"1D467\" xlink:href=\"#MJX-18-TEX-I-1D467\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(498,363) scale(0.707)\"><use data-c=\"2032\" xlink:href=\"#MJX-18-TEX-V-2032\"><\/use><\/g><\/g><g data-mml-node=\"mo\" transform=\"translate(3637.7,0)\"><use data-c=\"29\" xlink:href=\"#MJX-18-TEX-N-29\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">(x',y',z')<\/script>\u200b\u3002\u90a3\u4e48\u6211\u4eec\u5c31\u4f1a\u53d1\u73b0\uff1a\u5982\u679c\u6211\u4eec\u7684\u72d9\u51fb\u624b\u7684\u67d0\u4e00\u7ef4\u5ea6\u7684\u5750\u6807\u5c0f\u4e8e\u5269\u4f59\u70b9\u7684\u90a3\u4e00\u7ef4\u5ea6\u7684\u6700\u5c0f\u5750\u6807\uff0c\u6211\u4eec\u5c31\u5e94\u8be5\u628a\u72d9\u51fb\u624b\u79fb\u52a8\u7684\u90a3\u4e00\u7ef4\u5ea6\u7684\u6700\u5c0f\u5750\u6807\uff0c\u56e0\u4e3a\u8fd9\u6837\u53ea\u4f1a\u8ba9\u6211\u4eec\u80fd\u72d9\u51fb\u7684\u76ee\u6807\u589e\u591a\u3002\u5728\u6211\u4eec\u4e09\u4e2a\u7ef4\u5ea6\u90fd\u662f\u90a3\u4e00\u7ef4\u5ea6\u7684\u6700\u5c0f\u5750\u6807\u65f6\uff0c\u72d9\u51fb\u624b\u5c31\u5fc5\u987b\u5c06\u4e09\u4e2a\u7ef4\u5ea6\u4e2d\u67d0\u4e00\u7ef4\u5ea6\u6700\u5c0f\u5750\u6807\u7684\u6240\u6709\u654c\u519b\u90fd\u6d88\u706d\uff0c\u624d\u80fd\u7ee7\u7eed\u79fb\u52a8\u3002\u8fd9\u65f6\u6211\u4eec\u53ef\u4ee5\u8d2a\u5fc3\u7684\u9009\u53d6\u6240\u9700 <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"1.179ex\" height=\"1.595ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -694 521 705\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.025ex;\"><defs><path id=\"MJX-19-TEX-I-1D458\" d=\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D458\" xlink:href=\"#MJX-19-TEX-I-1D458\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">k<\/script> \u6700\u5c0f\u7684\u654c\u519b\u6d88\u706d\u3002\u590d\u6742\u5ea6 <mjx-container class=\"MathJax\" jax=\"SVG\" style=\"position: relative;\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"9.847ex\" height=\"2.262ex\" role=\"img\" focusable=\"false\" viewBox=\"0 -750 4352.3 1000\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" aria-hidden=\"true\" style=\"vertical-align: -0.566ex;\"><defs><path id=\"MJX-20-TEX-I-1D442\" d=\"M740 435Q740 320 676 213T511 42T304 -22Q207 -22 138 35T51 201Q50 209 50 244Q50 346 98 438T227 601Q351 704 476 704Q514 704 524 703Q621 689 680 617T740 435ZM637 476Q637 565 591 615T476 665Q396 665 322 605Q242 542 200 428T157 216Q157 126 200 73T314 19Q404 19 485 98T608 313Q637 408 637 476Z\"><\/path><path id=\"MJX-20-TEX-N-28\" d=\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"><\/path><path id=\"MJX-20-TEX-I-1D45B\" d=\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"><\/path><path id=\"MJX-20-TEX-N-6C\" d=\"M42 46H56Q95 46 103 60V68Q103 77 103 91T103 124T104 167T104 217T104 272T104 329Q104 366 104 407T104 482T104 542T103 586T103 603Q100 622 89 628T44 637H26V660Q26 683 28 683L38 684Q48 685 67 686T104 688Q121 689 141 690T171 693T182 694H185V379Q185 62 186 60Q190 52 198 49Q219 46 247 46H263V0H255L232 1Q209 2 183 2T145 3T107 3T57 1L34 0H26V46H42Z\"><\/path><path id=\"MJX-20-TEX-N-6F\" d=\"M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z\"><\/path><path id=\"MJX-20-TEX-N-67\" d=\"M329 409Q373 453 429 453Q459 453 472 434T485 396Q485 382 476 371T449 360Q416 360 412 390Q410 404 415 411Q415 412 416 414V415Q388 412 363 393Q355 388 355 386Q355 385 359 381T368 369T379 351T388 325T392 292Q392 230 343 187T222 143Q172 143 123 171Q112 153 112 133Q112 98 138 81Q147 75 155 75T227 73Q311 72 335 67Q396 58 431 26Q470 -13 470 -72Q470 -139 392 -175Q332 -206 250 -206Q167 -206 107 -175Q29 -140 29 -75Q29 -39 50 -15T92 18L103 24Q67 55 67 108Q67 155 96 193Q52 237 52 292Q52 355 102 398T223 442Q274 442 318 416L329 409ZM299 343Q294 371 273 387T221 404Q192 404 171 388T145 343Q142 326 142 292Q142 248 149 227T179 192Q196 182 222 182Q244 182 260 189T283 207T294 227T299 242Q302 258 302 292T299 343ZM403 -75Q403 -50 389 -34T348 -11T299 -2T245 0H218Q151 0 138 -6Q118 -15 107 -34T95 -74Q95 -84 101 -97T122 -127T170 -155T250 -167Q319 -167 361 -139T403 -75Z\"><\/path><path id=\"MJX-20-TEX-N-2061\" d=\"\"><\/path><path id=\"MJX-20-TEX-N-29\" d=\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"><\/path><\/defs><g stroke=\"currentColor\" fill=\"currentColor\" stroke-width=\"0\" transform=\"scale(1,-1)\"><g data-mml-node=\"math\"><g data-mml-node=\"mi\"><use data-c=\"1D442\" xlink:href=\"#MJX-20-TEX-I-1D442\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(763,0)\"><use data-c=\"28\" xlink:href=\"#MJX-20-TEX-N-28\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1152,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-20-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(1918.7,0)\"><use data-c=\"6C\" xlink:href=\"#MJX-20-TEX-N-6C\"><\/use><use data-c=\"6F\" xlink:href=\"#MJX-20-TEX-N-6F\" transform=\"translate(278,0)\"><\/use><use data-c=\"67\" xlink:href=\"#MJX-20-TEX-N-67\" transform=\"translate(778,0)\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3196.7,0)\"><use data-c=\"2061\" xlink:href=\"#MJX-20-TEX-N-2061\"><\/use><\/g><g data-mml-node=\"mi\" transform=\"translate(3363.3,0)\"><use data-c=\"1D45B\" xlink:href=\"#MJX-20-TEX-I-1D45B\"><\/use><\/g><g data-mml-node=\"mo\" transform=\"translate(3963.3,0)\"><use data-c=\"29\" xlink:href=\"#MJX-20-TEX-N-29\"><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><script type=\"math\/tex\">O(n \\log n)<\/script>\u3002<\/p>\n\n<\/body><\/html>\n\n\n\n<h2 class=\"wp-block-heading\">1006 STD<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>#include <bits\/stdc++.h>\nusing namespace std;\nusing ll = long long; \n#define tcT template<class T\n#define tcTU tcT, class U\n#define FOR(i,a,b) for (int i = (a); i < (b); ++i)\n#define F0R(i,a) FOR(i,0,a)\n#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)\n#define R0F(i,a) ROF(i,0,a)\n#define each(a,x) for (auto& a: x)\nconst int mod = 1000000007;\nconstexpr int pct(int x) { return __builtin_popcount(x); } \/\/ # of bits set\nll fdiv(ll a, ll b) { return a\/b-((a^b)<0&&a%b); } \/\/ divide a by b rounded down\ntcTU> T lstTrue(T lo, T hi, U f) { lo --; assert(lo <= hi); while (lo < hi) { T mid = lo+(hi-lo+1)\/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }\n\nconst int MX = (2<<22)+10;\nll a,b,c,d,e,f;\nint N,miv[MX],xv2[MX],yv2[MX],resv[MX],li[MX*2],ri[MX*2];\n\ninline int mul(int x,int y){return 1ll*x*y%mod;}\ninline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}\ninline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}\ninline int sq(int x){return 1ll*x*x%mod;}\nint mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b\/2))) : sq(mpow(a,b\/2)));}\n\nvoid solve(){\n cin>>a>>b>>c>>d>>e>>f;\n ll xbnd = lstTrue(0,4000000,[&](ll x){return (4*c*a-e*e)*x*x<=4*c*f;});\n ll ybnd = lstTrue(0,4000000,[&](ll x){return (4*c*a-e*e)*x*x<=4*a*f;});\n int cn = max(b+xbnd,d+ybnd)+10;\n N = 1;while(N<cn)N*=2;\n F0R(i,N){\n yv2[i] = miv[i];\n xv2[i] = 1ll*yv2[i]*yv2[i]%mod;\n resv[i] = 0;\n }\n F0R(ii,N){\n if(ii<b-xbnd || ii>b+xbnd){\n li[ii+N] = 1;ri[ii+N] = 0;\n continue;\n }\n ll i = ii-b,cv = e*e*i*i-4*c*(a*i*i-f),ce = sqrt(cv);\n while(ce*ce>cv)ce-=1; while((ce+1)*(ce+1)<=cv)ce+=1;\n ri[ii+N] = fdiv(-e*i+ce,c*2)+d;\n li[ii+N] = fdiv(-e*i-ce+c*2-1,c*2)+d;\n }\n int msk = N-2;\n R0F(i,N){\n li[i] = N-((N-max(li[i*2],li[i*2+1]))&msk);\n ri[i] = ((min(ri[i*2],ri[i*2+1])+1)&msk)-1;\n if(pct(i) == 1)msk-=msk&-msk;\n }\n auto conv = [&](int* xxa,int i){\n for(int s =0;s<N;s+=i*2){\n int* f1 = xxa+s,*f2 =xxa+s+i;\n for(int j=0;j<i;j++){ int c1 = f1[j],c2 = f2[j]; f1[j]=add(c1,c2); f2[j]=sub(c1,c2); }\n }\n };\n for(int i = 1;i<N;i*=2){\n int s;\n function<void(int,int)> calc= [&](int l,int r){\n for(int j=l;j<r;j+=i){\n int *a = xv2+s,*b = yv2+j,*res = resv+(s^j);\n for(int k=0;k<i;k++) res[k]=(1ll*a[k]*b[k]+res[k])%mod;\n }\n };\n for(s =0;s<N;s+=i){\n int id = (N+s)\/i;\n if(li[id]>ri[id])continue;\n if(li[id\/2]>ri[id\/2]){\n calc(li[id],ri[id]+1);\n }else{\n calc(li[id],li[id\/2]);\n calc(ri[id\/2]+1,ri[id]+1);\n }\n }\n conv(xv2,i);conv(yv2,i);conv(resv,i);\n }\n for(int i = 1;i<N;i*=2) conv(resv,i);\n int ans = 0;\n F0R(i,N) ans=add(ans,(1ll*((1ll*resv[i]*i)%mod)*((1ll*i*i)%mod))%mod);\n ans=mul(ans,mpow(N,mod-2));\n cout<<ans<<\"\\n\";\n}\n\nint main() {\n int T;cin>>T;\n miv[0] = miv[1]= 1;\n FOR(i,2,MX) miv[i] = mod-(long long)mod\/i*miv[mod%i]%mod;\n while(T--){\n solve();\n }\n return 0;\n}<\/code><\/pre>\n\n\n\n<p><\/p>\n ","protected":false},"excerpt":{"rendered":"<p>\u9898\u662f\u6211\u51fa\u7684\uff0cstd\u662f\u6211\u5199\u7684\u30021006\u662f\u539f\u521b\u5957\u8def\u30021008\u662f\u539f\u521b\u8d2a\u5fc3\u30021007\u662f\u4eceCF\u4e0a\u7684\u9898\u52a0\u5f3a\u4e86\u4e00\u4e0b\u5b50\u51fa\u7684\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/734"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=734"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/734\/revisions"}],"predecessor-version":[{"id":735,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/734\/revisions\/735"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=734"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=734"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=734"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}