<\/p>\n
\u4e09\u7ef4 LIS\u3002<\/p>\n
\u5148\u5bf9\u4e00\u4e2a\u8f74\u8fdb\u884c\u6392\u5e8f\uff0c\u4e8e\u662f\u8f6c\u6362\u6210\u4e8c\u7ef4 LIS \u95ee\u9898\uff0c\u4f46\u662f\u8f6c\u79fb\u65f6\u5fc5\u987b\u4fdd\u8bc1 j < i\u3002\n\n\n\n\n
\u8fd9\u79cd\u505a\u6cd5\u6bd4\u8f83\u88f8\u3002\u652f\u6301\u63d2\u5165 (x_i, y_i) \u7684\u70b9\u3001\u548c\u67e5\u8be2 y_j <= y_i && z_j <= z_i \u8303\u56f4\u5185\u6240\u6709\u7684\u70b9\u5373\u53ef\u3002\n\n\n\n
\u8003\u8651\u5f53\u524d\u70b9 i\uff0c\u6211\u4eec\u5c1d\u8bd5\u5bf9\u6240\u6709 $y_j <= y_i$ \u7684\u70b9\u5efa\u7acb\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff08\u53ea\u9700\u8981\u67e5\u8be2\u524d\u7f00\uff0c\u6811\u72b6\u6570\u7ec4\u5373\u53ef\uff09\u3002\n\u652f\u6301\u63d2\u5165 $z_i$ \u70b9\uff0c\u548c\u67e5\u8be2\u6240\u6709 $z_j <= z_i$ \u7684\u70b9\uff0c\u5c31\u53ef\u4ee5\u5728 $log(n)$ \u7684\u590d\u6742\u5ea6\u5185\u5b8c\u6210\u8f6c\u79fb\u4e86\u3002\n\u8fd9\u4e2a\u95ee\u9898\u901a\u5e38\u7684\u505a\u6cd5\u662f\u79bb\u7ebf\uff0c\u5bf9 $y$ \u8f74\u6392\u5e8f\uff0c\u4f46\u662f\u56e0\u4e3a\u4e4b\u524d\u7684\u6392\u5e8f\uff0c\u76f8\u5f53\u4e8e\u6211\u4eec\u73b0\u5728\u88ab\u8981\u6c42\u5f3a\u5236\u5728\u7ebf\u3002\n\ncdq \u5206\u6cbb\u4e3a\u6211\u4eec\u63d0\u4f9b\u4e86\u4e00\u79cd\u7a81\u7834\u6027\u7684\u89e3\u51b3\u65b9\u6cd5\u3002\n\n[cpp]\nvoid cdq(int l, int r){ \n cdq(l, m); \n merge(l, r);\n cdq(m, r); \n}\n[\/cpp]\n\nmerge(l, r) \u8868\u793a\u7528\u6240\u6709 [l, m) \u4e2d\u7684\u70b9\uff0c\u53bb\u66f4\u65b0 [m, r) \u4e2d\u70b9\u3002\uff08\u663e\u7136\u8981\u6c42 [l, m) \u4e2d\u7684\u70b9\u7684 dp \u503c\u5df2\u7ecf\u7b97\u51fa\uff0c\u56e0\u6b64\u5408\u5e76\u5fc5\u987b\u653e\u5728\u9012\u5f52\u53f3\u533a\u95f4\u4e4b\u524d\u3002\uff09\n\u800c\u8fd9\u4e2a\u8fc7\u7a0b\u662f\u53ef\u4ee5\u79bb\u7ebf\u7684\u3002\n\n\u5408\u5e76\u8fc7\u7a0b\u7684\u590d\u6742\u5ea6\u662f $$O(nlogn)$$\uff0c\u603b\u7684\u590d\u6742\u5ea6\u662f $$O(nlog^2n)$$\u3002\n\n\ncdq \u5206\u6cbb\uff1a\nhttps:\/\/gist.github.com\/lychees\/66c22315b8235d61722b#file-cdq-cpp<\/a><\/p>\n