\u6211\u4eec\u5c06\u4e00\u68f5\u4ee5\\(Splay\\)\u65b9\u5f0f\u7ef4\u62a4\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u5c01\u88c5\u4e3a\u4e00\u4e2a\u5bf9\u8c61\u3002
\n\u5bf9\u4e8e\u8fd9\u4e2a\u5bf9\u8c61\uff0c\u6211\u4eec\u5b9a\u4e49\u5b83\u7684\u4e00\u7c7b\u79c1\u6709\u5bf9\u8c61\\(Node\\)\uff0c\u4ee3\u8868\u4e8c\u53c9\u641c\u7d22\u6811\u4e0a\u7684\u4e00\u4e2a\u8282\u70b9\u3002
\n\u5bf9\u4e8e\u8fd9\u4e2a\u8282\u70b9\uff0c\u5728\u901a\u5e38\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u9700\u8981\u7ef4\u62a4\u7684\u4fe1\u606f\u5305\u62ec\uff1a
\n\\(sn\\)\uff0c\u8fd9\u662f\u4e00\u4e2a\u6709\u4e24\u4e2a\u5143\u7d20\u7684\u6570\u7ec4\u3002\u5176\u4e2d\u7b2c\\(0\\)\u9879\u8868\u793a\u5de6\u5b50\u8282\u70b9\uff0c\u7b2c\\(1\\)\u8868\u793a\u53f3\u5b50\u8282\u70b9\u3002
\n\\(fa\\)\uff0c\u8868\u793a\u5b83\u7684\u7236\u8282\u70b9\u3002
\n\\(v\\)\uff0c\u8868\u793a\u5b83\u7684\u503c\u3002
\n\\(nm\\)\uff0c\u8868\u793a\u503c\u4e3a\\(v\\)\u7684\u6570\u7684\u4e2a\u6570\u3002
\n\\(sz\\)\uff0c\u8868\u793a\u6240\u6709\u5b50\u8282\u70b9\u4e2d\u7684\u6570\u7684\u4e2a\u6570\u7684\u548c\u3002 <\/p>\n\n\n\n
\u5bf9\u4e8e\u4e00\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\u4e0a\u7684\u4e00\u4e2a\u8282\u70b9\uff0c\u6211\u4eec\u5b9a\u4e49\u5b83\u7684\u65cb\u8f6c\u3001\u5355\u65cb\u548c\u53cc\u65cb\u64cd\u4f5c\u3002
\n\u5b9a\u4e49\u4e00\u4e2a\u51fd\u6570\\(fndD(X)\\)\uff0c\u8868\u793a\u4e00\u4e2a\u8282\u70b9\u76f8\u5bf9\u4e8e\u5b83\u7684\u7236\u8282\u70b9\u662f\\(fndD(X)\\)\u5b50\u8282\u70b9
\n\u90a3\u4e48\uff0c\u4e00\u4e2a\u8282\u70b9\\(X\\)\u7684\u65cb\u8f6c\u64cd\u4f5c\u4e3a\uff1a
\n\u5c06\u5b83\u7684\\(fndD(X)\\ xor\\ 1\\)\u5b50\u8282\u70b9\u4f5c\u4e3a\u5b83\u7684\u7236\u8282\u70b9\u7684\\(fndD(X)\\)\u5b50\u8282\u70b9\uff0c\u5e76\u5c06\\(X\\)\u4f5c\u4e3a\u5b83\u7684\u7956\u7236\u8282\u70b9\u7684\\(fndD(X_fa)\\)\u8282\u70b9\uff0c\u7136\u540e\u5c06\u5b83\u539f\u6765\u7684\u7236\u8282\u70b9\u53d8\u6210\u5b83\u7684\\(fndD(X)\\ xor \\ 1\\)\u8282\u70b9\u3002
\n\u5b9a\u4e49\u4e00\u4e2a\u8282\u70b9\u7684\u5355\u65cb\u64cd\u4f5c\u4e3a\uff0c\u5c06\u8fd9\u4e2a\u8282\u70b9\u5411\u4e0a\u65cb\u8f6c\u4e24\u6b21\u3002
\n\u5b9a\u4e49\u4e00\u4e2a\u8282\u70b9\u7684\u53cc\u65cb\u64cd\u4f5c\u4e3a\uff0c\u5c06\u8fd9\u4e2a\u8282\u70b9\u7684\u7236\u8282\u70b9\u5411\u4e0a\u65cb\u8f6c\u4e00\u6b21\uff0c\u7136\u540e\u518d\u5c06\u8fd9\u4e2a\u8282\u70b9\u5411\u4e0a\u65cb\u8f6c\u4e00\u6b21\u3002
\n\u540c\u65f6\uff0c\u6211\u4eec\u5b9a\u4e49\u4e00\u4e2a\u5c06\u4e00\u4e2a\u8282\u70b9\u4e00\u76f4\u4f9d\u636e\u4e0b\u8ff0\u65b9\u6cd5\u5355\u65cb\/\u53cc\u65cb\u5230\u6839\u7684\u64cd\u4f5c\u4e3a\u4e00\u4e2a\u4f38\u5c55\u64cd\u4f5c\uff1a
\n\u5bf9\u4e8e\u4e00\u4e2a\u76f8\u5bf9\u4e8e\u5176\u7236\u4eb2\u7684\u4f4d\u7f6e\u4e0e\u5176\u7236\u4eb2\u76f8\u5bf9\u4e8e\u5176\u7956\u7236\u7684\u4f4d\u7f6e\u76f8\u540c\u7684\u8282\u70b9\uff0c\u5bf9\u5b83\u91c7\u7528\u53cc\u65cb\u64cd\u4f5c\u3002
\n\u5bf9\u4e8e\u4e00\u4e2a\u76f8\u5bf9\u4e8e\u5176\u7236\u4eb2\u7684\u4f4d\u7f6e\u4e0e\u5176\u7236\u4eb2\u76f8\u5bf9\u4e8e\u5176\u7956\u7236\u7684\u4f4d\u7f6e\u4e0d\u540c\u7684\u8282\u70b9\uff0c\u5bf9\u5b83\u91c7\u7528\u5355\u65cb\u64cd\u4f5c\u3002<\/p>\n\n\n\n
\u4e0b\u9762\u6211\u4eec\u7528\u4e00\u79cd\u88ab\u79f0\u4e3a\u52bf\u80fd\u5206\u6790\u6cd5\u7684\u590d\u6742\u5ea6\u5206\u6790\u65b9\u5f0f\u6765\u5206\u6790\u5b83\u7684\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n
\u6211\u4eec\u5b9a\u4e49\u5173\u4e8e\u4e00\u4e2a\u8282\u70b9\\(X\\)\u7684\u52bf\u80fd\u51fd\u6570\\(\\phi(X)\\)\uff0c\u5b9a\u4e49\u4e3a\u5b83\u7684\u5b50\u6811\u5927\u5c0f\u53d6\u5bf9\u6570\u3002\u6211\u4eec\u5b9a\u4e49\u5173\u4e8e\u6574\u68f5\u4e8c\u53c9\u641c\u7d22\u6811\\(T\\)\u7684\u4e00\u4e2a\u52bf\u80fd\u51fd\u6570\\(\\Phi (T)\\)\uff0c\u5b9a\u4e49\u4e3a\u5b83\u7684\u6240\u6709\u8282\u70b9\u7684\\(\\phi\\)\u503c\u4e4b\u548c\u3002<\/p>\n\n\n\n
\u5bf9\u4e8e\u7b2c\\(i\\)\u6b21\u64cd\u4f5c\uff0c\u6211\u4eec\u5b9a\u4e49\u4e00\u4e2a\u51fd\u6570\\(T\\)\u548c\u4e00\u4e2a\u644a\u8fd8\u4ee3\u4ef7\u8f85\u52a9\u51fd\u6570\\(A\\)\uff0c\u5176\u4e2d\\(T(i)\\)\u8868\u793a\u7b2c\\(i\\)\u6b21\u64cd\u4f5c\u6d88\u8017\u7684\u5b9e\u9645\u65f6\u95f4\u3002\\(A(i)\\)\u7531\u4e0b\u8ff0\u5f0f\u5b50\u5b9a\u4e49\uff1a
\n$$A_{i}=T_{i}+\\Phi_{i}-\\Phi_{i-1}$$
\n\u90a3\u4e48\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u516c\u5f0f\uff1a
\n$$A_{sum}=\\sum_{i=1}^{q}A_{i}=\\sum_{i=1}^{q}T_{i}+\\Phi_{q}-\\Phi_{0}$$
\n\u6545\u800c\uff0c\u6211\u4eec\u53ea\u9700\u8981\u6c42\u51fa\u5bf9\u4e8e\u6bcf\u4e00\u6b21\u64cd\u4f5c\u7684\\(T\\)\u4e0e\\(\\Delta\\Phi\\)\u5373\u53ef\u3002<\/p>\n\n\n\n
\u8003\u8651\u5230\uff0c\u6bcf\u4e00\u4e2a\u64cd\u4f5c\u4e8b\u5b9e\u4e0a\u90fd\u53ef\u4ee5\u89c6\u4e3a\u4e00\u6b21\\(Splay\\)\u64cd\u4f5c\uff0c\u6240\u4ee5\u6211\u4eec\u53ea\u9700\u8981\u8003\u8651\u5404\u7c7b\\(Splay\\)\u64cd\u4f5c\u9020\u6210\u7684\u5f71\u54cd\u5373\u53ef\u3002
\n\u6545\u800c\uff0c\u6211\u4eec\u9700\u8981\u8ba1\u7b97\u7684\u4fbf\u662f\u65cb\u8f6c\u3001\u5355\u65cb\u548c\u53cc\u65cb\u5bf9\u7684\u64cd\u4f5c\u590d\u6742\u5ea6\u4ee5\u53ca\u5b83\u4eec\u5bf9\\(\\Phi(T)\\)\u7684\u5f71\u54cd\u3002<\/p>\n\n\n\n
\u9996\u5148\u6211\u4eec\u5206\u6790\u65cb\u8f6c\u64cd\u4f5c\u3002
\n\u5bb9\u6613\u77e5\u9053\uff0c\u5bf9\u4e8e\u4e00\u6b21\u5173\u4e8e\u8282\u70b9\\(X\\)\u7684\u65cb\u8f6c\u64cd\u4f5c\uff0c\u4f1a\u6539\u53d8\\(\\phi\\)\u503c\u7684\u6709\u4e14\u4ec5\u6709\u4e24\u4e2a\u8282\u70b9\uff1a\\(X\\)\u548c\u5b83\u7684\u7236\u4eb2\\(Y\\)\u3002
\n\u6211\u4eec\u5b9a\u4e49\\(X\\)\u65cb\u8f6c\u540e\u7684\u8282\u70b9\u4e3a\\(X’\\)\uff0c\\(Y\\)\u65cb\u8f6c\u540e\u7684\u8282\u70b9\u4e3a\\(Y’\\)\uff0c\u5f88\u5bb9\u6613\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u5f0f\u5b50\uff1a
\n$$\\Delta\\Phi = \\phi_{X’} – \\phi_{X} + \\phi_{Y’} – \\phi_{Y}$$
\n\u8003\u8651\u5230\u65cb\u8f6c\u64cd\u4f5c\u540e\uff0c\\(X’\\)\u4f4d\u4e8e\\(Y\\)\u7684\u4f4d\u7f6e\uff0c\u5e76\u4e14\u8282\u70b9\u7684\u6570\u91cf\u6ca1\u6709\u589e\u51cf\u3001\u5bf9\u7236\u8282\u70b9\u4e5f\u6ca1\u6709\u5f71\u54cd\uff0c\u6240\u4ee5\u5f97\u5230\\(\\phi_{X’}=\\phi_{Y}\\)
\n\u8003\u8651\\(Y’\\)\u662f\\(X’\\)\u7684\u5b50\u8282\u70b9\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230
\n$$ \\phi_{X’} > \\phi_{Y’}$$
\n\u5c06\u4e0a\u8ff0\u4e24\u5f0f\u4ee3\u5165\u5f0f\u4e2d\uff0c\u53ef\u5f97\uff1a
\n$$\\Delta\\Phi < \\phi_{X’} – \\phi_{X}$$
\n\u4e8e\u662f\u53ef\u4ee5\u8bc1\u660e\uff0c\u4e00\u6b21\u65cb\u8f6c\u7684\u5747\u644a\u590d\u6742\u5ea6\u4e0a\u754c\u662f\\(O(\\phi_{X’}-\\phi_{X})\\)<\/p>\n\n\n\n
\u7136\u540e\u6211\u4eec\u5206\u6790\u5355\u65cb\u64cd\u4f5c\u3002
\u4f9d\u7136\u662f\u5b9a\u4e49\u4e00\u4e2a\u5173\u4e8e\u8282\u70b9\\(X\\)\u7684\u65cb\u8f6c\u64cd\u4f5c\uff0c\u5b9a\u4e49\u5b83\u7684\u7236\u4eb2\u4e3a\\(Y\\)\uff0c\u7956\u7236\u4e3a\\(Z\\)\uff0c\u65cb\u8f6c\u540e\u5206\u522b\u4e3a\\(X’,Y’,Z’\\)
\u5f88\u5bb9\u6613\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u5f0f\u5b50\uff1a
$$\\Delta\\Phi = \\phi_{X’} – \\phi_{X} + \\phi_{Y’} – \\phi_{Y} + \\phi_{Z’} – \\phi_{Z}$$
\u540c\u7406\u4e8e\u65cb\u8f6c\u64cd\u4f5c\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\uff1a
$$\\phi_{X’} = \\phi_{Z}$$
\u6545\u800c\uff1a
$$\\Delta\\Phi = – \\phi_{X} + \\phi_{Y’} – \\phi_{Y} + \\phi_{Z’}$$
\u540c\u7406\u4e8e\u65cb\u8f6c\u64cd\u4f5c\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\uff1a
$$\\phi_{Y’}<\\phi_{X’},\\phi_{X}<\\phi_{Y}$$ \u6545\u800c\uff1a$$\\Delta\\Phi < \\phi_{X’} + \\phi_{Z’} – 2\\phi_{X}$$$$\\Delta\\Phi < 2(\\phi_{X’}-\\phi_{X}) – \\phi_{X’} – \\phi_{Z’}$$\u53c8\uff0c$$\\phi_{X’} + \\phi_{Z’} = log_{2}{|X’||Z’|} > 2$$
\u6240\u4ee5\uff0c
$$\\Delta\\Phi < 2(\\phi_{X’}-\\phi_{X}) – 2$$
<\/p>\n\n\n\n
\u6545\u800c\u5355\u65cb\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u4e3a\\(O(\\phi_{X’}-\\phi_{X})\\)<\/p>\n\n\n\n
\u53cc\u65cb\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u540c\u7406\u3002<\/p>\n\n\n\n
\u4ee4\u603b\u5171\u8fdb\u884c\u4e86\\(n\\)\u6b21\u65cb\u8f6c\u64cd\u4f5c\uff0c\u5bf9\u4e8e\u603b\u4f53\u7684\u590d\u6742\u5ea6\u4e0a\u754c\uff0c\u6211\u4eec\u6709\uff1a
$$A_{sum}<\\sum_{i=1}^{n}\\phi_{i}-\\phi_{i-1}$$
\u6545\u800c\u5f97\u5230\u6700\u7ec8\u7684\u644a\u8fd8\u590d\u6742\u5ea6\uff1a\\(O(\\phi_{n})\\)<\/p>\n\n\n\n
\u7136\u800c\uff0c\u4e0a\u8ff0\u7684\u52bf\u80fd\u5206\u6790\u6cd5\u4ecd\u7136\u4e0d\u591f\u76f4\u89c2\u3002\u4e0b\u9762\u6211\u4eec\u8003\u8651\u4e00\u79cd\u57fa\u4e8e\u4f38\u5c55\u64cd\u4f5c\u7684\u6027\u8d28\u7684\u53e6\u4e00\u79cd\u5206\u6790\u6cd5\u3002
\n\u5f15\u7406\u4e00\uff1a \u6bcf\u4e00\u6b21\u4f38\u5c55\u64cd\u4f5c\uff0c\u5fc5\u7136\u4f1a\u4f7f\u5f97\u4ece\u8fd9\u4e2a\u8282\u70b9\u5230\u6839\u7684\u4e00\u6761\u94fe\u7684\u957f\u5ea6\u6298\u534a\u3002
\n\u9996\u5148\u6211\u4eec\u8003\u8651\u5355\u65cb\u548c\u53cc\u65cb\u64cd\u4f5c\u7684\u4f7f\u7528\u60c5\u51b5\u3002
\n\u6211\u4eec\u79f0\u5e94\u5f53\u4f7f\u7528\u53cc\u65cb\u7684\u60c5\u51b5\u4e3a\u4e00\u5b57\u578b\uff0c\u5e94\u5f53\u4f7f\u7528\u5355\u65cb\u7684\u60c5\u51b5\u4e3a\u4e4b\u5b57\u5f62\uff0c\u5f88\u5bb9\u6613\u53ef\u4ee5\u53d1\u73b0\uff0c\u539f\u6765\u5df2\u6709\u7684\u4e00\u6761\u94fe\u603b\u662f\u4f1a\u88ab\u62c6\u6210\u4e24\u4e2a\u90e8\u5206\u3002
\n\u800c\uff0c\u8be6\u7ec6\u5730\u8003\u8651\u5404\u79cd\u60c5\u51b5\uff0c\u6211\u4eec\u53d1\u73b0\uff0c\u4e0d\u5b58\u5728\u4e00\u79cd\u94fe\uff0c\u4f7f\u5f97\u8fd9\u79cd\u6298\u534a\u5931\u6548\u3002
\n\u6545\u800c\uff0c\u6211\u4eec\u5f97\u5230\u4e86\u5f15\u7406\u4e00\u3002<\/p>\n\n\n\n
\u4e0b\u9762\u8003\u8651\u5f15\u7406\u4e00\u662f\u600e\u6837\u5728\u5b9e\u9645\u60c5\u51b5\u4e2d\u53d1\u6325\u4f5c\u7528\u7684\u3002
\n\u6211\u4eec\u8bf4\u4e00\u4e2a\u8282\u70b9\u7684\u6df1\u5ea6\u53ef\u63a5\u53d7\uff0c\u6307\u7684\u662f\u5b83\u7684\u6df1\u5ea6\u662f\\(log_2n\\)\u7684\u5e38\u6570\u500d\u3002
\n\u8003\u8651\u5bf9\u67d0\u4e00\u4e2a\u8282\u70b9\u8fdb\u884c\u64cd\u4f5c\u3002\u5982\u679c\u8fd9\u4e2a\u8282\u70b9\u7684\u6df1\u5ea6\u53ef\u63a5\u53d7\uff0c\u90a3\u4e48\u64cd\u4f5c\u5b83\u7684\u590d\u6742\u5ea6\u4e5f\u662f\u53ef\u63a5\u53d7\u7684\u3002
\n\u5982\u679c\u8fd9\u4e2a\u8282\u70b9\u7684\u6df1\u5ea6\u4e0d\u53ef\u63a5\u53d7\uff0c\u6839\u636e\u5f15\u7406\u4e00\uff0c\u603b\u662f\u53ef\u4ee5\u5728\\(log_2n\\)\u6b21\u64cd\u4f5c\u4ee5\u5185\u5c06\u5176\u7684\u6df1\u5ea6\u53d8\u4e3a\u53ef\u63a5\u53d7\u7684\u3002
\n\u800c\u6bcf\u4e00\u6b21\u64cd\u4f5c\u6700\u591a\u53ea\u4f1a\u4ee4\u8fd9\u4e2a\u94fe\u7684\u6df1\u5ea6\u52a0\u4e00\uff0c\u56e0\u6b64\\(log_2n\\)\u6b21\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u53ef\u4ee5\u5747\u644a\u5230\u90a3\u4e9b\u4ee4\u8fd9\u4e2a\u94fe\u6df1\u5ea6\u52a0\u4e00\u7684\u64cd\u4f5c\u4e0a\uff0c\u4ece\u800c\u4f7f\u64cd\u4f5c\u7684\u5747\u644a\u6d6e\u6e23\u5ea6\u4ecd\u7136\u662f\u53ef\u63a5\u53d7\u7684\u3002<\/p>\n\n\n\n
\u6ce8\u610f\uff1a
\n1.\u4e09\u76ee\u8fd0\u7b97\u7b26\u4f18\u5148\u7ea7\u6bd4\u9017\u53f7\u9ad8\u3002
\n2.\u51fd\u6570\u540d\u4e0d\u8981\u641e\u6df7\u3002
\n3.\u6ce8\u610f\u533a\u5206\u8282\u70b9\u5927\u5c0f\u548c\u5b50\u6811\u5927\u5c0f\u3002
\n4.\u5f53\u5bfb\u627e\u524d\u9a71\u7684\u65f6\u5019\uff0c\u5f53\u524d\u503c\u4e0e\u5f53\u524d\u70b9\u7684\u503c\u76f8\u7b49\u5e94\u5f53\u5411\u5de6\u8d70\uff1b\u5f53\u5bfb\u627e\u540e\u7ee7\u65f6\uff0c\u5f53\u524d\u503c\u4e0e\u5f53\u524d\u70b9\u7684\u503c\u76f8\u7b49\u5e94\u5f53\u5411\u53f3\u8d70\u3002 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#define MAXQ 1000005\ninline int Max(int A,int B){\n return A>B?A:B;\n}\ninline int Min(int A,int B){\n return A<B?A:B;\n}\nclass Splay{\n\tprivate:\n\t\tclass Node{\n \t\tpublic:\n \t\t\tint sn[2];\n \t\t\tint fa;\n \t\t\tint v;\n \t\t\tint nm;\n \t\t\tint sz;\n \t\t\tinline void set(int FA,int LS,int RS,int V){\n \t\t\t fa=FA,v=V,sn[0]=LS,sn[1]=RS,nm=1,sz=1;\n }\n inline void init(){\n \tsn[0]=sn[1]=fa=v=nm=sz=0;\n\t\t\t\t}\n\t\t};\n\t\tint INF;\n\t\tNode tr[MAXQ];\n\t\tint st[100005],tp,cnt,rt;\n\t\tinline int fndD(int X){\n\t\t\treturn tr[tr[X].fa].sn[0]==X?0:1;\n\t\t}\n\t\tinline void szRnw(int X){\n\t\t tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].nm;\n }\n\t\tinline void splayOne(int X){\n\t\t\tint D=fndD(X),D2=fndD(tr[X].fa);\n\t\t\ttr[tr[X].sn[D^1]].fa=tr[X].fa;tr[tr[X].fa].sn[D]=tr[X].sn[D^1];\n\t\t\ttr[X].sn[D^1]=tr[X].fa;tr[X].fa=tr[tr[X].sn[D^1]].fa;\n\t\t\ttr[tr[X].sn[D^1]].fa=X;tr[tr[X].fa].sn[D2]=X;\n\t\t\tszRnw(tr[X].sn[D^1]);szRnw(X);\n\t\t\tif(!tr[X].fa){\n\t\t\t\trt=X;\n\t\t\t}\n\t\t}\n\t\tinline void splayTwo(int X){\n\t\t int D=fndD(X),D2=fndD(tr[X].fa);\n\t\t tr[X].fa?\n\t\t\t\t(tr[tr[X].fa].fa?\n\t\t\t\t\t(D==D2?\n\t\t\t\t\t\t(splayOne(tr[X].fa),splayOne(X),0)\n\t\t\t\t\t\t:(splayOne(X),splayOne(X),0))\n\t\t\t\t\t:(splayOne(X),0))\n\t\t\t\t:0;\n\t\t}\n\t\tinline void splayRnw(int X){\n\t\t\twhile(tr[X].fa){\n\t\t\t splayTwo(X);\n }\n\t\t}\n\t\tinline int nwlc(int FA,int LS,int RS,int V,int D){\n\t\t\tif(!cnt){\n\t\t\t\trt=1;\n\t\t\t}\n\t\t\tint P=tp?st[tp--]:++cnt;\n\t\t tr[FA].sn[D]=P;\n\t\t tr[P].set(FA,LS,RS,V);\n\t\t return P;\n }\n inline int fnd(int V){\n int P=rt,FP=0;\n while(P){\n FP=P;\n if(tr[P].v==V){\n splayRnw(P);\n return P;\n }\n P=tr[P].sn[tr[P].v>V?0:1];\n }\n return FP;\n }\n inline int fndMn(int X){\n int P=X,FP=tr[X].fa;\n while(P){\n FP=P;\n P=tr[P].sn[0];\n }\n return FP;\n }\n inline int fndMx(int X){\n \tint P=X,FP=tr[X].fa;\n \twhile(P){\n \t\tFP=P;\n \t\tP=tr[P].sn[1];\n\t\t\t}\n\t\t\treturn FP;\n\t\t}\n\t\tinline void clr(int X,int D){\n\t\t\tif(D==2){\n\t\t\t\ttr[X].init();\n\t\t\t\tst[++tp]=X;\n\t\t\t\treturn;\n\t\t\t}\n\t\t\trt=tr[X].sn[D],tr[tr[X].sn[D]].fa=0;\n\t\t\ttr[X].init();\n\t\t\tst[++tp]=X;\n\t\t}\n\t\tinline void init(int P){\n\t\t\tif(!tr[P].sn[0]||!tr[P].sn[1]){\n\t\t\t\ttr[P].sn[0]?(clr(P,0)):(tr[P].sn[1]?clr(P,1):clr(P,2));\n\t\t\t}else{\n\t\t\t\tint RS=fndMn(tr[P].sn[1]);\n\t\t\t\ttr[RS].sn[0]=tr[P].sn[0],tr[tr[P].sn[0]].fa=RS;\n\t\t\t\tclr(P,1);\n\t\t\t\tsplayRnw(RS);\n\t\t\t}\n\t\t\tif(!tr[rt].v&&!tr[rt].sz&&!tr[rt].fa&&!tr[rt].nm){\n\t\t\t\tsplayInit();\n\t\t\t}\n\t\t}\n\t\tinline void prnt(int X){\n\t\t\tif(!X){\n\t\t\t\treturn;\n\t\t\t}\n\t\t\tprnt(tr[X].sn[0]);\n\t\t\tprintf(\"(%d)%d:[%d,%d][%d] \",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].fa);\n\t\t\tprnt(tr[X].sn[1]);\n\t\t}\n\tpublic:\n\t inline void psh(int V){\n\t int P=rt,FP=0,D=0;\n\t while(P){\n\t FP=P;\n\t if(tr[P].v==V){\n\t ++tr[P].nm;\n\t splayRnw(P);\n\t return;\n }\n D=tr[P].v>V?0:1;\n\t P=tr[P].sn[tr[P].v>V?0:1];\n }\n splayRnw(nwlc(FP,0,0,V,D));\n }\n inline void del(int V){\n int P=fnd(V);\n splayRnw(P);\n tr[P].nm>1?(--tr[P].nm):(init(P),0);\n }\n inline int fndPre(int V){\n int P=rt,RT=-INF;\n while(P){\n RT=tr[P].v<V?Max(RT,tr[P].v):RT;\n P=tr[P].sn[tr[P].v<V?1:0];\n }\n return RT;\n }\n inline int fndNxt(int V){\n int P=rt,RT=INF;\n while(P){\n RT=tr[P].v>V?Min(RT,tr[P].v):RT;\n P=tr[P].sn[tr[P].v>V?0:1];\n }\n return RT;\n }\n inline int rnk(int V){\n int P=rt,RT=0;\n while(P){\n if(tr[P].v>V){\n P=tr[P].sn[0];\n }else if(tr[P].v==V){\n RT+=tr[tr[P].sn[0]].sz;\n splayRnw(P);\n return RT+1;\n }else{\n RT+=tr[tr[P].sn[0]].sz+tr[P].nm;\n P=tr[P].sn[1]; \n }\n }\n return RT+1;\n }\n inline int aRnk(int V){\n int P=rt;\n while(P){\n if(tr[tr[P].sn[0]].sz+tr[P].nm<V){\n V-=(tr[tr[P].sn[0]].sz+tr[P].nm);\n P=tr[P].sn[1];\n }else if(tr[tr[P].sn[0]].sz<V){\n return tr[P].v;\n }else{\n P=tr[P].sn[0];\n }\n }\n return P;\n }\n inline void splayInit(){\n\t\t\tINF=2147483647,tp=0,cnt=0,rt=0;\n\t\t\tmemset(tr,0,sizeof(tr));\n\t\t}\n\t\tinline void splayPrnt(){\n\t\t\tprnt(rt);\n\t\t\tputs(\"\");\n\t\t}\n}; \nSplay T;\nvoid init(){\n\tint n,x,op;\n\tscanf(\"%d\",&n);\n\tfor(int i=1;i<=n;++i){\n\t\t\/\/T.splayPrnt();\n\t\tscanf(\"%d%d\",&op,&x);\n\t\tswitch(op){\n\t\t\tcase 1:{\n\t\t\t\tT.psh(x);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 2:{\n\t\t\t\tT.del(x);\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 3:{\n\t\t\t\tprintf(\"%d\\n\",T.rnk(x));\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 4:{\n\t\t\t\tprintf(\"%d\\n\",T.aRnk(x));\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 5:{\n\t\t\t\tprintf(\"%d\\n\",T.fndPre(x));\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tcase 6:{\n\t\t\t\tprintf(\"%d\\n\",T.fndNxt(x));\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n}\nint main(){\n\/\/\tfreopen(\"Splay.out\",\"w\",stdout);\n\tT.splayInit();\n\tinit();\n\treturn 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u6211\u4eec\u5c06\u4e00\u68f5\u4ee5\\(Splay\\)\u65b9\u5f0f\u7ef4\u62a4\u7684\u4e8c\u53c9\u641c\u7d22\u6811\u5c01\u88c5\u4e3a\u4e00\u4e2a\u5bf9\u8c61\u3002 \u5bf9\u4e8e\u8fd9\u4e2a\u5bf9\u8c61\uff0c\u6211\u4eec\u5b9a\u4e49\u5b83\u7684\u4e00\u7c7b\u79c1\u6709\u5bf9\u8c61\\( … <\/p>\n