{"id":368,"date":"2023-07-23T20:55:52","date_gmt":"2023-07-23T12:55:52","guid":{"rendered":"https:\/\/www.xgnd.net\/?p=368"},"modified":"2025-11-22T12:42:49","modified_gmt":"2025-11-22T04:42:49","slug":"%e7%8f%82%e6%9c%b5%e8%8e%89%e6%a0%91%ef%bc%88odt%ef%bc%89%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0","status":"publish","type":"post","link":"https:\/\/www.xgnd.net\/index.php\/2023\/07\/23\/%e7%8f%82%e6%9c%b5%e8%8e%89%e6%a0%91%ef%bc%88odt%ef%bc%89%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0\/","title":{"rendered":"\u300c\u5b66\u4e60\u7b14\u8bb0\u300d\u73c2\u6735\u8389\u6811\uff08ODT\uff09"},"content":{"rendered":"

\u7b80\u4ecb<\/h2>\n

\u73c2\u6735\u8389\u6811\uff0c\u53c8\u540d\u8001\u53f8\u673a\u6811\uff08Old Driver Tree\uff09\u3002\u73c2\u6735\u8389\u6811\u8d77\u6e90\u4e8e Codeforces \u7684\u4e00\u573a\u6bd4\u8d5b CF896C<\/a>\u3002<\/p>\n

\n

\u8fd9\u79cd\u60f3\u6cd5\u7684\u672c\u8d28\u662f\u57fa\u4e8e\u6570\u636e\u968f\u673a\u7684\u300c\u989c\u8272\u6bb5\u5747\u644a\u300d\uff0c\u800c\u4e0d\u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\u3002 \u2014\u2014OI Wiki<\/a><\/p>\n<\/blockquote>\n

\u73c2\u6735\u8389\u6811\u672c\u8d28\u4e0a\u5e76\u4e0d\u80fd\u7b97\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u4ec5\u4ec5\u53ea\u80fd\u7b97\u4e00\u79cd\u601d\u60f3\u3002\u5e76\u4e14\u5176\u9002\u7528\u8303\u56f4\u8f83\u4e3a\u6709\u9650\uff0c\u53ea\u80fd\u9002\u7528\u4e8e\u4ee5\u4e0b\u60c5\u51b5\uff1a\u7ef4\u62a4\u4e00\u4e2a\u5e8f\u5217\uff0c\u6570\u636e\u968f\u673a\uff0c\u53ea\u6709\u533a\u95f4\u8d4b\u503c\u64cd\u4f5c\u3002<\/p>\n

\u5728\u6570\u636e\u968f\u673a\u7684\u60c5\u51b5\u4e0b\u4e00\u822c\u6548\u7387\u8f83\u9ad8\uff0c\u4f46\u6570\u636e\u4e0d\u968f\u673a\u65f6\uff0c\u5c31\u5bb9\u6613\u88ab\u5361\u3002\u5728\u53ea\u6709\u533a\u95f4\u8d4b\u503c\u64cd\u4f5c\u7684\u6570\u636e\u7ed3\u6784\u9898\u53ef\u4ee5\u62ff\u6765\u9a97\u5206\uff0c\u6570\u636e\u5f31\u4e00\u70b9\u7684\u9898\u751a\u81f3\u80fd AC\u3002<\/p>\n

\u6570\u636e\u968f\u673a\u65f6\uff0c\u7528set\u5b9e\u73b0\u7684\u73c2\u6735\u8389\u6811\u590d\u6742\u5ea6\u4e3a $O(n\\;log\\;log\\;n)$ \uff0c\u800c\u94fe\u8868\u5b9e\u73b0\u7684\u590d\u6742\u5ea6\u4e3a $O(n\\;log\\;n)$ \u3002\uff08\u73c2\u6735\u8389\u6811\u4e25\u683c\u8bc1\u660e\u53ef\u53c2\u8003\u8fd9\u7bc7<\/a>\uff09<\/p>\n

\u539f\u7406\u5176\u5b9e\u5f88\u7b80\u5355\uff0c\u751a\u81f3\u770b\u4ee3\u7801\u90fd\u80fd\u770b\u61c2\uff0c\u8fd9\u91cc\u4e00\u53e5\u8bdd\u5e26\u8fc7\uff1a\u7ef4\u62a4\u82e5\u5e72\u4e2a\u533a\u95f4\uff0c\u5c06\u503c\u76f8\u540c\u7684\u533a\u95f4\u5408\u5e76\u4e3a\u4e00\u4e2a\uff0c\u8fd9\u6837\u533a\u95f4\u603b\u6570\u5c31\u80fd\u51cf\u5c11\u3002<\/p>\n

\u800c\u8fd9\u91cc\u8bb2\u70b9\u4e0d\u4e00\u6837\u7684\uff0c\u672c\u6587\u91cd\u70b9\u4ecb\u7ecd\u4e00\u4e0bmap\u5b9e\u73b0\u7684\u73c2\u6735\u8389\u6811\uff08\u662f\u6211\u7684\u4e00\u4f4d\u5b66\u957f\u6559\u6211\u7684orz\uff09\uff0c\u7528\u7684\u4eba\u76f8\u5bf9\u8f83\u5c11\uff0c\u5176\u4ee3\u7801\u5b9e\u73b0\u76f8\u6bd4set\u5b9e\u73b0\u7684\u4e5f\u66f4\u7b80\u5355\u3002<\/p>\n

\u6b63\u6587<\/h2>\n
struct node{\n    int l,r;\n    mutable ll v;\n    node(int l,int r,ll v): l(l),r(r),v(v){}\n    bool operator&lt;(const node &amp;x)const{return l&lt;x.l;}\n};<\/code><\/pre>\n
\u8fd9\u662fset\u5b9e\u73b0\u7684ODT\u4fdd\u5b58\u8282\u70b9\u7684\u65b9\u5f0f\uff0c\u5b83\u4fdd\u5b58\u4e86\u533a\u95f4\u5de6\u53f3\u7aef\u70b9\u548c\u533a\u95f4\u7684\u503c\uff0c\u4f46\u5b9e\u9645\u4e0a\u533a\u95f4\u53f3\u7aef\u70b9\u662f\u6ca1\u5fc5\u8981\u4fdd\u5b58\u7684\uff0c\u56e0\u4e3a\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u4ece\u4e0b\u4e00\u4e2a\u533a\u95f4\u7684\u5de6\u7aef\u70b9\u63a8\u51fa\u5f53\u524d\u533a\u95f4\u7684\u53f3\u7aef\u70b9\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u80fd\u5c11\u7ef4\u62a4\u4e00\u4e2a\u4fe1\u606f\uff0c\u5c31\u53ef\u4ee5\u76f4\u63a5\u7528\u4e00\u4e2amap\u5b58\u4e86\u3002<\/p>\n
\u540c\u65f6\uff0c\u5728\u5de5\u7a0b\u4e0a\uff0c\u90fd\u4e60\u60ef\u7528\u5de6\u95ed\u53f3\u5f00\u7684\u533a\u95f4\u548c\u4e0b\u6807\u4ece0\u5f00\u59cb\uff0c\u8fd9\u91cc\u501f\u9274\u4e00\u4e0b\uff0c\u8fd9\u6837\u4e0b\u4e00\u4e2a\u533a\u95f4\u7684\u5de6\u7aef\u70b9\u5c31\u6b63\u597d\u5bf9\u5e94\u5f53\u524d\u533a\u95f4\u7684\u53f3\u7aef\u70b9\u4e86\u3002<\/p>\n
\u8981\u6ce8\u610f\u6700\u540e\u4e00\u4e2a\u533a\u95f4\u6ca1\u6709\u540e\u7ee7\uff0c\u4e3a\u4e86\u83b7\u53d6\u6700\u540e\u4e00\u4e2a\u533a\u95f4\u7684\u53f3\u7aef\u70b9\uff0c\u5728map\u7ed3\u5c3e\u63d2\u5165\u4e00\u4e2a $[n,+\\infty)$ \u7684\u533a\u95f4\u5c31\u53ef\u4ee5\u4e86\u3002<\/p>\n
\u8fd9\u6837\u505a\u4e3a\u4ec0\u4e48\u66f4\u597d\u5462\uff1f<\/h4>\n
set\u5b9e\u73b0\u7684 split\uff1a<\/p>\n
auto split(int pos){\n    auto it=lower_bound(s.begin(),s.end(),(node){pos,0,0});\n    if(it!=s.end() and it-&gt;l==pos)\n        return it;\n    it--;\n    if(it-&gt;r&lt;pos)return s.end();\n    int l=it-&gt;l;\n    int r=it-&gt;r;\n    ll v=it-&gt;v;\n    s.erase(it);\n    s.insert(node(l,pos-1,v));\n    return s.insert(node(pos,r,v)).first;\n}<\/code><\/pre>\n
\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5982\u679c\u6211\u4eec\u60f3\u628a\u5143\u7d20\u90fd\u4e00\u6837\u7684\u4e00\u4e2a\u533a\u95f4 $[l,r]$ \u4ece\u4e0b\u6807 $p$ \u5904\u5288\u5f00\uff0c\u6309\u7167\u4e0a\u9762\u7684\u5199\u6cd5\uff0c\u9700\u8981\u5148\u628a\u8fd9\u4e2a\u533a\u95f4\u5220\u6389\uff0c\u518d\u52a0\u5165\u4e24\u4e2a\u503c\u4e00\u6837\u4f46\u8303\u56f4\u5206\u522b\u4e3a $[l,p-1]$ \u548c $[p,r]$ \u7684\u533a\u95f4\uff0c\u539f\u56e0\u662f\u6211\u4eec\u628a\u533a\u95f4\u5288\u5f00\u540e\u8981\u4fee\u6539\u4e24\u4e2a\u533a\u95f4\u7684\u5de6\u53f3\u7aef\u70b9\uff0c\u6709\u70b9\u9ebb\u70e6\uff0c\u8fd9\u4e0d\u597d\u3002<\/p>\n
\u4f46\u5982\u679c\u4e0d\u5b58\u53f3\u7aef\u70b9\uff0c\u5c31\u53ea\u9700\u8981\u5728\u8fd9\u4e2a\u533a\u95f4\u540e\u9762\u63d2\u5165\u4e00\u4e2a\u4ece $p$ \u5f00\u59cb\u533a\u95f4\u5c31\u53ef\u4ee5\u4e86\uff0c\u8fd9\u5f88\u597d\u3002\u56e0\u4e3a\u6bcf\u4e2a\u533a\u95f4\u7684\u53f3\u7aef\u70b9\u90fd\u662f\u7531\u4e0b\u4e00\u4e2a\u533a\u95f4\u5de6\u7aef\u70b9\u51b3\u5b9a\u7684\uff0c\u4e5f\u5c31\u4e0d\u9700\u8981\u5bf9\u539f\u6765\u7684\u533a\u95f4\u505a\u4fee\u6539\u4e86\u3002<\/p>\n
map\u5b9e\u73b0\u7684 split\uff1a<\/p>\n
auto split(int l){\n    auto it = mp.lower_bound(l);\n    if (it-&gt;first == l)\n        return it;\n    it--;\n    return mp.insert({l, it-&gt;second}).first;\n}<\/code><\/pre>\n
\u53ef\u4ee5\u53d1\u73b0\uff0c\u7801\u91cf\u51cf\u5c11\u4e86\u5f88\u591a\u3002<\/p>\n
CF896C\u4ee3\u7801\u5b9e\u73b0<\/h4>\n
\u8fd9\u91cc\u7ed9\u51fa\u4e86\u6a21\u677f\u9898<\/a>\u7684\u4e24\u79cd\u4ee3\u7801\u5b9e\u73b0\u65b9\u5f0f\uff0c\u4ee5\u4f9b\u53c2\u7167\u548c\u5bf9\u6bd4 \uff08set\u5b9e\u73b0\u7684\u61d2\u5f97\u5c01\u88c5\u4e86\uff09<\/del>\u3002<\/p>\n
map\u5b9e\u73b0\uff1a<\/p>\n
#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\ntypedef long long ll;\nconst int maxn = 100005;\nll n, m, seed, vmax;\nll a[maxn];\n\nll qpow(ll a, ll b, ll p)\n{\n    ll res = 1;\n    a %= p;\n    while (b)\n    {\n        if (b &amp; 1)\n            res = res * a % p;\n        b &gt;&gt;= 1;\n        a = a * a % p;\n    }\n    return res;\n}\n\nstruct ODT\n{\n    map&lt;int, ll&gt; mp;\n    ODT(int size)\n    {\n        mp[size] = 0LL;\n        for(int i=0;i&lt;n;i++){\n            mp[i]=a[i];\n        }\n    }\n    auto split(int l)\n    {\n        auto it = mp.lower_bound(l);\n        if (it-&gt;first == l)\n            return it;\n        it--;\n        return mp.insert({l, it-&gt;second}).first;\n    }\n    void assign(int l, int r, ll v)\n    {\n        mp.erase(split(l), split(r));\n        mp[l] = v;\n    }\n    void add(int l, int r, ll v)\n    {\n        for (auto i = split(l), end = split(r); i != end; i++)\n            i-&gt;second += v;\n    }\n    ll kth(int l, int r, int k)\n    {\n        map&lt;ll, int&gt; mp;\n        for (auto i = split(l), end = split(r); i != end; i++)\n            mp[i-&gt;second] += (next(i)-&gt;first - i-&gt;first);\n        for (auto i : mp)\n        {\n            k -= i.second;\n            if (k &lt; 0)\n                return i.first;\n        }\n        return 114514;\n    }\n    ll pow(int l, int r, int x, int p)\n    {\n        ll result = 0;\n        for (auto i = split(l), end = split(r); i != end; i++)\n            result = (result + (ll)(next(i)-&gt;first - i-&gt;first) * qpow(i-&gt;second, x, p)) % p;\n        return result;\n    }\n};\n\nll rnd()\n{\n    ll ret = seed;\n    seed = (seed * 7 + 13) % 1000000007;\n    return ret;\n}\n\nint main()\n{\n    ios::sync_with_stdio(0);\n    cin &gt;&gt; n &gt;&gt; m &gt;&gt; seed &gt;&gt; vmax;\n\n    for (int i = 1; i &lt;= n; i++)\n        a[i - 1] = (rnd() % vmax) + 1;\n\n    ODT odt(n);\n\n    for (int i = 1; i &lt;= m; i++)\n    {\n        int opt = rnd() % 4 + 1;\n        int l = rnd() % n + 1;\n        int r = rnd() % n + 1;\n\n        if (l &gt; r)\n            swap(l, r);\n\n        ll x, y;\n        if (opt == 3)\n            x = rnd() % (r - l + 1) + 1;\n        else\n            x = rnd() % vmax + 1;\n\n        if (opt == 4)\n            y = rnd() % vmax + 1;\n\n        l--;\n\n        if (opt == 1)\n        {\n            odt.add(l, r, x);\n        }\n        else if (opt == 2)\n        {\n            odt.assign(l, r, x);\n        }\n        else if (opt == 3)\n        {\n            cout &lt;&lt; odt.kth(l, r, x - 1) &lt;&lt; &#039;\\n&#039;;\n        }\n        else\n        {\n            cout &lt;&lt; odt.pow(l, r, x, y) &lt;&lt; &#039;\\n&#039;;\n        }\n    }\n\n    return 0;\n}<\/code><\/pre>\n
set\u5b9e\u73b0\uff1a<\/p>\n
#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\ntypedef long long ll;\nconst int maxn = 100005;\nll n, m, seed, vmax;\nll a[maxn];\n\nstruct node\n{\n    int l, r;\n    mutable ll v;\n\n    node(int l, int r, ll v) : l(l), r(r), v(v) {}\n\n    bool operator&lt;(const node &amp;x) const\n    {\n        return l &lt; x.l;\n    }\n};\nset&lt;node&gt; s;\n\nauto split(int pos)\n{\n    auto it = lower_bound(s.begin(), s.end(), (node){pos, 0, 0});\n    if (it != s.end() and it-&gt;l == pos)\n    {\n        return it;\n    }\n    it--;\n    if (it-&gt;r &lt; pos)\n        return s.end();\n    int l = it-&gt;l;\n    int r = it-&gt;r;\n    ll v = it-&gt;v;\n    s.erase(it);\n    s.insert(node(l, pos - 1, v));\n    return s.insert(node(pos, r, v)).first;\n}\n\nvoid assign(int l, int r, ll x)\n{\n    auto itr = split(r + 1), itl = split(l);\n    s.erase(itl, itr);\n    s.insert(node(l, r, x));\n}\n\nvoid add(int l, int r, ll x)\n{\n    auto itr = split(r + 1), itl = split(l);\n    for (auto it = itl; it != itr; it++)\n    {\n        it-&gt;v += x;\n    }\n}\n\nstruct rnk\n{\n    ll num;\n    int len;\n\n    rnk(ll num, int len) : num(num), len(len) {}\n\n    bool operator&lt;(const rnk &amp;x) const\n    {\n        return num &lt; x.num;\n    }\n};\n\nll kth(int l, int r, ll x)\n{\n    auto itr = split(r + 1), itl = split(l);\n    vector&lt;rnk&gt; p;\n    for (auto it = itl; it != itr; it++)\n    {\n        p.push_back(rnk(it-&gt;v, it-&gt;r - it-&gt;l + 1));\n    }\n    sort(p.begin(), p.end());\n\n    int i = 0;\n    for (; i &lt; p.size(); i++)\n    {\n        if (p[i].len &lt; x)\n        {\n            x -= p[i].len;\n        }\n        else\n            break;\n    }\n    return p[i].num;\n}\n\nll qpow(ll a, ll b, ll p)\n{\n    ll res = 1;\n    a %= p;\n    while (b)\n    {\n        if (b &amp; 1)\n            res = res * a % p;\n        b &gt;&gt;= 1;\n        a = a * a % p;\n    }\n    return res;\n}\n\nll calc(int l, int r, ll k, ll p)\n{\n    auto itr = split(r + 1), itl = split(l);\n    ll ans = 0;\n    for (auto it = itl; it != itr; it++)\n    {\n        ans = (ans + qpow(it-&gt;v, k, p) % p * (it-&gt;r - it-&gt;l + 1) % p) % p;\n    }\n    return ans;\n}\n\nll rnd()\n{\n    ll ret = seed;\n    seed = (seed * 7 + 13) % 1000000007;\n    return ret;\n}\n\nint main()\n{\n    ios::sync_with_stdio(0);\n    cin &gt;&gt; n &gt;&gt; m &gt;&gt; seed &gt;&gt; vmax;\n\n    for (int i = 1; i &lt;= n; i++)\n    {\n        a[i] = (rnd() % vmax) + 1;\n        s.insert(node(i, i, a[i]));\n    }\n\n    for (int i = 1; i &lt;= m; i++)\n    {\n        int opt = rnd() % 4 + 1;\n        int l = rnd() % n + 1;\n        int r = rnd() % n + 1;\n\n        if (l &gt; r)\n            swap(l, r);\n\n        ll x, y;\n        if (opt == 3)\n            x = rnd() % (r - l + 1) + 1;\n        else\n            x = rnd() % vmax + 1;\n\n        if (opt == 4)\n            y = rnd() % vmax + 1;\n\n        if (opt == 1)\n        {\n            add(l, r, x);\n        }\n        else if (opt == 2)\n        {\n            assign(l, r, x);\n        }\n        else if (opt == 3)\n        {\n            cout &lt;&lt; kth(l, r, x) &lt;&lt; endl;\n        }\n        else\n        {\n            cout &lt;&lt; calc(l, r, x, y) &lt;&lt; endl;\n        }\n    }\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u7b80\u4ecb \u73c2\u6735\u8389\u6811\uff0c\u53c8\u540d\u8001\u53f8\u673a\u6811\uff08Old Driver Tree\uff09\u3002\u73c2\u6735\u8389\u6811\u8d77\u6e90\u4e8e Codeforces \u7684\u4e00\u573a\u6bd4 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3,6],"tags":[],"class_list":["post-368","post","type-post","status-publish","format-standard","hentry","category-c","category-oi","category-6"],"_links":{"self":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/comments?post=368"}],"version-history":[{"count":2,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/368\/revisions"}],"predecessor-version":[{"id":531,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/368\/revisions\/531"}],"wp:attachment":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/media?parent=368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/categories?post=368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/tags?post=368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}