{"id":301059,"date":"2020-03-31T21:00:25","date_gmt":"2020-03-31T21:00:25","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=301059"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=301059","title":{"rendered":"\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0430 \u044d\u043a\u0437\u0430\u043c\u0435\u043d\u0435 \u0432 \u0428\u0410\u0414"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/494998\/\">\n<p>\u041f\u0440\u0438\u0432\u0435\u0442! \u041c\u0435\u043d\u044f \u0437\u043e\u0432\u0443\u0442 \u0410\u043b\u0435\u043a\u0441\u0430\u043d\u0434\u0440 \u041a\u0443\u0440\u0438\u043b\u043a\u0438\u043d, \u0438 \u044f \u0432\u0435\u0434\u0443 \u043a\u0443\u0440\u0441 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0432 \u00ab\u0428\u0410\u0414 Helper\u00bb. \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0437\u0431\u0435\u0440\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u0434\u0430\u0447 \u0438\u0437 \u0432\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u044d\u043a\u0437\u0430\u043c\u0435\u043d\u043e\u0432 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u043b\u0435\u0442, \u0447\u0442\u043e\u0431\u044b \u0432\u044b \u0441\u043c\u043e\u0433\u043b\u0438 \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0432\u0430\u0441 \u0436\u0434\u0435\u0442, \u0438 \u043f\u043e\u043d\u044f\u0442\u044c, \u0447\u0435\u043c\u0443 \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u0432\u0430\u0441 \u043d\u0430\u0443\u0447\u0438\u0442\u044c \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u043a\u0443\u0440\u0441\u0435. \u041d\u0430\u0434\u0435\u044e\u0441\u044c, \u0447\u0442\u043e \u0432\u044b \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442\u0435 \u043c\u043e\u044e \u043b\u044e\u0431\u043e\u0432\u044c \u043a \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u043c \u0437\u0430\u0434\u0430\u0447\u0430\u043c \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0435 \u0438\u0441\u043a\u0440\u0435\u043d\u043d\u0435\u0435 \u0443\u0434\u043e\u0432\u043e\u043b\u044c\u0441\u0442\u0432\u0438\u0435 \u043e\u0442 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0441\u0442\u0430! \u0418\u0442\u0430\u043a, \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c&#8230;<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/na\/im\/kg\/naimkgdsyccbubz6mky9z7q-kxw.png\"><a name=\"habracut\"><\/a>  <\/p>\n<p><strong>28.05.2016, \u21164<\/strong><\/p>\n<p>  <\/p>\n<p>\u0414\u0430\u043d\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f74\/083\/f5f\/f74083f5f61704a9b0b672bedf591e16.svg\" alt=\"$[a_i; b_i]$\" data-tex=\"inline\"><\/math>. \u041d\u0430\u0437\u043e\u0432\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043e\u0442\u0440\u0435\u0437\u043a\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f74\/083\/f5f\/f74083f5f61704a9b0b672bedf591e16.svg\" alt=\"$[a_i; b_i]$\" data-tex=\"inline\"><\/math> \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0435\u0433\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442. \u041f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0438\u0439, \u0435\u0441\u0442\u044c \u043b\u0438 \u0432 \u043d\u0430\u0431\u043e\u0440\u0435 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0441\u0442\u0438, \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0449\u0438\u043c 1000. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cba\/e5c\/054\/cbae5c05497ff7402dbf72df48a09595.svg\" alt=\"$O(n \\log n)$\" data-tex=\"inline\"><\/math>, \u043f\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0412\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432 \u0441\u0440\u0435\u0434\u0435 \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u043d\u0438\u043a\u043e\u0432 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f &quot;\u0441\u043a\u0430\u043d\u043b\u0430\u0439\u043d&quot;. \u0415\u0433\u043e \u0441\u0443\u0442\u044c \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0441\u0432\u043e\u0434\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u043d\u0430\u0431\u043e\u0440\u0443 \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0447\u0442\u043e-\u0442\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0434\u0435\u043b\u0430\u044f, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0440\u0435\u0448\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0443. \u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0441\u043e\u0431\u044b\u0442\u0438\u044f &quot;\u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043e\u0442\u043a\u0440\u044b\u043b\u0441\u044f&quot;, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/122\/b00\/691\/122b006916bcacd39b883735fa907bfa.svg\" alt=\"$a_i$\" data-tex=\"inline\"><\/math>, \u0438 &quot;\u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0437\u0430\u043a\u0440\u044b\u043b\u0441\u044f&quot;, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0432 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/efc\/54b\/d54\/efc54bd547b1a0f308a2ae4281e7d6ed.svg\" alt=\"$b_i$\" data-tex=\"inline\"><\/math>. \u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u043f\u043e \u0438\u0445 \u043c\u043e\u043c\u0435\u043d\u0442\u0443 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438 \u043d\u0430\u0447\u043d\u0435\u043c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0438\u0445 \u0432 \u0442\u0430\u043a\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u041a\u043e\u0433\u0434\u0430 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043d\u0443\u0436\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u043d\u0430 1. \u041a\u043e\u0433\u0434\u0430 \u043e\u0442\u043a\u0440\u044b\u043b\u0441\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a, \u0430 \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u0443\u0436\u0435 \u0431\u044b\u043b \u0431\u043e\u043b\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u0435\u043d 1000, \u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0431\u044b, \u043c\u044b \u0443\u0436\u0435 \u0440\u0435\u0448\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u2014 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0432 1000 \u0443\u0436\u0435 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u0440\u0430\u043d\u0435\u0435. \u041d\u043e \u0432\u0441\u0435 \u043d\u0435 \u0442\u0430\u043a \u043f\u0440\u043e\u0441\u0442\u043e \u2014 \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0438\u0437 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u0440\u0430\u043d\u0435\u0435 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u043c\u043e\u0433\u043b\u0438 \u0437\u0430\u043a\u0440\u044b\u0442\u044c\u0441\u044f \u0440\u0430\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0437\u0430\u043a\u0440\u043e\u0435\u0442\u0441\u044f \u043d\u0430\u0448 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c \u043a\u0430\u043a \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u043d\u0430 \u043e\u0442\u0432\u0435\u0442. \u0427\u0442\u043e\u0431\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u044d\u0442\u0443 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e (std::multiset \u0432 C++), \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u043a\u043e\u043d\u0446\u043e\u0432 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432. \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u043a\u043e\u043d\u0446\u044b \u0432 \u043d\u0435\u043c \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u2014 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043b\u0438\u0448\u044c 1000 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445. \u0422\u0435\u043f\u0435\u0440\u044c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0438 \u043f\u0440\u0430\u0432\u0434\u0430 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043d\u0430\u043c, \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0432 \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 *set.begin(), \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u0441\u0440\u0435\u0434\u0438 1000 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445) \u043a\u043e\u043d\u0435\u0446 \u043d\u0435 \u043b\u0435\u0432\u0435\u0435 \u043a\u043e\u043d\u0446\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043f\u0440\u0430\u0432\u0434\u0430, \u0442\u043e \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0435\u043d\u0430! \u0415\u0441\u043b\u0438 \u043d\u0435\u0442, \u0442\u043e \u0443\u0432\u044b, \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0442\u044c \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0440\u0430\u043d\u044c\u0448\u0435. \u0415\u0441\u043b\u0438 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0437\u0430\u043a\u0440\u044b\u043b\u0441\u044f, \u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0438\u0437 \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0435\u0433\u043e \u043a\u043e\u043d\u0435\u0446. \u0415\u0441\u043b\u0438 \u0432\u0441\u0435 \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u044b, \u0430 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043d\u0435 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0435\u043d, \u0442\u043e \u0435\u0433\u043e \u0438 \u043d\u0435\u0442! <\/p>\n<p>  <\/p>\n<p>\u0423 \u043f\u044b\u0442\u043b\u0438\u0432\u043e\u0433\u043e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u043f\u0440\u0438 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u0438 \u043c\u043e\u0433 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0432\u043e\u043f\u0440\u043e\u0441: \u043f\u043e\u0447\u0435\u043c\u0443 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043b\u0438\u0448\u044c 1000 \u043a\u043e\u043d\u0446\u043e\u0432? \u0412\u0434\u0440\u0443\u0433 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u043e\u0435, \u0447\u0442\u043e \u0443\u0434\u0430\u043b\u0438\u0442\u0441\u044f \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0438\u0437 \u044d\u0442\u0438\u0445 1000 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u043d\u0446\u043e\u0432, \u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u043e \u0431\u044b\u043b\u043e \u0431\u043e\u043b\u044c\u0448\u0435 1000 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432, \u0438 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u043e\u0442\u043a\u0443\u0434\u0430-\u0442\u043e \u0432\u0437\u044f\u0442\u044c \u043a\u043e\u043d\u0435\u0446, \u0447\u0442\u043e\u0431\u044b \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u043d\u044b\u0439? \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u0431\u044b\u0442\u044c \u043d\u0435 \u043c\u043e\u0436\u0435\u0442, \u0432\u0435\u0434\u044c \u0435\u0441\u043b\u0438 \u043c\u044b \u0443\u0434\u0430\u043b\u0438\u043b\u0438 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0438\u0437 1000 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u043d\u0446\u043e\u0432, \u0437\u043d\u0430\u0447\u0438\u0442, \u043c\u044b \u0437\u0430\u043a\u0440\u044b\u043b\u0438 \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u0441 \u0442\u0430\u043a\u0438\u043c \u043a\u043e\u043d\u0446\u043e\u043c, \u0430 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0437\u0430\u043a\u0440\u044b\u043b\u0438 \u0438 \u0432\u0441\u0435 \u043e\u0442\u0440\u0435\u0437\u043a\u0438 \u0441 \u043a\u043e\u043d\u0446\u0430\u043c\u0438 \u043b\u0435\u0432\u0435\u0435 \u043d\u0430\u0448\u0435\u0433\u043e, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u0437\u0430\u043c\u0435\u043d\u044f\u0442\u044c \u0432 \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u043d\u0435\u0446 \u043d\u0435\u0447\u0435\u043c.<\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0442 \u0438 \u0432\u0441\u0435, \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0435\u043d\u0430. \u041c\u044b \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cba\/e5c\/054\/cbae5c05497ff7402dbf72df48a09595.svg\" alt=\"$O(n \\log n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043d\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u0441\u043e\u0431\u044b\u0442\u0438\u0439, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a36\/15d\/0c7\/a3615d0c7d9fddb62835444b32d3e2e9.svg\" alt=\"$O(n \\log 1000) = O(n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441 \u043c\u0443\u043b\u044c\u0442\u0438\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u043a\u043e\u043d\u0446\u043e\u0432 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u0438 O(n) \u043d\u0430 \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u043e\u0435. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cba\/e5c\/054\/cbae5c05497ff7402dbf72df48a09595.svg\" alt=\"$O(n \\log n)$\" data-tex=\"inline\"><\/math>. \u041f\u0430\u043c\u044f\u0442\u0438 \u043c\u044b \u0443\u0436 \u0442\u043e\u0447\u043d\u043e \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043b\u0438 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p><strong>25.05.2019, \u21164<\/strong><\/p>\n<p>  <\/p>\n<p>\u0414\u0430\u043d \u043c\u0430\u0441\u0441\u0438\u0432 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math>. \u041f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math> \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043f\u0440\u0430\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0435\u0433\u043e \u0445\u043e\u0442\u044f \u0431\u044b \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430. \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435\u0442, \u0442\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ffb\/cad\/1b1\/ffbcad1b1eea934028c9c71e5a45ec2f.svg\" alt=\"$None$\" data-tex=\"inline\"><\/math>. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cba\/e5c\/054\/cbae5c05497ff7402dbf72df48a09595.svg\" alt=\"$O(n \\log n)$\" data-tex=\"inline\"><\/math>, \u043f\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0411\u0443\u0434\u0435\u043c \u0438\u0434\u0442\u0438 \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u0441\u0442\u0435\u043a \u043f\u0430\u0440 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cfa\/e76\/527\/cfae7652717e5ea0d21de3f2b7555312.svg\" alt=\"$(\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043d\u0434\u0435\u043a\u0441)$\" data-tex=\"inline\"><\/math> \u043f\u0440\u043e\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041d\u0430\u0447\u043d\u0435\u043c \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 (\u0434\u043b\u044f \u043d\u0435\u0433\u043e \u043e\u0442\u0432\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ffb\/cad\/1b1\/ffbcad1b1eea934028c9c71e5a45ec2f.svg\" alt=\"$None$\" data-tex=\"inline\"><\/math>), \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u0432 \u0441\u0442\u0435\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3ce\/8c2\/afd\/3ce8c2afdf02ec16e11dc1fb2a7bd52d.svg\" alt=\"$(A[n - 1], n - 1)$\" data-tex=\"inline\"><\/math>, \u043f\u043e\u0439\u0434\u0435\u043c \u043b\u0435\u0432\u0435\u0435. \u041f\u0443\u0441\u0442\u044c \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u043a\u0430\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430, \u043f\u0440\u043e\u0439\u0434\u0435\u043d\u043d\u044b\u0435 \u0440\u0430\u043d\u0435\u0435, \u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0434\u043b\u044f \u043d\u0430\u0441 \u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0430 \u0432 \u043f\u043b\u0430\u043d\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043f\u0440\u0430\u0432\u0430 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u043a\u0430\u043a \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u043b\u0435\u0432\u0435\u0435? \u042d\u0442\u043e \u0442\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043c\u0435\u0436\u0434\u0443 \u043d\u0430\u0448\u0438\u043c \u0438 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u043c \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0441\u043f\u0440\u0430\u0432\u0430. \u0418 \u043f\u0440\u0430\u0432\u0434\u0430, \u0437\u0430\u0447\u0435\u043c \u043e\u043d\u0438 \u043d\u0430\u043c \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c, \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u043b\u0435\u0432\u0435\u0435, \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \u043d\u0438\u0445? \u0410 \u0432\u043e\u0442 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0435 \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043c \u0435\u0449\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u044c\u0441\u044f. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0438\u0437 \u0441\u0442\u0435\u043a\u0430 \u0432\u0435\u0440\u0445\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043f\u043e\u043a\u0430 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u043d\u044b \u043d\u0430\u0448\u0435\u043c\u0443. \u041a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0443 \u0432\u0435\u0440\u0445\u0443\u0448\u043a\u0438 \u0441\u0442\u0435\u043a\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u0442\u0430\u043b\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u043f\u043e\u0440\u0430 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c\u0441\u044f \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043d\u0430 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0441\u0442\u0435\u043a\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4bb\/ee0\/2d5\/4bbee02d5c8d10f9e9fcadaaeaf60424.svg\" alt=\"$(A[i], i)$\" data-tex=\"inline\"><\/math>. \u0425\u043e\u0440\u043e\u0448\u043e, \u0441\u043e \u0441\u0442\u0435\u043a\u043e\u043c \u043c\u044b \u043f\u043e\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438, \u043d\u043e \u043a\u0430\u043a \u0442\u0435\u043f\u0435\u0440\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0441\u043f\u0440\u0430\u0432\u0430 \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430? \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u0430 \u0432 \u0441\u0442\u0435\u043a\u0435 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b (\u0441\u0432\u0435\u0440\u0445\u0443 \u0432\u043d\u0438\u0437) \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0438 \u043f\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u0432 \u0441\u0442\u0435\u043a\u0435 (\u0434\u0430, \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u0446\u0438\u044f \u0441\u0442\u0435\u043a\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u043c\u0435\u0441\u0442\u043e \u0441\u0442\u0435\u043a\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c std::vector) \u043d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u043d\u043e\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fc3\/ac1\/324\/fc3ac132453a72a67470f47aecd712fa.svg\" alt=\"$A[i] \\cdot 2$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0435 \u043d\u0430\u0448\u043b\u043e\u0441\u044c, \u043d\u0443\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c \u0435\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441 (\u043c\u044b \u0436\u0435 \u0445\u0440\u0430\u043d\u0438\u043c \u0435\u0433\u043e \u0432 \u043f\u0430\u0440\u0435), \u0430 \u0435\u0441\u043b\u0438 \u043d\u0435 \u043d\u0430\u0448\u043b\u043e\u0441\u044c, \u0442\u043e \u043e\u0442\u0432\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ffb\/cad\/1b1\/ffbcad1b1eea934028c9c71e5a45ec2f.svg\" alt=\"$None$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u0425\u043e\u0440\u043e\u0448\u043e, \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u044b \u0440\u0435\u0448\u0438\u043b\u0438, \u043d\u043e \u043a\u0430\u043a\u043e\u0432\u0430 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430? \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u0441\u044f \u0438 \u0443\u0434\u0430\u043b\u0438\u0442\u0441\u044f \u0438\u0437 \u0441\u0442\u0435\u043a\u0430 \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u0440\u0430\u0437, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0430 \u0432\u0441\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0435\u043a \u043c\u044b \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043c O(n), \u0430 \u0435\u0449\u0435 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u043f\u043e\u0438\u0441\u043a\u043e\u0432, \u0447\u0442\u043e \u0437\u0430\u0439\u043c\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cba\/e5c\/054\/cbae5c05497ff7402dbf72df48a09595.svg\" alt=\"$O(n \\log n)$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u0432\u0441\u0435 \u0435\u0449\u0435 \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438. \u041f\u0430\u043c\u044f\u0442\u0438 \u043c\u044b, \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043b\u0438, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p><strong>10.06.12, \u21165<\/strong><br \/>  \u0412 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u043a\u0430\u0436\u0434\u044b\u0439 \u043c\u043e\u0436\u0435\u0442 \u0437\u043d\u0430\u0442\u044c \u0438\u043b\u0438 \u043d\u0435 \u0437\u043d\u0430\u0442\u044c \u0434\u0440\u0443\u0433\u043e\u0433\u043e (\u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math> \u0437\u043d\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/20d\/8ca\/ec6\/20d8caec693d8d8eaf70885e408419f6.svg\" alt=\"$B$\" data-tex=\"inline\"><\/math>, \u043e\u0442\u0441\u044e\u0434\u0430 \u043d\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/20d\/8ca\/ec6\/20d8caec693d8d8eaf70885e408419f6.svg\" alt=\"$B$\" data-tex=\"inline\"><\/math> \u0437\u043d\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/493\/c1c\/008\/493c1c008018df9bed4910321f29ff00.svg\" alt=\"$A$\" data-tex=\"inline\"><\/math>). \u0412\u0441\u0435 \u0437\u043d\u0430\u043a\u043e\u043c\u0441\u0442\u0432\u0430 \u0437\u0430\u0434\u0430\u043d\u044b \u0431\u0443\u043b\u0435\u0432\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/646\/75c\/284\/64675c284bcf7c94a946b44f2878e495.svg\" alt=\"$n\u00d7n$\" data-tex=\"inline\"><\/math>. \u0412 \u044d\u0442\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0439\u0442\u0438\u0441\u044c \u0438\u043b\u0438 \u043d\u0435 \u043d\u0430\u0439\u0442\u0438\u0441\u044c \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c \u2014 \u0447\u0435\u043b\u043e\u0432\u0435\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0438\u043a\u043e\u0433\u043e \u043d\u0435 \u0437\u043d\u0430\u0435\u0442, \u043d\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0437\u043d\u0430\u044e\u0442 \u0432\u0441\u0435. \u041f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043b \u0432 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c \u0438\u043b\u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u043b, \u0447\u0442\u043e \u0435\u0435 \u0432 \u044d\u0442\u043e\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043d\u0435\u0442. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0414\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043f\u0443\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f78\/429\/2a4\/f784292a43b5ac4c91d734a324823f70.svg\" alt=\"$K_{ij} = 1$\" data-tex=\"inline\"><\/math>, \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0439 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u0437\u043d\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u0433\u043e \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u0430, \u0438 0 \u0438\u043d\u0430\u0447\u0435. <\/p>\n<p>  <\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u0437\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9fe\/45d\/eb5\/9fe45deb5bdc405e3052fd9d1ca475bb.svg\" alt=\"$K_{ij} = 1 ~ (i \\neq j)$\" data-tex=\"inline\"><\/math>, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0439 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c\u044e, \u0432\u0435\u0434\u044c \u043e\u043d \u043a\u043e\u0433\u043e-\u0442\u043e \u0437\u043d\u0430\u0435\u0442, \u0430 \u0432\u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u0439 \u043c\u043e\u0436\u0435\u0442, \u0430 \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6bb\/f7e\/5b3\/6bbf7e5b34c8a668693e525bd8143659.svg\" alt=\"$K_{ij} = 0$\" data-tex=\"inline\"><\/math>, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u0439 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c\u044e, \u0432\u0435\u0434\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0439 \u0435\u0433\u043e \u043d\u0435 \u0437\u043d\u0430\u0435\u0442. <\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u043d\u0430\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c: \u043f\u0443\u0441\u0442\u044c \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u2014 \u043d\u0430\u0448 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u0432 \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u0438. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043d\u0430\u0447\u043d\u0435\u043c \u0438\u0434\u0442\u0438 \u043f\u043e \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432\u043f\u0440\u0430\u0432\u043e, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u043c 1, \u0441\u043a\u0430\u0436\u0435\u043c, \u0432 \u0441\u0442\u043e\u043b\u0431\u0446\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/30f\/b68\/14e\/30fb6814eea0091044df0e5de33dfbc2.svg\" alt=\"$l$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u043b\u044e\u0434\u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u043f\u0440\u043e\u0439\u0434\u0435\u043d\u043d\u044b\u043c \u0441\u0442\u043e\u043b\u0431\u0446\u0430\u043c (\u0433\u0434\u0435 \u0431\u044b\u043b \u0437\u0430\u043f\u0438\u0441\u0430\u043d 0), \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044f\u043c\u0438, \u0430 \u0447\u0435\u043b\u043e\u0432\u0435\u043a, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435, \u0442\u043e\u0436\u0435 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c\u044e, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043d \u043a\u043e\u0433\u043e-\u0442\u043e \u0437\u043d\u0430\u0435\u0442 (\u0430 \u0438\u043c\u0435\u043d\u043d\u043e, \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u0442\u0440\u043e\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/30f\/b68\/14e\/30fb6814eea0091044df0e5de33dfbc2.svg\" alt=\"$l$\" data-tex=\"inline\"><\/math>). \u0422\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/30f\/b68\/14e\/30fb6814eea0091044df0e5de33dfbc2.svg\" alt=\"$l$\" data-tex=\"inline\"><\/math>-\u0439 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u2014 \u043d\u0430\u0448 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u0432 \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u0438, \u0438 \u043d\u0430\u0447\u043d\u0435\u043c \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0441 \u043a\u043b\u0435\u0442\u043a\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18d\/918\/b33\/18d918b33ed1c9479e0fb2edc0ab0812.svg\" alt=\"$(l, l + 1)$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u043d\u0430 \u043f\u0443\u0442\u0438 \u043d\u0430\u043c \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0442\u0441\u044f 1, \u0442\u043e \u043e\u0431\u043d\u043e\u0432\u0438\u043c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u0430\u0442\u0430, \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435, \u043f\u043e\u043a\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u0434\u0442\u0438 \u0432\u043f\u0440\u0430\u0432\u043e. \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043b\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043d\u0430\u0448 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0441\u0442\u044c\u044e. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c, \u0447\u0442\u043e \u0432 \u0441\u0442\u043e\u043b\u0431\u0446\u0435, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u043c \u0435\u043c\u0443, \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b (\u043a\u0440\u043e\u043c\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u043d\u0430 \u0433\u043b\u0430\u0432\u043d\u043e\u0439 \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u0438), \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0435\u0433\u043e \u0432\u0441\u0435 \u0437\u043d\u0430\u044e\u0442, \u0430 \u0432 \u0435\u0433\u043e \u0441\u0442\u0440\u043e\u043a\u0435 \u0432\u0441\u0435 \u043d\u0443\u043b\u0438, \u0442\u043e \u0435\u0441\u0442\u044c \u043e\u043d \u043d\u0438\u043a\u043e\u0433\u043e \u043d\u0435 \u0437\u043d\u0430\u0435\u0442. \u041f\u043e\u043a\u0430 \u043c\u044b \u0448\u043b\u0438 \u043f\u043e \u043c\u0430\u0442\u0440\u0438\u0446\u0435, \u043c\u044b \u0434\u0432\u0438\u0433\u0430\u043b\u0438\u0441\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043f\u0440\u0430\u0432\u043e, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0430 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u043e\u0431\u0435\u0436\u0430\u043b\u0438\u0441\u044c \u043f\u043e \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438 \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0441\u0442\u043e\u043b\u0431\u0446\u0443, \u0447\u0442\u043e \u0442\u0430\u043a\u0436\u0435 \u0437\u0430\u043d\u044f\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u0418\u0442\u043e\u0433\u043e: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math> \u0432\u0440\u0435\u043c\u0435\u043d\u0438. \u0422\u0430\u043a\u0436\u0435 \u043d\u0438\u0447\u0435\u0433\u043e, \u043a\u0440\u043e\u043c\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u043c\u044b \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u043b\u0438 (\u0441\u0447\u0438\u0442\u0430\u0435\u043c, \u0447\u0442\u043e \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0431\u044b\u043b\u0430 \u0434\u0430\u043d\u0430 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0438 \u0432 \u0440\u0430\u0441\u0447\u0435\u0442 \u043f\u0430\u043c\u044f\u0442\u0438 \u043d\u0435 \u0432\u0445\u043e\u0434\u0438\u0442), \u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u043c\u044b \u0437\u0430\u043d\u044f\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u043b\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435! <\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0431\u044b\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u0440\u0435\u0431\u0443\u044e\u0449\u0438\u0435 \u0441\u043c\u0435\u043a\u0430\u043b\u043a\u0438 \u0438 \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0437\u043d\u0430\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u0430 \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0436\u0435\u0441\u0442\u0438!<\/p>\n<p>  <\/p>\n<p><strong>2019, \u043e\u043d\u043b\u0430\u0439\u043d-\u043a\u043e\u043d\u0442\u0435\u0441\u0442, \u0437\u0430\u0434\u0430\u0447\u0430 D<\/strong><\/p>\n<p>  <\/p>\n<p>\u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u0447\u0430\u0441\u0442\u044c 2<br \/>  \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438: 2 \u0441\u0435\u043a\u0443\u043d\u0434\u044b<br \/>  \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438: 256Mb<\/p>\n<p>  <\/p>\n<p>\u0412\u0430\u043c \u0434\u0430\u043d \u043d\u0435\u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0432\u0437\u0432\u0435\u0448\u0435\u043d\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e2e\/33f\/15a\/e2e33f15a96008ca33579599483c4531.svg\" alt=\"$m$\" data-tex=\"inline\"><\/math> \u0440\u0451\u0431\u0440\u0430\u043c\u0438. \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d68\/cc4\/926\/d68cc4926bf74bae8fa3b51ca4a09ec8.svg\" alt=\"$q$\" data-tex=\"inline\"><\/math> \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 \u0432\u0438\u0434\u0430 \u00ab\u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u043d\u043e\u043c\u0435\u0440 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043d\u0430 1\u00bb. \u041f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0433\u0440\u0430\u0444\u0435.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0433\u0440\u0430\u0444\u0430 \u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0433\u0440\u0430\u0444, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0433\u0440\u0430\u0444\u0430 \u0438 \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0439\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e\u043c. \u041e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c, \u0435\u0441\u043b\u0438 \u0441\u0443\u043c\u043c\u0430 \u0432\u0435\u0441\u043e\u0432 \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0432 \u043d\u0435\u0433\u043e \u0440\u0451\u0431\u0435\u0440 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430\u044f.<\/p>\n<p>  <\/p>\n<p>\u0413\u0440\u0430\u0444 \u0441\u0432\u044f\u0437\u0435\u043d \u0438 \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u0435\u0442\u0435\u043b\u044c \u0438 \u043a\u0440\u0430\u0442\u043d\u044b\u0445 \u0440\u0451\u0431\u0435\u0440. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0430 \u0432\u0435\u0441\u0430 \u0432\u0441\u0435\u0445 \u0440\u0451\u0431\u0435\u0440 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b.<\/p>\n<p>  <\/p>\n<p><em>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/em><\/p>\n<p>  <\/p>\n<p>\u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0444\u0430\u0439\u043b\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u0441\u044f \u0434\u0432\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e2e\/33f\/15a\/e2e33f15a96008ca33579599483c4531.svg\" alt=\"$m$\" data-tex=\"inline\"><\/math> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0438 \u0440\u0451\u0431\u0435\u0440 \u0433\u0440\u0430\u0444\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e (<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/088\/896\/3dd\/0888963ddc1803233ca34570a49d6b05.svg\" alt=\"$1 \\le n, m \\le 10^5, 2 \\le n)$\" data-tex=\"inline\"><\/math>. \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e2e\/33f\/15a\/e2e33f15a96008ca33579599483c4531.svg\" alt=\"$m$\" data-tex=\"inline\"><\/math> \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043f\u043e \u0442\u0440\u0438 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1d0\/034\/a09\/1d0034a09108db7af7cf42ea23a91ecd.svg\" alt=\"$w$\" data-tex=\"inline\"><\/math>. \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0432 \u0433\u0440\u0430\u0444\u0435 \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u0432\u0435\u0441\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1d0\/034\/a09\/1d0034a09108db7af7cf42ea23a91ecd.svg\" alt=\"$w$\" data-tex=\"inline\"><\/math>, \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0435\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> (<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/673\/b72\/891\/673b728919646423aa8d2cb37845a7b9.svg\" alt=\"$1 \\le u, v \\le n, 1 \\le w \\le 10$\" data-tex=\"inline\"><\/math>).<\/p>\n<p>  <\/p>\n<p>\u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d68\/cc4\/926\/d68cc4926bf74bae8fa3b51ca4a09ec8.svg\" alt=\"$q$\" data-tex=\"inline\"><\/math> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432 (<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/13a\/12b\/bbc\/13a12bbbc41acbb604ebbcfa375a720b.svg\" alt=\"$1 \\le q \\le 10^5$\" data-tex=\"inline\"><\/math>). \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d68\/cc4\/926\/d68cc4926bf74bae8fa3b51ca4a09ec8.svg\" alt=\"$q$\" data-tex=\"inline\"><\/math> \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0446\u0435\u043b\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d83\/7e6\/5ff\/d837e65ff5ecf2b43ef1866a85a9bcf6.svg\" alt=\"$id$\" data-tex=\"inline\"><\/math> (<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/915\/ec7\/e25\/915ec7e25d3c9944f3ce4e77885a43b4.svg\" alt=\"$1 \\le id \\le m$\" data-tex=\"inline\"><\/math>). \u042d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043d\u0430 \u0435\u0434\u0438\u043d\u0438\u0446\u0443 \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d83\/7e6\/5ff\/d837e65ff5ecf2b43ef1866a85a9bcf6.svg\" alt=\"$id$\" data-tex=\"inline\"><\/math>. \u0420\u0451\u0431\u0440\u0430 \u043d\u0443\u043c\u0435\u0440\u0443\u044e\u0442\u0441\u044f \u0441 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0432\u043e \u0432\u0445\u043e\u0434\u043d\u043e\u043c \u0444\u0430\u0439\u043b\u0435.<\/p>\n<p>  <\/p>\n<p><em>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/em><\/p>\n<p>  <\/p>\n<p>\u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d68\/cc4\/926\/d68cc4926bf74bae8fa3b51ca4a09ec8.svg\" alt=\"$q$\" data-tex=\"inline\"><\/math> \u0447\u0438\u0441\u0435\u043b, \u0440\u0430\u0437\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0431\u0435\u043b\u0430\u043c\u0438 \u0438\u043b\u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430\u043c\u0438 \u0441\u0442\u0440\u043e\u043a\u0438 \u2014 \u0432\u0435\u0441\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0441\u043b\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0430.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0439\u043c\u0435\u043c, \u043a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443, \u0435\u0441\u043b\u0438 \u0431\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0431\u044b\u043b\u0438 \u043f\u043e\u043c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u043d\u0430\u0448\u0438 \u0440\u0443\u043a\u0438 \u0431\u044b\u043b\u0438 \u043f\u043e\u0441\u0438\u043b\u044c\u043d\u0435\u0435 99% \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0449\u0438\u0445 \u0432 \u0428\u0410\u0414. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e. <\/p>\n<p>  <\/p>\n<p>\u041f\u0443\u0441\u043a\u0430\u0439 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u0437\u0430\u043f\u0440\u043e\u0441 &quot;\u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u043c\u0435\u0436\u0434\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math>&quot;, \u0438 \u043d\u043e\u0432\u044b\u0439 \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u0441\u0442\u0430\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u0435\u0441\u043b\u0438 \u0432 \u0434\u0435\u0440\u0435\u0432\u0435 \u043d\u0430 \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u0432\u0435\u0441\u043e\u043c \u0431\u043e\u043b\u044c\u0448\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> (\u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u0430\u043a\u043e\u0433\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u043f\u0443\u0442\u0438. \u0412 \u0441\u0438\u043b\u0443 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043d\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u0435\u0441\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k+1$\" data-tex=\"inline\"><\/math>, \u0438\u043d\u0430\u0447\u0435 \u0431\u044b \u043e\u0441\u0442\u043e\u0432 \u043d\u0435 \u0431\u044b\u043b \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430 \u043f\u0443\u0442\u0438 \u0432 \u043e\u0441\u0442\u043e\u0432\u0435 \u043c\u0435\u0436\u0434\u0443 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u043c\u0438 \u0440\u0435\u0431\u0440\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> \u0431\u044b\u043b\u043e \u0440\u0435\u0431\u0440\u043e \u0432\u0435\u0441\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/800\/bf6\/d4f\/800bf6d4f9ea71edfc2906c15df350f3.svg\" alt=\"$&gt; k + 1$\" data-tex=\"inline\"><\/math>, \u0430 \u043d\u0430\u0448\u0435 \u0440\u0435\u0431\u0440\u043e \u0431\u044b\u043b\u043e \u0432\u0435\u0441\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k + 1$\" data-tex=\"inline\"><\/math>, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u0432\u044b\u0433\u043e\u0434\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0431\u043e\u0301\u043b\u044c\u0448\u0435\u0435 \u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u043d\u0430\u0448\u0435), \u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u0434\u0430\u043b\u0438\u0442\u044c \u0435\u0433\u043e \u0438\u0437 \u043e\u0441\u0442\u043e\u0432\u0430 \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0432\u043c\u0435\u0441\u0442\u043e \u043d\u0435\u0433\u043e \u043d\u0430\u0448\u0435, \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0432 \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 1. \u042d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0\" rel=\"nofollow\">\u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0422\u0430\u0440\u044c\u044f\u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/a>. \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u043d\u0430 \u043f\u0443\u0442\u0438, \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u0438\u0437 \u0434\u0435\u0440\u0435\u0432\u0430 \u0438 \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0442\u044c \u0434\u0432\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0440\u0435\u0431\u0440\u043e\u043c. \u042d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u043b\u0438\u0431\u043e \u043d\u0430\u0438\u0432\u043d\u043e \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u043d\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u043d\u0430\u043c \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443, \u0443\u043b\u043e\u0436\u0438\u0432\u0448\u0438\u0441\u044c \u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u043b\u0438\u0431\u043e \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/214\/875\/38a\/21487538a6dbcc06fa5704effedb4282.svg\" alt=\"$O(\\log n)$\" data-tex=\"inline\"><\/math> \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 <a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=Link-Cut_Tree\" rel=\"nofollow\">link-cut tree<\/a>, \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0443 \u0432\u0430\u0441 \u0437\u0430\u0439\u043c\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0447\u0435\u043c \u0441\u0430\u043c \u043a\u043e\u043d\u0442\u0435\u0441\u0442 (\u0438 \u044d\u0442\u043e \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435). \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0434\u0440\u0443\u0433\u043e\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u0432\u0435\u0441\u0430 \u0431\u044b\u0432\u0430\u044e\u0442 \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u043e\u0442 1 \u0434\u043e 10, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c 10 \u043e\u0441\u0442\u043e\u0432\u043e\u0432 (\u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043b\u0435\u0441\u0430\u043c\u0438, \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438). \u0412 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>-\u043c \u043e\u0441\u0442\u043e\u0432\u0435 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0431\u0440\u0430 \u0432\u0435\u0441\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/630\/c17\/97d\/630c1797d7299ca9b1450e6dd805defa.svg\" alt=\"$\\le k$\" data-tex=\"inline\"><\/math>. \u041a\u0430\u0436\u0434\u044b\u0439 \u043e\u0441\u0442\u043e\u0432 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043c <a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0\" rel=\"nofollow\">\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u041a\u0440\u0430\u0441\u043a\u0430\u043b\u0430<\/a>. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0434\u0432\u0435 \u043f\u0440\u0438\u0447\u0438\u043d\u044b: \u043e\u043d \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0438\u0448\u0435\u0442\u0441\u044f, \u0438 \u0421\u041d\u041c\u044b (<a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0\" rel=\"nofollow\">\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u043d\u0435\u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432<\/a>) \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u0430, \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u043f\u043e\u0441\u043b\u0435 \u043d\u0435\u0433\u043e, \u043d\u0430\u043c \u0435\u0449\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u044f\u0442\u0441\u044f \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u0435\u0440\u0432\u044b\u0439 \u043e\u0441\u0442\u043e\u0432 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u0432\u0442\u043e\u0440\u043e\u0433\u043e, \u0432\u0442\u043e\u0440\u043e\u0439 \u0442\u0440\u0435\u0442\u044c\u0435\u0433\u043e, \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>  <\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c74\/1de\/5be\/c741de5be49f902186d30bc5f93ed569.svg\" alt=\"$(u, v)$\" data-tex=\"inline\"><\/math> \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u043b\u0441\u044f \u043d\u0430 1 \u0438 \u0441\u0442\u0430\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0435\u0433\u043e \u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>-\u0439 \u043e\u0441\u0442\u043e\u0432. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0421\u041d\u041c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c, \u043b\u0435\u0436\u0430\u0442 \u043b\u0438 \u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>-\u043c \u043e\u0441\u0442\u043e\u0432\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0435 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043d\u0435 \u0442\u0430\u043a, \u0442\u043e \u043d\u0430 \u043f\u0443\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e \u0432\u0435\u0441\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k+1$\" data-tex=\"inline\"><\/math>, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u043c\u043e\u0436\u043d\u043e \u0435\u0433\u043e \u0432\u044b\u043a\u0438\u043d\u0443\u0442\u044c \u0438 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 \u043d\u0430\u0448\u0435. \u041d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0435 \u044d\u0442\u043e \u044f\u0432\u043d\u043e \u043d\u0435 \u0431\u0443\u0434\u0435\u043c, \u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0441\u043b\u0438\u044f\u043d\u0438\u0435 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> \u0432 \u0421\u041d\u041c\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>-\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u0430, \u0437\u0430\u043e\u0434\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0432 \u0432\u0435\u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0441\u0442\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0430 1. \u0415\u0441\u043b\u0438 \u0436\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/784\/f98\/db3\/784f98db37a499162c1479600e8465ed.svg\" alt=\"$u$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c1\/778\/187\/1c1778187263268cc347012d16da61e2.svg\" alt=\"$v$\" data-tex=\"inline\"><\/math> \u043b\u0435\u0436\u0430\u0442 \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0435 \u0441\u0432\u044f\u0437\u043d\u043e\u0441\u0442\u0438 \u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>-\u043c \u043e\u0441\u0442\u043e\u0432\u0435, \u0442\u043e \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u0435\u0441\u0442\u044c \u043f\u0443\u0442\u044c \u043f\u043e \u0440\u0435\u0431\u0440\u0430\u043c \u0441 \u0432\u0435\u0441\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/630\/c17\/97d\/630c1797d7299ca9b1450e6dd805defa.svg\" alt=\"$\\le k$\" data-tex=\"inline\"><\/math>, \u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u0435 \u0432\u0435\u0441\u0430 \u043d\u0430\u0448\u0435\u0433\u043e \u0440\u0435\u0431\u0440\u0430 \u043d\u0435 \u043f\u0440\u0438\u043d\u0435\u0441\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u043f\u043e\u043b\u044c\u0437\u044b.<\/p>\n<p>  <\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0443 \u0440\u0435\u0448\u0438\u043b\u0438, \u043f\u0438\u0448\u0435\u0442\u0441\u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e, \u0430 \u0447\u0442\u043e \u0442\u0430\u043c \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438 \u043f\u0430\u043c\u044f\u0442\u0438? <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d00\/cc1\/e57\/d00cc1e57dbac07b3bf8b28a46f809a9.svg\" alt=\"$O(\\alpha(n))$\" data-tex=\"inline\"><\/math> \u043d\u0430 \u0437\u0430\u043f\u0440\u043e\u0441 \u0438 \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043f\u0438\u0441\u0430\u0442\u044c \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435 \u0437\u0430\u0431\u043e\u0442\u044f\u0441\u044c \u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/131\/f71\/b36\/131f71b365220b55d96d2752eb6de17e.svg\" alt=\"$O(10 \\cdot m \\log n) = O(m \\log n)$\" data-tex=\"inline\"><\/math> \u043d\u0430 \u043f\u0440\u0435\u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0438\u043d\u0433. \u0412 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u043e \u0443\u043b\u043e\u0436\u0438\u0442\u044c\u0441\u044f, Accepted \ud83d\ude42<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/494998\/\"> https:\/\/habr.com\/ru\/post\/494998\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/494998\/\">\n<p>\u041f\u0440\u0438\u0432\u0435\u0442! \u041c\u0435\u043d\u044f \u0437\u043e\u0432\u0443\u0442 \u0410\u043b\u0435\u043a\u0441\u0430\u043d\u0434\u0440 \u041a\u0443\u0440\u0438\u043b\u043a\u0438\u043d, \u0438 \u044f \u0432\u0435\u0434\u0443 \u043a\u0443\u0440\u0441 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0432 \u00ab\u0428\u0410\u0414 Helper\u00bb. \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0437\u0431\u0435\u0440\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u0434\u0430\u0447 \u0438\u0437 \u0432\u0441\u0442\u0443\u043f\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u044d\u043a\u0437\u0430\u043c\u0435\u043d\u043e\u0432 \u043f\u0440\u043e\u0448\u043b\u044b\u0445 \u043b\u0435\u0442, \u0447\u0442\u043e\u0431\u044b \u0432\u044b \u0441\u043c\u043e\u0433\u043b\u0438 \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u0432\u0430\u0441 \u0436\u0434\u0435\u0442, \u0438 \u043f\u043e\u043d\u044f\u0442\u044c, \u0447\u0435\u043c\u0443 \u043c\u044b \u0441\u043c\u043e\u0436\u0435\u043c \u0432\u0430\u0441 \u043d\u0430\u0443\u0447\u0438\u0442\u044c \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u043a\u0443\u0440\u0441\u0435. \u041d\u0430\u0434\u0435\u044e\u0441\u044c, \u0447\u0442\u043e \u0432\u044b \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442\u0435 \u043c\u043e\u044e \u043b\u044e\u0431\u043e\u0432\u044c \u043a \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u043c \u0437\u0430\u0434\u0430\u0447\u0430\u043c \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0435 \u0438\u0441\u043a\u0440\u0435\u043d\u043d\u0435\u0435 \u0443\u0434\u043e\u0432\u043e\u043b\u044c\u0441\u0442\u0432\u0438\u0435 \u043e\u0442 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0441\u0442\u0430! \u0418\u0442\u0430\u043a, \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u043c&#8230;<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/na\/im\/kg\/naimkgdsyccbubz6mky9z7q-kxw.png\"><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-301059","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/301059","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=301059"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/301059\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=301059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=301059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=301059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}