Результат MediaWiki API
Это HTML-представление формата JSON. HTML хорош для отладки, но неудобен для практического применения.
Укажите параметр format для изменения формата вывода. Для отображения не-HTML-представления формата JSON, присвойте format=json.
См. полную документацию или справку API для получения дополнительной информации.
{
"compare": {
"fromid": 1102,
"fromrevid": 1,
"fromns": 0,
"fromtitle": "\u0417\u0430\u0433\u043b\u0430\u0432\u043d\u0430\u044f \u0441\u0442\u0440\u0430\u043d\u0438\u0446\u0430",
"toid": 1040,
"torevid": 2,
"tons": 0,
"totitle": "\u0414\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e",
"*": "<tr><td colspan=\"2\" class=\"diff-lineno\" id=\"mw-diff-left-l1\">\u0421\u0442\u0440\u043e\u043a\u0430 1:</td>\n<td colspan=\"2\" class=\"diff-lineno\">\u0421\u0442\u0440\u043e\u043a\u0430 1:</td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div><del class=\"diffchange diffchange-inline\">'''\u0412\u0438\u043a\u0438-\u0434\u0432\u0438\u0436\u043e\u043a \u00abMediaWiki\u00bb \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d</del>.<del class=\"diffchange diffchange-inline\">'''</del></div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">== \u041e\u0431\u0449\u0438\u0435 \u0441\u0432\u0435\u0434\u0435\u043d\u0438\u044f ==</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">[[\u0424\u0430\u0439\u043b:treap_trees_height_comparison.jpg|200px|thumb|right|\u0420\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f \u043f\u043e\u0438\u0441\u043a\u0430, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432]]</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u0412\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c\u0438 \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430 \u0432\u044b\u0441\u043e\u0442\u0435 \u0434\u0435\u0440\u0435\u0432\u0430. \u0412\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u043e\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0414\u0435\u0440\u0435\u0432\u043e, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0435 N \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0443 \u043e\u0442 &lceil;log<sub>2</sub>N&rceil; \u0434\u043e N</ins>.</div></td></tr>\n<tr><td class=\"diff-marker\"></td><td class=\"diff-context diff-side-deleted\"><br/></td><td class=\"diff-marker\"></td><td class=\"diff-context diff-side-added\"><br/></td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div><del class=\"diffchange diffchange-inline\">\u0418\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e </del>\u043f\u043e <del class=\"diffchange diffchange-inline\">\u0440\u0430\u0431\u043e\u0442\u0435 </del>\u0441 <del class=\"diffchange diffchange-inline\">\u044d\u0442\u043e\u0439 \u0432\u0438\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 [//meta.wikimedia.org/wiki/%D0%9F%D0%BE%D0%BC%D0%BE%D1%89%D1%8C:%D0%A1%D0%BE%D0%B4%D0%B5%D1%80%D0%B6%D0%B0%D0%BD%D0%B8%D0%B5 \u0441\u043f\u0440\u0430\u0432\u043e\u0447\u043d\u043e\u043c \u0440\u0443\u043a\u043e\u0432\u043e\u0434\u0441\u0442\u0432\u0435]</del>.</div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041f\u0443\u0441\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u0443\u0437\u0435\u043b \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0438\u043c\u0435\u0435\u0442, \u043a\u0440\u043e\u043c\u0435 \u043a\u043b\u044e\u0447\u0430, \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043c\u0435\u043d\u0443\u0435\u043c\u043e\u0435 ''\u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c'', \u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435: \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u0435\u0440\u0435\u0432\u0430 </ins>\u043f\u043e <ins class=\"diffchange diffchange-inline\">\u0441\u0432\u043e\u0438\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0442 \u043f\u0438\u0440\u0430\u043c\u0438\u0434\u0443, \u0442\u043e \u0435\u0441\u0442\u044c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0443\u0437\u043b\u043e\u0432 \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u0432 \u0435\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432 (\u0441\u043b\u0443\u0447\u0430\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u043f\u0438\u0440\u0430\u043c\u0438\u0434\u044b). \u0422\u043e\u0433\u0434\u0430, \u0432\u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 </ins>\u0441 <ins class=\"diffchange diffchange-inline\">\u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0438\u043c\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0435\u0433\u043e \u0444\u043e\u0440\u043c\u0430 \u0437\u0430\u0434\u0430\u043d\u0430 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e</ins>.</div></td></tr>\n<tr><td class=\"diff-marker\"></td><td class=\"diff-context diff-side-deleted\"><br/></td><td class=\"diff-marker\"></td><td class=\"diff-context diff-side-added\"><br/></td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div>== <del class=\"diffchange diffchange-inline\">\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0435 \u0440\u0435\u0441\u0443\u0440\u0441\u044b </del>==</div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u0423\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e\u0441\u0442\u0438 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c. \u041a\u043e\u0440\u043d\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c. \u0412 \u043b\u0435\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 \u043a\u043b\u044e\u0447\u0430 \u043a\u043e\u0440\u043d\u044f, \u0432 \u043f\u0440\u0430\u0432\u043e\u043c \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435 &mdash; \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b (\u0434\u0435\u0440\u0435\u0432\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442 \u043e\u0441\u0442\u0430\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0430). \u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044f \u043b\u0435\u0432\u043e\u0435 \u0438 \u043f\u0440\u0430\u0432\u043e\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u044c\u044f (\u043a\u043e\u0440\u043d\u044f\u043c\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438, \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435), \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u043a \u0432\u044b\u0432\u043e\u0434\u0443, \u0447\u0442\u043e \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u0430 \u0437\u0430\u0434\u0430\u043d\u043e \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e, \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043f\u0430\u0440\u044b (\u043a\u043b\u044e\u0447 &mdash; \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442) \u0438 \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0434\u0435\u0440\u0435\u0432\u043e.</ins></div></td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div><del class=\"diffchange diffchange-inline\">* </del>[//<del class=\"diffchange diffchange-inline\">www</del>.<del class=\"diffchange diffchange-inline\">mediawiki</del>.<del class=\"diffchange diffchange-inline\">org</del>/<del class=\"diffchange diffchange-inline\">wiki</del>/<del class=\"diffchange diffchange-inline\">Manual:Configuration_settings \u0421\u043f\u0438\u0441\u043e\u043a \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u043d\u0430\u0441\u0442\u0440\u043e\u0435\u043a</del>];</div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div>* [//<del class=\"diffchange diffchange-inline\">www</del>.<del class=\"diffchange diffchange-inline\">mediawiki</del>.<del class=\"diffchange diffchange-inline\">org</del>/<del class=\"diffchange diffchange-inline\">wiki</del>/<del class=\"diffchange diffchange-inline\">Manual</del>:<del class=\"diffchange diffchange-inline\">FAQ \u0427\u0430\u0441\u0442\u043e \u0437\u0430\u0434\u0430\u0432\u0430\u0435\u043c\u044b\u0435 \u0432\u043e\u043f\u0440\u043e\u0441\u044b </del>\u0438 <del class=\"diffchange diffchange-inline\">\u043e\u0442\u0432\u0435\u0442\u044b \u043f\u043e MediaWiki]</del>;</div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"><gallery width</ins>=<ins class=\"diffchange diffchange-inline\">200px height</ins>=<ins class=\"diffchange diffchange-inline\">200px caption="\u041f\u0440\u0438\u043c\u0435\u0440\u044b \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432"></ins></div></td></tr>\n<tr><td class=\"diff-marker\" data-marker=\"\u2212\"></td><td class=\"diff-deletedline diff-side-deleted\"><div>* <del class=\"diffchange diffchange-inline\">[https</del>://<del class=\"diffchange diffchange-inline\">lists</del>.<del class=\"diffchange diffchange-inline\">wikimedia</del>.<del class=\"diffchange diffchange-inline\">org</del>/<del class=\"diffchange diffchange-inline\">mailman</del>/<del class=\"diffchange diffchange-inline\">listinfo</del>/<del class=\"diffchange diffchange-inline\">mediawiki-announce \u0420\u0430\u0441\u0441\u044b\u043b\u043a\u0430 \u0443\u0432\u0435\u0434\u043e\u043c\u043b\u0435\u043d\u0438\u0439 \u043e \u0432\u044b\u0445\u043e\u0434\u0435 \u043d\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u0441\u0438\u0439 MediaWiki</del>]<del class=\"diffchange diffchange-inline\">.</del></div></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">File:treap_example_1.jpg</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">File:treap_example_2.jpg</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"></gallery></ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u043e\u043b\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u0438\u0437 N \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0432\u044b\u0441\u043e\u0442\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 &lceil;4log<sub>2</sub>N&rceil;, \u0441\u0442\u0440\u0435\u043c\u0438\u0442\u0441\u044f \u043a 100%. \u042d\u0442\u043e\u0442 \u0444\u0430\u043a\u0442 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0438\u0434\u0435\u044e \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430: \u0435\u0441\u043b\u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u044b \u0443\u0437\u043b\u043e\u0432 \u043d\u0430\u0437\u043d\u0430\u0447\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0442\u043e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0435\u0435\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u0443, \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0449\u0443\u044e &lceil;4log<sub>2</sub>N&rceil;, \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u0440\u0435\u043d\u0435\u0431\u0440\u0435\u0436\u0438\u043c\u043e \u043c\u0430\u043b\u043e\u0439. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c\u0438 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c\u0438, \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0442 \u043f\u0438\u0440\u0430\u043c\u0438\u0434\u0443 \u043f\u043e \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u0430\u043c, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e O(logN).</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041e\u043f\u0438\u0441\u0430\u043d\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u043e\u043c (\u0434\u0435\u0440\u0430\u043c\u0438\u0434\u043e\u0439, \u0430\u043d\u0433\u043b. cartesian tree, treap). \u0415\u0441\u043b\u0438 \u043f\u0430\u0440\u044b (\u043a\u043b\u044e\u0447 &mdash; \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442) \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0443\u0437\u043b\u0430 \u043d\u0430 \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e\u0439 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u0442\u043e \u043b\u044e\u0431\u043e\u0435 \u043d\u0430\u0440\u0438\u0441\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u044b\u043c (\u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0440\u0451\u0431\u0435\u0440\u043d\u044b\u0445 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0439).</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">== \u0414\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b </ins>==</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>[<ins class=\"diffchange diffchange-inline\">http:</ins>//<ins class=\"diffchange diffchange-inline\">people</ins>.<ins class=\"diffchange diffchange-inline\">ksp</ins>.<ins class=\"diffchange diffchange-inline\">sk</ins>/<ins class=\"diffchange diffchange-inline\">~kuko</ins>/<ins class=\"diffchange diffchange-inline\">bak/index.html \u0412\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0442\u043e\u0440 \u0434\u0440\u0435\u0432\u043e\u0432\u0438\u0434\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440</ins>]<ins class=\"diffchange diffchange-inline\">, \u0432\u043a\u043b\u0430\u0434\u043a\u0430 &laquo;Treap&raquo;.</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">== \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 ==</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041f\u0440\u0435\u0436\u0434\u0435 \u0432\u0441\u0435\u0433\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0442\u0438\u043f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u044b <tt>TreapNode</tt>. \u0415\u0433\u043e \u043f\u043e\u043b\u044f\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043a\u043b\u044e\u0447, \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u0438 \u0445\u0440\u0430\u043d\u0438\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u043b\u0435\u0432\u043e\u0433\u043e \u0438 \u043f\u0440\u0430\u0432\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043c\u043a\u043e\u0432.</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> struct TreapNode {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 int k, p, v;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 TreapNode *l, *r;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 TreapNode(int key, int value) {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 k = key;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 v = value</ins>;</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 p = (double)rand() / RAND_MAX </ins>* <ins class=\"diffchange diffchange-inline\">100000;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 l = r = NULL;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 }</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> };</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">=== \u0421\u043b\u0438\u044f\u043d\u0438\u0435 \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 (merge) ===</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>[<ins class=\"diffchange diffchange-inline\">[\u0424\u0430\u0439\u043b:treap_merge.jpg|200px|thumb|right|\u041e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435 \u0434\u0435\u0440\u0430\u043c\u0438\u0434]]</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d\u044b \u0434\u0432\u0435 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u044b <tt>A<</ins>/<ins class=\"diffchange diffchange-inline\">tt> (\u0441 \u043a\u043e\u0440\u043d\u0435\u043c <tt>a<</ins>/<ins class=\"diffchange diffchange-inline\">tt>) \u0438 <tt>B</tt> (\u0441 \u043a\u043e\u0440\u043d\u0435\u043c <tt>b</tt>), \u043f\u0440\u0438\u0447\u0451\u043c \u043a\u043b\u044e\u0447\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 <tt>A</tt> \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043b\u044e\u0447\u0435\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 <tt>B</tt></ins>. <ins class=\"diffchange diffchange-inline\">\u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u043e\u0432\u0443\u044e \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u0443 <tt>T</tt> \u0438\u0437 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 <tt>A</tt> \u0438 <tt>B</tt> \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0435\u0451 \u043a\u043e\u0440\u0435\u043d\u044c</ins>.</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> TreapNode *merge(TreapNode *a, TreapNode *b) {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 if (!a || !b)</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 return a ? a : b;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 if (a->p > b->p) {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 a->r = merge(a->r, b);</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 return a;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 } else {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 b->l = merge(a, b->l);</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 return b;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 }</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> }</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041a\u043e\u0440\u043d\u0435\u043c <tt>T<</ins>/<ins class=\"diffchange diffchange-inline\">tt> \u0431\u0443\u0434\u0435\u0442 \u0442\u043e\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 <tt>A<</ins>/<ins class=\"diffchange diffchange-inline\">tt> \u0438\u043b\u0438 <tt>B</tt>, \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c. \u041d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0432\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043b\u0438\u0431\u043e <tt>a</tt>, \u043b\u0438\u0431\u043e <tt>b</tt>. \u041f\u0443\u0441\u0442\u044c <tt>(a-&gt;p &gt; b-&gt;p)</tt>, \u0442\u043e\u0433\u0434\u0430 <tt>a</tt> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430. \u0412\u0441\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u043a <tt>A</tt> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b <tt>B</tt> \u0438\u043c\u0435\u044e\u0442 \u043a\u043b\u044e\u0447\u0438, \u0431\u043e\u043b\u044c\u0448\u0438\u0435 <tt>a-&gt;k</tt>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d\u0438 \u0432\u0441\u0435 \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043c\u0435\u0449\u0435\u043d\u044b \u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e <tt>a-&gt;r</tt>. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u044b \u043f\u0435\u0440\u0435\u0448\u043b\u0438 \u043e\u0442 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f <tt>A</tt> \u0438 <tt>B</tt> \u043a \u0437\u0430\u0434\u0430\u0447\u0435 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u044f <tt>a-&gt;r</tt> \u0438 <tt>B</tt>; \u043d\u0430\u043b\u0438\u0446\u043e \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u043b\u0438\u044f\u043d\u0438\u044f (\u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e). \u0411\u0430\u0437\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u0430 \u0438\u0437 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u044f\u0435\u043c\u044b\u0445 \u0434\u0435\u0440\u0430\u043c\u0438\u0434 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0443\u0441\u0442\u043e\u0439.</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">=== \u0420\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u0438\u0435 \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 (split) ===\u00a0 </ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">[[\u0424\u0430\u0439\u043b</ins>:<ins class=\"diffchange diffchange-inline\">treap_split.jpg|200px|thumb|right|\u0420\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u0438\u0435 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u044b]]\u00a0 </ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d\u0430 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u0430 <tt>T</tt> (\u0441 \u043a\u043e\u0440\u043d\u0435\u043c <tt>t</tt>) </ins>\u0438 <ins class=\"diffchange diffchange-inline\">\u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <tt>k</tt>. \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0434\u0432\u0435 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u044b: <tt>A</tt>, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0443\u044e \u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b <tt>T</tt>, \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <tt>k</tt>, \u0438 <tt>B</tt>, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0443\u044e \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b <tt>T</tt>. \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c \u0434\u0432\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f</ins>; <ins class=\"diffchange diffchange-inline\">\u0432 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u043d\u0438 \u043f\u0435\u0440\u0435\u0434\u0430\u044e\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b, \u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u043c \u0442\u0438\u043f\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <tt>void</tt>.</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> void split(TreapNode </ins>*<ins class=\"diffchange diffchange-inline\">t, int k, TreapNode *&a, TreapNode *&b) {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 if (!t)</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 a = b = NULL;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 else if (t->k <= k) {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 split(t->r, k, t->r, b);</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 a = t;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 } else {</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 split(t->l, k, a, t->l);</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 \u00a0 \u00a0 b = t;</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u00a0 \u00a0 }</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\"> }</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">\u0415\u0441\u043b\u0438 <tt>(t-&gt;k &lt= k)</tt>, \u0442\u043e <tt>t</tt> \u0441\u0442\u0430\u043d\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c <tt>A</tt>, \u0438\u043d\u0430\u0447\u0435 &mdash; \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c <tt>B</tt>. \u041f\u0443\u0441\u0442\u044c <tt>t</tt> \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e <tt>A</tt> (\u043d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e <tt>t</tt> \u0441\u0442\u0430\u043d\u0435\u0442 \u043a\u043e\u0440\u043d\u0435\u043c <tt>A</tt>), \u0442\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0430 <tt>t-&gt;l</tt> \u0442\u0430\u043a\u0436\u0435 \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e <tt>A</tt>, \u0442\u0430\u043a \u043a\u0430\u043a \u0438\u0445 \u043a\u043b\u044e\u0447\u0438 \u043c\u0435\u043d\u044c\u0448\u0435 <tt>t-&gt;k</tt>, \u0430 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043c\u0435\u043d\u044c\u0448\u0435 <tt>k</tt>. \u0421\u0438\u0442\u0443\u0430\u0446\u0438\u044f \u0441 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u043e\u043c <tt>t-&gt;r</tt> \u0441\u043b\u043e\u0436\u043d\u0435\u0435</ins>: <ins class=\"diffchange diffchange-inline\">\u043e\u043d\u043e \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043a\u0430\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <tt>k<</ins>/<ins class=\"diffchange diffchange-inline\">tt>, \u0442\u0430\u043a \u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <tt>k<</ins>/<ins class=\"diffchange diffchange-inline\">tt></ins>. <ins class=\"diffchange diffchange-inline\">\u041f\u043e\u0441\u0442\u0443\u043f\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043c <tt>t-&gt;r</tt> \u043f\u043e <tt>k</tt>, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u0441\u044f \u0434\u0432\u0435 \u0434\u0435\u0440\u0430\u043c\u0438\u0434\u044b <tt>A'</tt> \u0438 <tt>B'</tt></ins>. <ins class=\"diffchange diffchange-inline\">\u0414\u0435\u0440\u0430\u043c\u0438\u0434\u0443 <tt>A'<</ins>/<ins class=\"diffchange diffchange-inline\">tt> \u043d\u0443\u0436\u043d\u043e \u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u0430 \u043c\u0435\u0441\u0442\u0435 <tt>t-&gt;r<</ins>/<ins class=\"diffchange diffchange-inline\">tt>, \u0442\u043e\u0433\u0434\u0430 <tt>T<</ins>/<ins class=\"diffchange diffchange-inline\">tt> \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <tt>k</tt>. <tt>B'</tt> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441 \u043a\u043b\u044e\u0447\u0430\u043c\u0438, \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 <tt>k</tt>. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u0438\u044f \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f <tt>T</tt> \u0438 <tt>B'</tt>. \u0421\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e. \u041c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e; \u0431\u0430\u0437\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 <tt>T</tt> \u043f\u0443\u0441\u0442\u0430.</ins></div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div>\u00a0</div></td></tr>\n<tr><td colspan=\"2\" class=\"diff-side-deleted\"></td><td class=\"diff-marker\" data-marker=\"+\"></td><td class=\"diff-addedline diff-side-added\"><div><ins class=\"diffchange diffchange-inline\">[[Category:\u0423\u0447\u0435\u0431\u043d\u044b\u0439 \u043a\u0443\u0440\u0441 &laquo;\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445&raquo;]</ins>]</div></td></tr>\n"
}
}