{"id":10,"date":"2025-11-09T20:23:52","date_gmt":"2025-11-09T12:23:52","guid":{"rendered":"https:\/\/tblog.zeabur.app\/?p=10"},"modified":"2026-01-18T15:09:32","modified_gmt":"2026-01-18T07:09:32","slug":"%e6%9a%b4%e5%8a%9b%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e7%8f%82%e6%9c%b5%e8%8e%89%e6%a0%91-odt","status":"publish","type":"post","link":"https:\/\/tblog.zeabur.app\/?p=10","title":{"rendered":"\u66b4\u529b\u6570\u636e\u7ed3\u6784 : \u73c2\u6735\u8389\u6811 (ODT)"},"content":{"rendered":"\n

\u524d\u8a00<\/h1>\n\n\n\n

\u73c2\u6735\u8389\u6811Old Driver Tree<\/rt><\/ruby> (ODT) \u662f\u4e00\u79cd\u5341\u5206\u66b4\u529b\u7684\u6570\u636e\u7ed3\u6784\u3002\u73c2\u6735\u8389\u6811\u662f\u4e00\u573a CF \u6bd4\u8d5b\u4e2d\u63d0\u51fa\u7684\u6570\u636e\u7ed3\u6784\uff0c\u56e0\u90a3\u9053\u9898\u9898\u9762\uff08CF896C\uff09\u5173\u4e8e\u73c2\u6735\u8389\u800c\u5f97\u540d\u3002<\/p>\n\n\n\n

\u73c2\u6735\u8389\u6811\u9002\u7528\u4e8e\u4ee5\u4e0b\u7684\u60c5\u51b5\uff1a\u7ef4\u62a4\u4e00\u4e2a\u5e8f\u5217\uff0c\u6709\u533a\u95f4\u8d4b\u503c<\/strong>\u64cd\u4f5c\uff0c\u6570\u636e\u968f\u673a<\/strong>\u3002\u4e0b\u9762\u662f\u73c2\u6735\u8389\u6811\u677f\u5b50\u9898\uff1a<\/p>\n\n\n\n

\n

\u7ef4\u62a4\u4e00\u4e2a\u5e8f\u5217\uff0c\u9700\u8981\u652f\u6301\u4ee5\u4e0b\u64cd\u4f5c<\/p>\n\n\n\n

1. \u5c06 $[l,r]$ \u533a\u95f4\u6240\u6709\u6570\u52a0\u4e0a $x$<\/p>\n\n\n\n

2. \u5c06 $[l,r]$ \u533a\u95f4\u6240\u6709\u6570\u6539\u6210 $x$<\/p>\n\n\n\n

3. \u6c42 $[l,r]$ \u533a\u95f4\u7b2c $k$ \u5c0f<\/p>\n\n\n\n

4. \u6c42 $[l,r]$ \u533a\u95f4\u6bcf\u4e2a\u6570\u5b57\u7684 $x$ \u6b21\u65b9\u7684\u548c\u6a21 $y$ \u7684\u503c (\u5373 $\\left(\\sum_{i=l}^{r} a_{i}^{x}\\right) \\bmod y$)<\/p>\n\n\n\n

\u2013 CF896C Willem, Chtholly and Seniorious<\/p>\n<\/blockquote>\n\n\n\n

\u652f\u6301\u7684\u64cd\u4f5c\u8fd8\u53ef\u4ee5\u6709\u5f88\u591a\uff0c\u53ea\u8981\u66b4\u529b\u80fd\u505a\u73c2\u6735\u8389\u6811\u4e00\u822c\u90fd\u53ef\u4ee5\u505a\u3002<\/p>\n\n\n\n

\u73c2\u6735\u8389\u6811\u7684\u601d\u60f3\u662f\u7ef4\u62a4\u4e00\u5806\u533a\u95f4\uff0c\u5408\u5e76\u76f8\u540c\u503c\u7684\u533a\u95f4\uff0c\u8fd9\u6837\u533a\u95f4\u603b\u6570\u5c31\u53ef\u4ee5\u51cf\u5c11\u3002<\/p>\n\n\n\n

\u73c2\u6735\u8389\u6811\u975e\u5e38\u4f9d\u8d56\u533a\u95f4\u8d4b\u503c\u64cd\u4f5c<\/strong>\uff0c\u5982\u679c\u533a\u95f4\u8d4b\u503c\u64cd\u4f5c\u5f88\u5c11\u6216\u8005\u533a\u95f4\u8d4b\u503c\u7684\u533a\u95f4\u90fd\u8f83\u77ed\uff0c\u90a3\u4e48\u73c2\u6735\u8389\u6811\u548c\u66b4\u529b\u5c31\u6ca1\u4ec0\u4e48\u533a\u522b\u4e86\u3002<\/p>\n\n\n\n

\u663e\u7136\uff0c\u8981\u5361\u73c2\u6735\u8389\u6811\u975e\u5e38\u5bb9\u6613\u3002\u4f46\u5bf9\u4e8e\u6570\u636e\u5b8c\u5168\u968f\u673a\u7684\u60c5\u51b5\uff0c\u73c2\u6735\u8389\u6811\u5c31\u53ef\u4ee5\u8dd1\u5f97\u98de\u5feb\u3002\u6709\u5f88\u591a\u9898\u53ef\u4ee5\u7528\u73c2\u6735\u8389\u6811\u6c34\u8fc7\uff0c\u751a\u81f3\u6bd4\u6b63\u89e3\u8fd8\u5feb\u3002<\/p>\n\n\n\n

\u601d\u8def<\/h1>\n\n\n\n

\u73c2\u6735\u8389\u6811\u7ef4\u62a4\u4e86\u5f88\u591a\u533a\u95f4\u3002<\/p>\n\n\n\n

\u4e00\u4e2a\u533a\u95f4\u8868\u793a\u4e00\u6bb5\u76f8\u540c\u7684\u6570<\/strong>\u3002\u4e00\u4e2a\u533a\u95f4 $(l,r,num)$ \u8868\u793a\u4ece\u5de6\u7aef\u70b9 $l$ \u5230\u53f3\u7aef\u70b9 $r$\uff0c\u4e2d\u95f4\u7684\u6570\u5b57\u5168\u90e8\u4e3a $num$\u3002<\/p>\n\n\n\n

\u4f8b\u5982 $1,2,3,3,3,4,4,5$ \u53ef\u4ee5\u7528 $5$ \u4e2a\u533a\u95f4\u6765\u8868\u793a\uff1a$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$\u3002<\/p>\n\n\n\n

\u533a\u95f4\u8d4b\u503c\u7684\u65f6\u5019\uff0c\u6211\u4eec\u53ef\u4ee5\u5220\u53bb\u4e00\u4e9b\u533a\u95f4\u5e76\u7528\u4e00\u4e2a\u5927\u533a\u95f4\u4ee3\u66ff\u5b83\u4eec\uff0c\u533a\u95f4\u6570\u91cf\u5c31\u5c11\u4e86\u5f88\u591a\u3002<\/p>\n\n\n\n

\u800c\u67e5\u8be2\u53ea\u9700\u8981\u627e\u51fa\u76f8\u5e94\u7684\u533a\u95f4\uff0c\u7136\u540e\u66b4\u529b\u7edf\u8ba1\u5373\u53ef\u3002<\/p>\n\n\n\n

\u5982\u679c\u67d0\u6b21\u64cd\u4f5c\u7684\u8fb9\u754c\u5728\u67d0\u4e2a\u533a\u95f4\u7684\u4e2d\u5fc3\uff0c\u90a3\u4e48\u5c06\u8fd9\u4e2a\u533a\u95f4\u65ad\u5f00\u5373\u53ef\u3002<\/p>\n\n\n\n

\u6211\u4eec\u7528 set \u7ef4\u62a4\u533a\u95f4\u5de6\u7aef\u70b9\u4f4d\u7f6e\u7684\u503c\uff0c\u4f7f\u533a\u95f4\u59cb\u7ec8\u4fdd\u6301\u6709\u5e8f\u3002<\/p>\n\n\n\n

\u533a\u95f4\u7ed3\u6784\u4f53\u5b9a\u4e49<\/h2>\n\n\n\n
struct node\n{\n    long long l,r;\n    mutable long long num;\n    bool operator<(const node y) const\n    {\n        return l<y.l;\n    }\n};<\/code><\/pre>\n\n\n\n
Split<\/h2>\n\n\n\n
Split \u64cd\u4f5c\u7528\u6765\u5c06\u4e00\u4e2a\u533a\u95f4\u65ad\u5f00\u3002<\/p>\n\n\n\n
set<node>::iterator split(long long x)\n{\n    node tmp={x};\n    set<node>::iterator it=s.lower_bound(tmp);\n    if(it!=s.end()&&it->l==x)\n    {\n        return it;\n    }\n    it--;\n    long long l=it->l,r=it->r,num=it->num;\n    s.erase(it);\n    tmp={l,x-1,num};\n    s.insert(tmp);\n    tmp={x,r,num};\n    return s.insert(tmp).first;\n}<\/code><\/pre>\n\n\n\n
\u533a\u95f4\u8d4b\u503c\u64cd\u4f5c (Assign)<\/h2>\n\n\n\n
\u5220\u9664\u8be5\u533a\u95f4\u6240\u8986\u76d6\u7684\u6240\u6709\u5c0f\u533a\u95f4\uff0c\u5e76\u63d2\u5165\u4e00\u4e2a\u5927\u533a\u95f4\u6765\u4ee3\u66ff\u5b83\u4eec\u3002<\/p>\n\n\n\n
void assign(long long l,long long r,long long x)\n{\n    set<node>::iterator R=split(r+1);\n    set<node>::iterator L=split(l);\n    s.erase(L,R);\n    node tmp={l,r,x};\n    s.insert(tmp);\n}<\/code><\/pre>\n\n\n\n
\u67e5\u8be2\u64cd\u4f5c<\/h2>\n\n\n\n
\u5c31\u662f\u66b4\u529b\uff0c\u627e\u51fa\u76f8\u5e94\u533a\u95f4\u5e76\u66b4\u529b\u7edf\u8ba1<\/p>\n\n\n\n
\u533a\u95f4\u548c<\/h3>\n\n\n\n
long long query_sum(long long l,long long r)\n{\n\tset<node>::iterator R=split(r+1),L=split(l);\n\tlong long ans=0;\n\twhile (L!=R)\n       {\n\t\tans+=L->num*(L->r-L->l+1); \/\/\u904d\u5386\u6c42\u548c\n\t\tans%=y; \n\t\tL++;\n\t}\n\treturn ans;\n}<\/code><\/pre>\n\n\n\n
\u533a\u95f4 x \u6b21\u65b9\u548c<\/h3>\n\n\n\n
\u548c\u6c42\u548c\u4e00\u6837\uff0c\u53ea\u662f\u6539\u6210\u5feb\u901f\u5e42<\/p>\n\n\n\n
long long query_pow_sum(long long l,long long r,long long x,long long y)\n{\n    set<node>::iterator R=split(r+1),L=split(l);\n    long long ans=0;\n    while(L!=R)\n    {\n        ans+=qpow(L->num,x,y)*(L->r-L->l+1);\n        ans%=y;\n        L++;\n    }\n    return ans;\n}<\/code><\/pre>\n\n\n\n
\u533a\u95f4\u7b2c k \u5c0f<\/h3>\n\n\n\n
\u53d6\u51fa\u76f8\u5e94\u533a\u95f4\u5185\u7684\u6240\u6709\u533a\u95f4\u6392\u5e8f\uff0c\u4ece\u524d\u5230\u540e\u627e\u7b2c k \u5c0f<\/p>\n\n\n\n
long long query_kth(long long l,long long r,long long k)\n{\n    set<node>::iterator R=split(r+1),L=split(l);\n    vector<pair<long long,long long> > t;\n    while(L!=R)\n    {\n        t.push_back(make_pair(L->num,L->r-L->l+1));\n        L++;\n    }\n    sort(t.begin(),t.end());\n    for(long long i=0;i<t.size();i++)\n    {\n        k-=t[i].second;\n        if(k<=0)\n        {\n            return t[i].first;\n        }\n    }\n    return -2147483647;\n}<\/code><\/pre>\n\n\n\n
\u5176\u4ed6\u64cd\u4f5c<\/h3>\n\n\n\n
\u4f60\u5e94\u8be5\u5df2\u7ecf\u53d1\u73b0\u4e86\uff0c\u73c2\u6735\u8389\u6811\u5176\u5b9e\u5c31\u662f\u66b4\u529b\uff0c\u66b4\u529b\u600e\u4e48\u5199\u73c2\u6735\u8389\u6811\u5c31\u600e\u4e48\u5199\uff0c\u771f\u00b7\u66b4\u529b\u6570\u636e\u7ed3\u6784<\/p>\n\n\n\n
\u4f8b\u9898\u4ee3\u7801<\/h1>\n\n\n\n
CF896C Willem, Chtholly and Seniorious<\/a><\/p>\n\n\n\n
#include<bits\/stdc++.h>\nusing namespace std;\n\nlong long n,m,seed,vmax;\n\nlong long rnd()\n{\n    long long ret=seed;\n    seed=(seed*7+13)%1000000007;\n    return ret;\n}\n\ninline long long qpow(long long a,long long b,long long p)\n{\n    long long ans=1;\n    a%=p;\n    while(b)\n    {\n        if(b&1)\n        {\n            ans=ans*a%p;\n        }\n        a=a*a%p;\n        b>>=1;\n    }\n    return ans;\n}\n\nstruct node\n{\n    long long l,r;\n    mutable long long num;\n    bool operator<(const node y) const\n    {\n        return l<y.l;\n    }\n};\n\nset<node> s;\n\nset<node>::iterator split(long long x)\n{\n    node tmp={x};\n    set<node>::iterator it=s.lower_bound(tmp);\n    if(it!=s.end()&&it->l==x)\n    {\n        return it;\n    }\n    it--;\n    long long l=it->l,r=it->r,num=it->num;\n    s.erase(it);\n    tmp={l,x-1,num};\n    s.insert(tmp);\n    tmp={x,r,num};\n    return s.insert(tmp).first;\n}\n\nvoid assign(long long l,long long r,long long x)\n{\n    set<node>::iterator R=split(r+1);\n    set<node>::iterator L=split(l);\n    s.erase(L,R);\n    node tmp={l,r,x};\n    s.insert(tmp);\n}\n\nlong long query_kth(long long l,long long r,long long k)\n{\n    set<node>::iterator R=split(r+1),L=split(l);\n    vector<pair<long long,long long> > t;\n    while(L!=R)\n    {\n        t.push_back(make_pair(L->num,L->r-L->l+1));\n        L++;\n    }\n    sort(t.begin(),t.end());\n    for(long long i=0;i<t.size();i++)\n    {\n        k-=t[i].second;\n        if(k<=0)\n        {\n            return t[i].first;\n        }\n    }\n    return -2147483647;\n}\n\nlong long query_pow_sum(long long l,long long r,long long x,long long y)\n{\n    set<node>::iterator R=split(r+1),L=split(l);\n    long long ans=0;\n    while(L!=R)\n    {\n        ans+=qpow(L->num,x,y)*(L->r-L->l+1);\n        ans%=y;\n        L++;\n    }\n    return ans;\n}\n\nvoid add(long long l,long long r,long long x)\n{\n    set<node>::iterator R=split(r+1),L=split(l);\n    while(L!=R)\n    {\n        L->num+=x;\n        L++;\n    }\n}\n\nint main()\n{\n    cin>>n>>m>>seed>>vmax;\n    for(long long i=1;i<=n;i++)\n    {\n        node tmp={i,i,rnd()%vmax+1};\n        s.insert(tmp);\n    }\n    for(long long i=1;i<=m;i++)\n    {\n        long long op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;\n        if(l>r)\n        {\n            swap(l,r);\n        }\n        if(op==3)\n        {\n            x=(rnd()%(r-l+1))+1;\n        }\n        else\n        {\n            x=(rnd()%vmax)+1;\n        }\n        if(op==4)\n        {\n            y=(rnd()%vmax)+1;\n        }\n        if(op==1)\n        {\n            add(l,r,x);\n        }\n        if(op==2)\n        {\n            assign(l,r,x);\n        }\n        if(op==3)\n        {\n            cout<<query_kth(l,r,x)<<endl;\n        }\n        if(op==4)\n        {\n            cout<<query_pow_sum(l,r,x,y)<<endl;\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
\u6ce8\uff1a\u8f6c\u8f7d\u81ea\u66b4\u529b\u6570\u636e\u7ed3\u6784 : \u73c2\u6735\u8389\u6811 (ODT)<\/a><\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u524d\u8a00 \u73c2\u6735\u8389\u6811Old Driver Tree (ODT) \u662f\u4e00\u79cd\u5341\u5206\u66b4\u529b\u7684\u6570\u636e\u7ed3\u6784\u3002\u73c2\u6735\u8389\u6811\u662f\u4e00\u573a  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,8],"tags":[3,4],"class_list":["post-10","post","type-post","status-publish","format-standard","hentry","category-oi","category-reblog","tag-oi","tag-reblog"],"featured_image_src":null,"author_info":{"display_name":"CaelumRadish_c","author_link":"https:\/\/tblog.zeabur.app\/?author=1"},"_links":{"self":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/10","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10"}],"version-history":[{"count":2,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":13,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/10\/revisions\/13"}],"wp:attachment":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}