\u6811\u5957\u6811\u6709\u5f88\u591a\u79cd\uff0c\u53ef\u4ee5\u662f\u6811\u72b6\u6570\u7ec4\u5957\u7ebf\u6bb5\u6811\uff0c\u4e5f\u53ef\u4ee5\u662f\u7ebf\u6bb5\u6811\u5957\u7ebf\u6bb5\u6811\uff0c\u7ebf\u6bb5\u6811\u5957\u5e73\u8861\u6811\u7b49\u7b49\u3002\u6211\u4eec\u8fd9\u91cc\u5148\u53ea\u8ba8\u8bba\u6811\u72b6\u6570\u7ec4\u5957\u7ebf\u6bb5\u6811\u3002<\/p>\n
\u8be5\u6570\u636e\u7ed3\u6784\u5b9e\u73b0\u5728\u4e3b\u5e2d\u6811\u57fa\u7840\u4e0a\u3002<\/p>\n
\u6240\u8c13\u6811\u5957\u6811\uff0c\u5c31\u662f\u4e00\u9897\u6811\u4e0a\u9762\u7684\u6bcf\u4e00\u4e2a\u70b9\uff0c\u4e0d\u4ec5\u8868\u793a\u4e00\u4e2a\u533a\u95f4\u4fe1\u606f\uff0c\u8fd8\u662f\u4e00\u4e2a\u6811\uff0cemmm\u53ef\u89c1\u6700\u5916\u9762\u8fd9\u68f5\u6811\u6709\u591a\u5927\uff0c\u5f53\u7136\u7a7a\u95f4\u4f1a\u70b8\uff0c\u4f46\u662f\u6ce8\u610f\u5230\u6811\u4e0a\u9762\u7684\u7ed3\u70b9\u5927\u90e8\u5206\u90fd\u662f\u7a7a\u7ed3\u70b9\uff0c\u6240\u4ee5\u53ef\u4ee5\u7701\u6389\u5927\u91cf\u7a7a\u95f4\u3002\u4e00\u822c\u6765\u8bf4\uff0c\u6700\u5916\u9762\u90a3\u68f5\u6811\u662f\u533a\u95f4\u7ebf\u6bb5\u6811\uff0c\u5bf9\u5e94\u7684\u662f\u539f\u5e8f\u5217\u4e2d\u7684\u533a\u95f4\u3002\u91cc\u9762\u7684\u6811\u662f\u6743\u503c\u7ebf\u6bb5\u6811\uff0c\u5bf9\u5e94\u7684\u662f\u5916\u9762\u90a3\u68f5\u6811\u6240\u8868\u793a\u7684\u533a\u95f4\u5185\u6240\u6709\u5143\u7d20\u7684\u503c\uff0c\u6240\u7ec4\u6210\u7684\u4e00\u9897\u6811\u3002<\/p>\n
\u5927\u6982\u5c31\u662f\u8fd9\u4e2a\u6837\u5b50\uff0c\u5269\u4e0b\u7684\u51e0\u79cd\u6811\u5957\u6811\u4e5f\u90fd\u662f\u8fd9\u4e2a\u5f62\u5f0f\u3002<\/p>\n
\u90a3\u4e48\u6811\u72b6\u6570\u7ec4\u5957\u7ebf\u6bb5\u6811\uff0c\u5c31\u662f\uff0c\u6811\u72b6\u6570\u7ec4\u4e0a\u7684\u6bcf\u4e2a\u70b9\uff0c\u8868\u793a\u7684\u533a\u95f4\u662f[i-lowbit(i)+1, i]\uff0c\u540c\u65f6\u8fd8\u662f\u4e00\u4e2a\u6743\u503c\u7ebf\u6bb5\u6811\uff0c\u8fd9\u9897\u6743\u503c\u7ebf\u6bb5\u6811\u662f\u5efa\u7acb\u5728\u539f\u5e8f\u5217[i-lowbit(i)+1, i]\u533a\u95f4\u4e0a\u7684\u3002<\/p>\n
\u6811\u5957\u6811\u7684\u601d\u60f3\u90e8\u5206\u5c31\u8fd9\uff0c\u63a5\u4e0b\u6765\u770b\u5b9e\u73b0\u3002<\/p>\n
\u6211\u4eec\u5728\u89e3\u51b3\u9759\u6001\u533a\u95f4\u7b2ck\u5927\/\u5c0f\u65f6\uff0c\u53ea\u9700\u7ef4\u62a4\u524d\u7f00\u548c\u7ebf\u6bb5\u6811\uff0c\u7136\u540e\u4e24\u4e2a\u7ebf\u6bb5\u6811\u76f8\u51cf\u53ef\u4ee5\u5f97\u5230\u4efb\u4e00\u533a\u95f4\u5185\u5143\u7d20\u7ec4\u6210\u7684\u6743\u503c\u7ebf\u6bb5\u6811\uff0c\u8fd9\u6837\u53ef\u4ee5\u5f88\u5bb9\u6613\u6c42\u5f97\u7b2ck\u5927\uff0c\u65f6\u7a7a\u590d\u6742\u5ea6\u5747\u4e3aO(nlogn)\uff0c\u4f46\u662f\u5f53\u9898\u76ee\u8981\u6c42\u8981\u66f4\u6539\u67d0\u4e9b\u5143\u7d20\u503c\u65f6\uff0c\u5c31\u6ca1\u8f99\u4e86\u3002\u3002\u4e5f\u5c31\u662f\u52a8\u6001\u533a\u95f4\u7b2ck\u5927\/\u5c0f\uff0c\u8fd9\u4e2a\u65f6\u5019\u9700\u8981\u7528\u5230\u6811\u5957\u6811\uff0c\u90a3\u4e48\u9700\u8981\u66f4\u6539\u5143\u7d20\u503c\u65f6\uff0c\u53ea\u9700\u66f4\u6539logn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811(\u8ddf\u666e\u901a\u6811\u72b6\u6570\u7ec4\u66f4\u6539\u5355\u70b9\u503c\u4e00\u6837)\uff0c\u7136\u540e\u6bcf\u9897\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u66f4\u6539\u65f6\u95f4\u590d\u6742\u5ea6\u4e5f\u4e3alogn\uff0c\u52a0\u8d77\u6765\u5c31\u662f \u6811\u7684\u53d8\u91cf\u5b9a\u4e49\uff1a<\/p>\n \u7528\u5230\u7684\u6700\u591a\u7684\u51fd\u6570\uff1a<\/p>\n \u5728\u4ee3\u7801\u4e2d\u6709\u4e24\u884c\u662f\u7528\u6765\u8282\u7ea6\u5927\u91cf\u7a7a\u95f4\u7684\uff0c\u5f53\u4f7f\u7528\u9759\u6001\u4e3b\u5e2d\u6811\u65f6\uff0c\u76f4\u63a5++top\u3002<\/p>\n \u5728\u9759\u6001\u4e3b\u5e2d\u6811\u4e2d\uff0c\u6bcf\u9897\u6743\u503c\u7ebf\u6bb5\u6811\u90fd\u662f\u5728\u524d\u4e00\u68f5\u6811\u7684\u57fa\u7840\u4e0a\u66f4\u6539\u503c\uff0c\u5373\u7ebf\u6bb5\u6811\u4e2d\u7684\u7ed3\u70b9\u53ef\u80fd\u662f\u88ab\u591a\u9897\u6811\u6240\u5171\u7528\u7684\uff0c\u4e0d\u53ef\u968f\u610f\u66f4\u6539\u3002\u800c\u5728\u52a8\u6001\u4e3b\u5e2d\u6811\u4e2d\uff0c\u6bcf\u9897\u6743\u503c\u7ebf\u6bb5\u6811\u662f\u5728\u5b83\u7684\u4e0a\u4e00\u4e2a\u7248\u672c\u7684\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u57fa\u7840\u4e0a\u8fdb\u884c\u4fee\u6539\u7684\uff0c\u6811\u91cc\u9762\u7684\u7ed3\u70b9(\u9664\u4e86\u7a7a\u7ed3\u70b9)\u5c31\u5b83\u8fd9\u4e00\u4e2a\u70b9\u5728\u4f7f\u7528\uff0c\u56e0\u6b64\u5f53\u8981\u4fee\u6539\u7684\u7ed3\u70b9\u4e0d\u662f\u7a7a\u7ed3\u70b9\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u5728\u8be5\u6e90\u7ed3\u70b9\u4e0a\u8fdb\u884c\u4fee\u6539\uff0c\u4e0d\u9700\u8981\u987e\u5fcc\u5176\u5b83\u56e0\u7d20\u3002<\/p>\n \u6ca1\u5565\u597d\u8bf4\u7684\u3002\u3002\u5728\u4e0b\u6807i\u51fa\u628a\u6743\u503c\u7ebf\u6bb5\u6811\u4e2dk\u7684\u503c\u589e\u52a0flag\uff0c\u5171\u66f4\u65b0logn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811\u3002<\/p>\n \u7531\u4e8e\u662flogn\u68f5\u7ebf\u6bb5\u6811\u76f8\u51cf\uff0c\u6ca1\u529e\u6cd5\u9012\u5f52\uff0c\u6240\u4ee5\u4f7f\u7528\u8fed\u4ee3\u3002\u8868\u793a[1, l-1]\u7684logn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u6811\u6839\u4eec\u653e\u5728q1[maxn]\u91cc\uff0c\u5171\u6709len1\u68f5\uff1b\u8868\u793a[1, r]\u7684logn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811\u7684\u6811\u6839\u4eec\u653e\u5728q2[maxn]\u91cc\uff0c\u5171\u6709len2\u68f5\u3002<\/p>\n \u9898\u76ee<\/p>\n \u52a8\u6001\u533a\u95f4\u7b2ck\u5c0f\uff0c\uff0c\uff0c\u4ee5\u540e\u79bb\u6563\u5316\u76f4\u63a5unordered_map\u6bd4\u8f83\u597d\u3002\u3002\u3002<\/p>\n \u6bcf\u6b21\u53bb\u6389\u4e00\u4e2a\u70b9\uff0c\u6c42\u6bcf\u6b21\u66f4\u6539\u524d\u7684\u9006\u5e8f\u5bf9\u6570\u3002 \u6bd4\u8f83\u6076\u5fc3\u7684\u4e00\u9898\uff0c\uff0c\u56e0\u4e3a\u8be2\u95ee\u7684\u64cd\u4f5c\u79cd\u7c7b\u6bd4\u8f83\u591a\uff0c\u4ee3\u7801\u957f \u7c7b\u4f3c\u4e8e\u52a8\u6001\u9006\u5e8f\u5bf9<\/p>\n \u6811\u5957\u6811 \u6811\u5957\u6811\u6709\u5f88\u591a\u79cd\uff0c\u53ef\u4ee5\u662f\u6811\u72b6\u6570\u7ec4\u5957\u7ebf\u6bb5\u6811\uff0c\u4e5f\u53ef\u4ee5\u662f\u7ebf\u6bb5\u6811\u5957\u7ebf\u6bb5\u6811\uff0c\u7ebf\u6bb5\u6811\u5957\u5e73\u8861\u6811\u7b49\u7b49\u3002\u6211\u4eec\u8fd9\u91cc […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[14],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/845"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=845"}],"version-history":[{"count":9,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/845\/revisions"}],"predecessor-version":[{"id":854,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/845\/revisions\/854"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=845"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=845"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=845"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}O(log^2n)<\/code>\uff1b\u67e5\u8be2\u7684\u65f6\u5019\uff0c\u60f3\u8981\u8868\u793a\u51fa\u67d0\u4e2a\u533a\u95f4\uff0c\u5176\u5b9e\u5c31\u662flogn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811\u51cf\u53bb\u53e6\u5916logn\u68f5\u6743\u503c\u7ebf\u6bb5\u6811(\u8ddf\u666e\u901a\u6811\u72b6\u6570\u7ec4\u67e5\u8be2\u4e00\u6837)\uff0c\u6bd4\u5982\u8981\u67e5\u8be2[l, r]\uff0c[1, r]\u53ef\u4ee5\u6709logn\u68f5\u6811\u8868\u793a\uff0c[1, l-1]\u4e5f\u53ef\u4ee5\u7531logn\u68f5\u6811\u8868\u793a\uff0c\u4e24\u4e2a\u76f8\u51cf\u5c31\u5f97\u5230[l, r]\u7684\u6743\u503c\u7ebf\u6bb5\u6811\u4e86\u3002<\/p>\nstruct tree{\n int left, right, w; \/\/\u5de6\u53f3\u5b69\u5b50\u548c\u7ed3\u70b9\u6743\u503c \u533a\u95f4\u4fe1\u606f\u5728\u9012\u5f52\u51fd\u6570\u4e2d\u7ed9\u51fa\n}tree[maxn*200]; \/\/\u6570\u636e\u6c60\nint root[maxn]; \/\/\u6811\u72b6\u6570\u7ec4\u6bcf\u4e2a\u7ed3\u70b9\u5728\u6570\u636e\u6c60\u4e2d\u7684\u4e0b\u6807\nint top; \/\/\u6570\u636e\u6c60\u4f7f\u7528\u60c5\u51b5\n\nint len1, len2, q1[100], q2[100];<\/code><\/pre>\nadd\u51fd\u6570\uff1a\u5728\u67d0\u4e2a\u7ed3\u70b9\u6240\u8868\u793a\u7684\u5b50\u6811\u4e0a\u66f4\u65b0\u67d0\u4e2a\u70b9\u7684\u503c\u3002<\/h5>\n
\/\/l,r\u8868\u793a\u533a\u95f4\u4fe1\u606f\uff0cx\u8868\u793a\u6e90\u7ed3\u70b9\uff0ck\u8868\u793a\u8981\u66f4\u6539\u7684\u6743\u503c\u70b9\uff0cflag\u8868\u793a\u8be5\u70b9\u51fa\u6743\u503c+1\u8fd8\u662f-1\ninline int add(int x, int l, int r, int k, int flag) {\n int tmp; \/\/\u65b0\u7ed3\u70b9\u4e3atmp\n if (x) tmp = x; \/\/\u8fd9\u4e24\u884c\u4ee3\u7801\u81f3\u5173\u91cd\u8981\uff0c\u4e0b\u9762\u4f1a\u8bb2\n else tmp = ++top;\n if (l == r) {\n tree[tmp].w = tree[x].w + flag;\n return tmp;\n }\n int mid = (l + r) >> 1;\n if (k <= mid) { \/\/k\u5728\u5de6\u533a\u95f4\u65f6\uff0c\u6e90\u8282\u70b9\u7684\u53f3\u533a\u95f4\u76f4\u63a5\u8d4b\u7ed9tmp\u5373\u53ef\uff0c\u7136\u540e\u8fdb\u4e00\u6b65\u4fee\u6539\u5de6\u533a\u95f4\n tree[tmp].left = add(tree[x].left, l, mid, k, flag);\n tree[tmp].right = tree[x].right;\n } else {\n tree[tmp].left = tree[x].left;\n tree[tmp].right = add(tree[x].right, mid + 1, r, k, flag);\n }\n tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;\n return tmp;\n}\n<\/code><\/pre>\nif (x) tmp = x;\nelse tmp = ++top;<\/code><\/pre>\nupdate\u51fd\u6570\uff1a\u66f4\u6539\u5355\u70b9\u503c<\/h5>\n
inline void update(int i, int k, int flag){\n while (i<=n){\n root[i] = add(root[i], k, flag, 1, cnt);\n i += lowbit(i);\n }\n return;\n}<\/code><\/pre>\n\u67e5\u8be2\u51fd\u6570src: \u56e0\u9898\u800c\u5b9a\u7684\u67e5\u8be2\u64cd\u4f5c<\/h5>\n
inline int src(int x, int y, int k, int l, int r, int flag){ \/\/\u533a\u95f4\u5185\u67e5\u8be2\u6bd4k\u5c0f\u7684\u6570\u7684\u4e2a\u6570\n len1 = len2 = 0;\n int ans = 0;\n x--; \/\/\u8fd9\u91ccx\uff0cy\u8868\u793a\u8981\u6c42[x, y]\u533a\u95f4\u7684\u4fe1\u606f\n while (x){\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y){\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int mid;\n while (l<r){\n mid = (l+r)>>1;\n x = y = 0; \/\/\u8fd9\u91ccx\uff0cy\u8868\u793a\u6240\u6c42\u533a\u95f4\u5185\u5de6\u53f3\u5b69\u5b50\u5404\u81ea\u7684\u6743\u503c\n for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w, y += tree[tree[q2[i]].right].w;\n for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w, y -= tree[tree[q1[i]].right].w;\n if (flag==2)\n if (k<=mid){\n r = mid;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }else{\n l = mid+1, ans += x;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }\n else\n if (k<=mid){\n r = mid, ans += y;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }else{\n l = mid+1;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }\n }\n return ans;\n}<\/code><\/pre>\nP2617 Dynamic Rankings<\/a><\/h4>\n
#include <bits\/stdc++.h>\n\nusing namespace std;\nconst int maxn = 1e5+5;\nint n, m, cnt;\nint nums[maxn];\n\/\/mp12\u5206\u522b\u8868\u793a\u539f\u6570\u7ec4\u548c\u8be2\u95ee\u4e2d\u6570\u503c\u5bf9\u5e94\u7684\u7f16\u53f7,,,mp4\u8868\u793a\u79bb\u6563\u5316\u503c\u5bf9\u5e94\u7684\u539f\u6570 \u539f\u6570->\u7f16\u53f7->\u79bb\u6563\u5316\u503c->\u539f\u6570 12->3->4\nint mp1[maxn], mp2[maxn], mp3[maxn*2], mp4[maxn*2];\nint se[maxn];\nstruct z{\n int w, idx; \/\/w\u8868\u793a\u539f\u6765\u7684\u503c\uff0c v\u8868\u793a\u79bb\u6563\u5316\u540e\u7684\u503c\n}disc[maxn*2];\nstruct y{\n int opt, l, r, k;\n}query[maxn];\n\nstruct tree{\n int left, right, w;\n}tree[maxn*400];\nint top, root[maxn];\nqueue<int> q1, q2;\ninline int lowbit(int i){return i&(-i);}\ninline int add(int x, int k, int flag, int l, int r){ \/\/\u7ed9\u7ed3\u70b9x\u6240\u8868\u793a\u7684\u7ebf\u6bb5\u6811\u52a0\u4e0a\u6743\u503ck\uff0cflag=1\u8868\u793a\u52a0\uff0c-1\u8868\u793a\u51cf\n int tmp;\n if (x) tmp = x;\n else tmp = ++top;\n if (l==r){\n tree[tmp].w = flag + tree[x].w;\n return tmp;\n }\n int mid = (l+r)>>1;\n if (k<=mid){\n tree[tmp].left = add(tree[x].left, k, flag, l, mid);\n tree[tmp].right = tree[x].right;\n }else{\n tree[tmp].left = tree[x].left;\n tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);\n }\n tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;\n return tmp;\n}\n\ninline void update(int i, int k, int flag){\n while (i<=n){\n root[i] = add(root[i], k, flag, 1, cnt);\n i += lowbit(i);\n }\n return;\n}\ninline int src(int x, int y, int l, int r, int k){ \/\/\u533a\u95f4[x+1, y]\u5185\u7b2ck\u5c0f\n while (!q1.empty()) q1.pop();\n while (!q2.empty()) q2.pop();\n while (x){\n q1.push(root[x]);\n x -= lowbit(x);\n }\n while (y){\n q2.push(root[y]);\n y -= lowbit(y);\n }\n int mid, left, len1, len2, tmp;\n while (l<r){\n mid = (l+r) >> 1;\n left = x = 0;\n len1 = q1.size(),len2 = q2.size();\n while (len2--){\n tmp = q2.front(); q2.pop();\n x += tree[tree[tmp].left].w;\n q2.push(tmp);\n }\n while (len1--){\n tmp = q1.front(); q1.pop();\n x -= tree[tree[tmp].left].w;\n q1.push(tmp);\n }\n if (k <= x){\n r = mid;\n len1 = q1.size(),len2 = q2.size();\n while (len2--){\n tmp = q2.front(); q2.pop();\n q2.push(tree[tmp].left);\n }\n while (len1--){\n tmp = q1.front(); q1.pop();\n q1.push(tree[tmp].left);\n }\n }else{\n l = mid+1, k -= x;\n len1 = q1.size(),len2 = q2.size();\n while (len2--){\n tmp = q2.front(); q2.pop();\n q2.push(tree[tmp].right);\n }\n while (len1--){\n tmp = q1.front(); q1.pop();\n q1.push(tree[tmp].right);\n }\n }\n }\n return l;\n}\n\ninline int read(){\n int x=0; char ch=getchar();\n while (ch<'0' || ch>'9') ch=getchar();\n while (ch>='0' && ch<='9'){\n x = x*10 + ch-'0';\n ch=getchar();\n }\n return x;\n}\ninline char cread(){\n char ch=getchar();\n while (!isalpha(ch)) ch=getchar();\n return ch;\n}\ninline bool cmp1(struct z a, struct z b){\n return a.w < b.w;\n}\nint main(){\n n = read(), m = read();\n for (int i=1; i<=n; i++) nums[i] = read();\n for (int i=1; i<=m; i++){\n if (cread()=='Q'){\n query[i].opt = 1;\n query[i].l = read(), query[i].r = read(), query[i].k = read();\n }else{\n query[i].opt = 2;\n query[i].l = read(), query[i].r = read();\n }\n }\n for (int i=1; i<=n; i++) disc[i].w = nums[i], mp1[i] = i, disc[i].idx = i;\n cnt = n;\n for (int i=1; i<=m; i++) if (query[i].opt==2){\n cnt++;\n disc[cnt].w = query[i].r, mp2[i] = cnt, disc[cnt].idx = cnt;\n }\n sort (disc+1, disc+cnt+1, cmp1);\n for (int i=1; i<=cnt; i++){\n mp3[disc[i].idx] = i;\n mp4[i] = disc[i].w;\n }\n top = 0;\n for (int i=1; i<=n; i++) se[i] = i;\n for (int i=1; i<=n; i++){\n update(i, mp3[se[i]], 1);\n }\n for (int i=1; i<=m; i++){\n if (query[i].opt==2){\n update(query[i].l, mp3[se[query[i].l]], -1);\n se[query[i].l] = mp2[i];\n update(query[i].l, mp3[se[query[i].l]], 1);\n }else{\n int ans = src(query[i].l-1, query[i].r, 1, cnt, query[i].k);\n printf ("%d\\n", mp4[ans]);\n }\n }\n return 0;\n}<\/code><\/pre>\nP3157 \u52a8\u6001\u9006\u5e8f\u5bf9<\/a><\/h4>\n
\n\u5148\u6c42\u5f97\u539f\u59cb\u5e8f\u5217\u7684\u9006\u5e8f\u5bf9\u6570ans\uff0c\u7136\u540e\u53bb\u6389\u4e00\u4e2a\u5143\u7d20\u65f6\uff0c\u5269\u4e0b\u7684\u9006\u5e8f\u5bf9\u6570\u662fans-\u524d\u9762\u6bd4\u8be5\u5143\u7d20\u5c0f\u7684\u4e2a\u6570-\u540e\u9762\u6bd4\u8be5\u5143\u7d20\u5927\u7684\u4e2a\u6570\u3002\u7136\u540e\u6ce8\u610f\u66f4\u65b0\u3002<\/p>\n#include <bits\/stdc++.h>\n\nusing namespace std;\n\nconst int maxn = 1e5+5;\ntypedef long long ll;\nint n, m;\nint nums[maxn], mp[maxn];\nll c[maxn], ans;\n\nstruct tree{\n int left, right, w;\n}tree[maxn*150];\nint root[maxn], top;\nint len1, len2, q1[maxn], q2[maxn];\n\ninline int lowbit(int i){\n return i & -i;\n}\ninline void update_(int i, int k){\n while (i<=n){\n c[i] += k;\n i += lowbit(i);\n }\n return;\n}\ninline ll sum_(int i){\n ll ans = 0;\n while (i){\n ans += c[i];\n i -= lowbit(i);\n }\n return ans;\n}\ninline int add(int x, int k, int flag, int l, int r){ \/\/\n int tmp;\n if (x) tmp = x;\n else tmp = ++top;\n if (l==r){\n tree[tmp].w = tree[x].w + flag;\n return tmp;\n }\n int mid = (l+r)>>1;\n if (k<=mid){\n tree[tmp].left = add(tree[x].left, k, flag, l, mid);\n tree[tmp].right = tree[x].right;\n }else{\n tree[tmp].left = tree[x].left;\n tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);\n }\n tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;\n return tmp;\n}\ninline void update(int i, int k, int flag){\n while (i<=n){\n root[i] = add(root[i], k, flag, 1, n);\n i += lowbit(i);\n }\n return;\n}\ninline int src(int x, int y, int k, int l, int r, int flag){ \/\/\u533a\u95f4\u5185\u67e5\u8be2\u6bd4k\u5c0f\u7684\u6570\u7684\u4e2a\u6570\n len1 = len2 = 0;\n int ans = 0;\n x--;\n while (x){\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y){\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int mid;\n while (l<r){\n mid = (l+r)>>1;\n x = y = 0;\n for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w, y += tree[tree[q2[i]].right].w;\n for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w, y -= tree[tree[q1[i]].right].w;\n if (flag==2)\n if (k<=mid){\n r = mid;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }else{\n l = mid+1, ans += x;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }\n else\n if (k<=mid){\n r = mid, ans += y;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }else{\n l = mid+1;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }\n }\n return ans;\n}\nint main(){\n int x;\n ans = top = 0;\n scanf ("%d %d", &n, &m);\n for (int i=1; i<=n; i++){\n scanf ("%d", nums+i);\n mp[nums[i]] = i;\n update(i, nums[i], 1);\n update_(nums[i], 1);\n ans += sum_(n) - sum_(nums[i]);\n }\n for (int i=1; i<=m; i++){\n scanf ("%d", &x);\n printf ("%lld\\n", ans);\n ans -= src(1, mp[x], x, 1, n, 1) + src(mp[x], n, x, 1, n, 2);\n update(mp[x], x, -1);\n }\n return 0;\n}\n\/*\n1 5 3 4 2\n*\/<\/code><\/pre>\nP3380 \u3010\u6a21\u677f\u3011\u4e8c\u903c\u5e73\u8861\u6811\uff08\u6811\u5957\u6811\uff09<\/a><\/h4>\n
\n\u8fd9\u91cc\u6211\u5728\u6c42\u524d\u9a71\u540e\u7ee7\u65f6\uff0c\u5148\u67e5\u8be2k\u7684\u6392\u540dx\uff0c\u7136\u540e\u8f93\u51fa\u6392\u540dx-1\u548cx+1\u7684\u6570\u3002<\/p>\n\/*\u6811\u72b6\u6570\u7ec4\u5957\u4e3b\u5e2d\u6811*\/\n\n#include <bits\/stdc++.h>\n\nusing namespace std;\nconst int maxn = 50005;\n\nint n, m;\nint nums[maxn], se[maxn*2], cnt; \/\/cnt\u662f\u79bb\u6563\u540e\u7684\u6700\u5927\u7f16\u53f7\nstruct opt{\n int opt;\n int l, r, k;\n int pos;\n}query[maxn];\nunordered_map<int, int> mp1, mp2; \/\/mp1: \u539f\u6570\u503c->\u79bb\u6563\u503c mp2:\u79bb\u6563\u503c->\u539f\u6570\u503c\n\nstruct tree{\n int left, right, w;\n}tree[maxn*250];\nint root[maxn], top;\nint len1, len2, q1[maxn], q2[maxn];\n\nint lowbit(int i){\n return i & -i;\n}\nint add(int x, int k, int flag, int l, int r){\n int tmp = ++top;\n if (l==r){\n tree[tmp].w = tree[x].w + flag;\n return tmp;\n }\n int mid = (l+r) >> 1;\n if (k <= mid){\n tree[tmp].left = add(tree[x].left, k, flag, l, mid);\n tree[tmp].right = tree[x].right;\n }else{\n tree[tmp].left = tree[x].left;\n tree[tmp].right = add(tree[x].right, k, flag, mid+1, r);\n }\n tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;\n return tmp;\n}\nvoid update(int i, int k, int flag){\n while (i<=n){\n root[i] = add(root[i], k, flag, 1, cnt);\n i += lowbit(i);\n }\n return;\n}\nint src1(int x, int y, int k){ \/\/\u533a\u95f4[x, y]\u5185\uff0ck\u6392\u7b2c\u51e0\n len1 = len2 = 0, x -= 1;\n while (x){\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y){\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int l = 1, r = cnt, mid, ans = 0;\n while (l<r){\n mid = (l+r) >> 1, x = y = 0;\n for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w;\n for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w;\n if (k>mid){\n ans += x, l = mid+1;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }else{\n r = mid;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }\n }\n return ans+1;\n}\nint src2(int x, int y, int k){ \/\/\u533a\u95f4[x, y]\u5185\uff0c\u6392\u7b2ck\u7684\u6570\n len1 = len2 = 0, x -= 1;\n while (x){\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y){\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int l = 1, r = cnt, mid;\n while (l<r){\n mid = (l+r) >> 1, x = y = 0;\n for (int i=1; i<=len2; i++) x += tree[tree[q2[i]].left].w;\n for (int i=1; i<=len1; i++) x -= tree[tree[q1[i]].left].w;\n if (k>x){\n k -= x, l = mid+1;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }else{\n r = mid;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }\n }\n return l;\n}\nint src5(int x, int y, int k){ \/\/\u533a\u95f4[x, y]\u5185\uff0ck\u7684\u540e\u7ee7\n int tmp = src1(x, y, k);\n int tmpx = x, tmpy = y;\n len1 = len2 = 0, x -= 1;\n while (x){\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y){\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int l = 1, r = cnt, mid, ans = 0, tot = 0; \/\/\u8fd9\u4e2aans\u8868\u793a\u7684\u662fk\u7684\u4e2a\u6570\n for (int i=1; i<=len2; i++) tot += tree[q2[i]].w;\n for (int i=1; i<=len1; i++) tot -= tree[q1[i]].w;\n while (l<r){\n mid = (l+r) >> 1;\n if (k>mid){\n l = mid+1;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].right;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].right;\n }else{\n r = mid;\n for (int i=1; i<=len2; i++) q2[i] = tree[q2[i]].left;\n for (int i=1; i<=len1; i++) q1[i] = tree[q1[i]].left;\n }\n }\n for (int i=1; i<=len2; i++) ans += tree[q2[i]].w;\n for (int i=1; i<=len1; i++) ans -= tree[q1[i]].w;\n if (ans+tmp > tot) return -1;\n return src2(tmpx, tmpy, ans + tmp);\n}\nint main(){\n scanf ("%d %d", &n, &m);\n for (int i=1; i<=n; i++) scanf ("%d", nums+i);\n for (int i=1; i<=n; i++) se[i] = nums[i];\n cnt = n;\n for (int i=1; i<=m; i++){\n scanf ("%d", &query[i].opt);\n if (query[i].opt==3) scanf ("%d %d", &query[i].pos, &query[i].k);\n else scanf ("%d %d %d", &query[i].l, &query[i].r, &query[i].k);\n \/\/if (query[i].opt>=3) \n se[++cnt] = query[i].k;\n }\n sort (se+1, se+cnt+1);\n mp1[se[1]] = 1, mp2[1] = se[1];\n for (int i=2; i<=cnt; i++) if (se[i]!=se[i-1]){\n mp1[se[i]] = mp1[se[i-1]]+1;\n mp2[mp1[se[i]]] = se[i];\n }\n cnt = mp1.size(), top = 0;\n for (int i=1; i<=n; i++) update(i, mp1[nums[i]], 1);\n mp2[-1] = 2147483647;\n for (int i=1; i<=m; i++){\n if (query[i].opt==3){\n update(query[i].pos, mp1[nums[query[i].pos]], -1);\n nums[query[i].pos] = query[i].k;\n update(query[i].pos, mp1[nums[query[i].pos]], 1);\n continue;\n }else if (query[i].opt==1){\n printf ("%d\\n", src1(query[i].l, query[i].r, mp1[query[i].k]));\n continue;\n }else if (query[i].opt==2){\n printf ("%d\\n", mp2[src2(query[i].l, query[i].r, query[i].k)]);\n continue;\n }else if (query[i].opt==4){\n \/\/src4(query[i].l, query[i].r, mp1[query[i].k]);\n int tmp = src1(query[i].l, query[i].r, mp1[query[i].k]);\n if (tmp==1) puts("-2147483647");\n else printf ("%d\\n", mp2[src2(query[i].l, query[i].r, tmp-1)]);\n continue;\n }else{\n printf ("%d\\n", mp2[src5(query[i].l, query[i].r, mp1[query[i].k])]);\n }\n }\n return 0;\n}<\/code><\/pre>\nP3759 [TJOI2017]\u4e0d\u52e4\u52b3\u7684\u56fe\u4e66\u7ba1\u7406\u5458<\/a><\/h4>\n
#include <bits\/stdc++.h>\n\nusing namespace std;\ntypedef long long ll;\nconst ll maxn = 50005, mod = 1e9 + 7;\n\nint n, m;\nint nums[maxn], nums1[maxn];\n\nstruct tree {\n int left, right;\n short int w;\n int sum;\n} tree[maxn * 200];\nint root[maxn], top;\n\nint len1, len2, q1[maxn], q2[maxn];\n\ninline int lowbit(int i) { return i & -i; }\ninline int add(int x, int l, int r, int k, int flag) {\n int tmp;\n if (x)\n tmp = x;\n else\n tmp = ++top;\n if (l == r) {\n tree[tmp].w = tree[x].w + flag;\n tree[tmp].sum = tree[tmp].w * nums[k];\n return tmp;\n }\n int mid = (l + r) >> 1;\n if (k <= mid) {\n tree[tmp].left = add(tree[x].left, l, mid, k, flag);\n tree[tmp].right = tree[x].right;\n } else {\n tree[tmp].left = tree[x].left;\n tree[tmp].right = add(tree[x].right, mid + 1, r, k, flag);\n }\n tree[tmp].w = tree[tree[tmp].left].w + tree[tree[tmp].right].w;\n tree[tmp].sum = (tree[tree[tmp].left].sum + tree[tree[tmp].right].sum) % mod;\n return tmp;\n}\ninline void update(int i, int k, int flag) {\n while (i <= n) {\n root[i] = add(root[i], 1, n, k, flag);\n i += lowbit(i);\n }\n return;\n}\n\ninline void src(int x, int y, int k, int flag, ll &t, ll &ans) { \/\/ t\u8868\u793a\u4e2a\u6570,, ans\u8868\u793a\u503c 1\u5927\u4e8e 0\u5c0f\u4e8e\n t = ans = 0;\n if (x > y)\n return;\n len1 = len2 = 0;\n x--;\n while (x) {\n q1[++len1] = root[x];\n x -= lowbit(x);\n }\n while (y) {\n q2[++len2] = root[y];\n y -= lowbit(y);\n }\n int l = 1, r = n, mid;\n ll left1, left2, right1, right2;\n while (l < r) {\n left1 = left2 = right1 = right2 = 0;\n for (int i = 1; i <= len1; i++) left1 -= tree[tree[q1[i]].left].w;\n for (int i = 1; i <= len2; i++) left1 += tree[tree[q2[i]].left].w;\n for (int i = 1; i <= len1; i++) left2 -= tree[tree[q1[i]].left].sum;\n for (int i = 1; i <= len2; i++) left2 += tree[tree[q2[i]].left].sum;\n for (int i = 1; i <= len1; i++) right1 -= tree[tree[q1[i]].right].w;\n for (int i = 1; i <= len2; i++) right1 += tree[tree[q2[i]].right].w;\n for (int i = 1; i <= len1; i++) right2 -= tree[tree[q1[i]].right].sum;\n for (int i = 1; i <= len2; i++) right2 += tree[tree[q2[i]].right].sum;\n mid = (l + r) >> 1;\n if (flag) {\n if (k <= mid) {\n t += right1, ans += right2, r = mid;\n for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].left;\n for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].left;\n } else {\n l = mid + 1;\n for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].right;\n for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].right;\n }\n } else {\n if (k > mid) {\n t += left1, ans += left2, l = mid + 1;\n for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].right;\n for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].right;\n } else {\n r = mid;\n for (int i = 1; i <= len1; i++) q1[i] = tree[q1[i]].left;\n for (int i = 1; i <= len2; i++) q2[i] = tree[q2[i]].left;\n }\n }\n }\n return;\n}\ninline int read() {\n int x = 0;\n char ch = getchar();\n while (ch < '0' || ch > '9') ch = getchar();\n while (ch >= '0' && ch <= '9') {\n x = x * 10 + ch - '0';\n ch = getchar();\n }\n return x;\n}\n\nint main() {\n int tmp, x, y;\n ll now = 0, t, ans;\n top = 0;\n \/\/ scanf ("%d %d", &n, &m);\n n = read(), m = read();\n for (int i = 1; i <= n; i++) {\n \/\/ scanf ("%d", &nums1[i]);\n \/\/ scanf ("%d", &nums[nums1[i]]);\n nums1[i] = read();\n nums[nums1[i]] = read();\n }\n for (int i = 1; i <= n; i++) {\n src(1, i - 1, nums1[i], 1, t, ans);\n now += ans + t * nums[nums1[i]];\n now %= mod;\n update(i, nums1[i], 1);\n }\n for (int i = 1; i <= m; i++) {\n \/\/ scanf ("%d %d", &x, &y);\n x = read(), y = read();\n src(1, x - 1, nums1[x], 1, t, ans);\n now -= ans + t * nums[nums1[x]];\n src(x + 1, n, nums1[x], 0, t, ans);\n now -= ans + t * nums[nums1[x]];\n update(x, nums1[x], -1);\n src(1, y - 1, nums1[y], 1, t, ans);\n now -= ans + t * nums[nums1[y]];\n src(y + 1, n, nums1[y], 0, t, ans);\n now -= ans + t * nums[nums1[y]];\n update(y, nums1[y], -1);\n swap(nums1[x], nums1[y]);\n src(1, x - 1, nums1[x], 1, t, ans);\n now += ans + t * nums[nums1[x]];\n src(x + 1, n, nums1[x], 0, t, ans);\n now += ans + t * nums[nums1[x]];\n update(x, nums1[x], 1);\n src(1, y - 1, nums1[y], 1, t, ans);\n now += ans + t * nums[nums1[y]];\n src(y + 1, n, nums1[y], 0, t, ans);\n now += ans + t * nums[nums1[y]];\n update(y, nums1[y], 1);\n now %= mod;\n now = (now + mod) % mod;\n printf("%lld\\n", now);\n }\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"