{"id":223,"date":"2024-03-10T21:40:23","date_gmt":"2024-03-10T13:40:23","guid":{"rendered":"https:\/\/linxce.ink\/?p=223"},"modified":"2024-03-10T21:40:23","modified_gmt":"2024-03-10T13:40:23","slug":"%e7%8f%82%e6%9c%b5%e8%8e%89%e6%a0%91chtholly","status":"publish","type":"post","link":"https:\/\/linxce.ink\/index.php\/%e7%8f%82%e6%9c%b5%e8%8e%89%e6%a0%91chtholly\/%e5%85%a8%e9%83%a8\/acm\/","title":{"rendered":"\u73c2\u6735\u8389\u6811Chtholly"},"content":{"rendered":"

\u73c2\u6735\u8389\u00b7\u8bfa\u5854\u00b7\u745f\u5c3c\u6b27\u91cc\u65af<\/h3>\n

\u5bf9\u533a\u95f4\u5b9d\u5177\uff0c\u771f\u6b63\u7684\u73c2\u5b66<\/h4>\n

\"\"<\/a><\/p>\n

struct Chtholly \/\/[l, r]\u95ed\u533a\u95f4\n{\n    ll l, r;\n    mutable ll v;\n    Chtholly(ll L, ll R = -1, ll V = 0) : l(L), r(R), v(V) {}\n    bool operator < (const Chtholly &x)const{ return l < x.l; } \/\/\u6309\u5de6\u7aef\u70b9\u6392\u5e8f\n};\nusing It = set<Chtholly>::iterator;\nset<Chtholly>tr;\nIt split(int pos) \/\/\u5206\u5272\u533a\u95f4\n{\n    It it = tr.lower_bound(Chtholly(pos)); \/\/\u627e\u5230\u6240\u9700\u7684pos\u7684\u8fed\u4ee3\u5668\n    if(it != tr.end() && it->l == pos) return it; \/\/\u770b\u770b\u8fd9\u4e2a\u8fed\u4ee3\u5668\u7684l\u662f\u4e0d\u662f\u6240\u9700\u8981\u7684pos\uff0c\u662f\u7684\u8bdd\u76f4\u63a5\u8fd4\u56de\u5c31\u884c\n    --it; \/\/\u4e0d\u662f\u7684\u8bdd\u5c31\u8bf4\u660e\u80af\u5b9a\u662f\u5728\u524d\u4e00\u4e2a\u91cc\u9762\n    ll l = it->l, r = it->r, v = it->v;\n    tr.erase(it);\n    tr.insert(Chtholly(l, pos - 1, v)); \/\/\u62c6\u5206\u6210\u4e24\u4e2a\u533a\u95f4[l, pos),[pos, r] \/\/[pos, r]\u5c31\u662f\u95ed\u533a\u95f4\n    return tr.insert(Chtholly(pos, r, v)).first; \/\/\u8fd4\u56de\u4ee5pos\u5f00\u5934\u7684\u533a\u95f4\u7684\u8fed\u4ee3\u5668\n}\nvoid emerge(int l, int r, ll x) \/\/\u5408\u5e76\u533a\u95f4||\u533a\u95f4\u4fee\u6539\n{\n    It itr = split(r + 1), itl = split(l); \/\/\u5148\u627e\u5230r+1\u7684\u8fed\u4ee3\u5668\u4f4d\u7f6e\uff0c\u518d\u627el\u7684\u8fed\u4ee3\u5668\u4f4d\u7f6e\n    tr.erase(itl, itr); \/\/\u5220\u6389\u8fd9\u4e00\u6bb5\u8fed\u4ee3\u5668\n    tr.insert(Chtholly(l, r, x)); \/\/\u91cd\u65b0\u63d2\u5165\u6240\u9700\u533a\u95f4\n}\nvoid delta(int l, int r, ll x) \/\/\u533a\u95f4\u503c\u52a0\u51cf,O(m),m\u4e3a[l,r]\u5185\u533a\u95f4\u4e2a\u6570\n{\n    It itr = split(r + 1), itl = split(l);\n    for(;itl != itr; ++itl) itl->v += x;\n}\nll query(ll l, ll r, ll pos) \/\/\u5355\u70b9\u67e5\u8be2\n{\n    It it = tr.lower_bound(Chtholly(pos));\n    if(it != tr.end() && it->l == pos) return it.v;\n    return (--it).v;\n}\nll query_k(ll l, ll r, ll k) \/\/\u67e5\u8be2\u533a\u95f4[l, r]\u91cc\u6392\u540d\u4e3ak\u7684\u6570,O(mlogm),m\u4e3a[l,r]\u5185\u533a\u95f4\u4e2a\u6570\n{\n    It itr = split(r + 1), itl = split(l);\n    vector<pair<ll, ll>> tmp;\n    for (; itl != itr; ++itl) tmp.pb(make_pair(itl->v, itl->r - itl->l + 1));\n    sort(tmp.begin(), tmp.end());\n    for (auto it : tmp) if ((k -= it.se) <= 0) return it.fi;\n    return -1; \/\/\u6ca1k\u4e2a\u6570\u8fd4\u56de-1\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u73c2\u6735\u8389\u00b7\u8bfa\u5854\u00b7\u745f\u5c3c\u6b27\u91cc\u65af \u5bf9\u533a\u95f4...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,18,19],"tags":[21,7,17,20],"class_list":["post-223","post","type-post","status-publish","format-standard","hentry","category-acm","category-18","category-19","tag-acm","tag-cpp","tag-17","tag-20"],"_links":{"self":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/comments?post=223"}],"version-history":[{"count":1,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/223\/revisions"}],"predecessor-version":[{"id":225,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/223\/revisions\/225"}],"wp:attachment":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media?parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/categories?post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/tags?post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}