{"id":194,"date":"2019-08-07T13:28:00","date_gmt":"2019-08-07T13:28:00","guid":{"rendered":"https:\/\/imwarming.com\/?p=194"},"modified":"2019-08-07T13:28:00","modified_gmt":"2019-08-07T13:28:00","slug":"%e4%b8%80%e4%ba%9b%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/imwarming.com\/?p=194","title":{"rendered":"\u4e00\u4e9b\u6a21\u677f"},"content":{"rendered":"

string \u64cd\u4f5c\uff1a<\/h3>\n
\n
 1<\/span> =,assign()   \/\/<\/span>\u8d4b\u4ee5\u65b0\u503c<\/span>\n 2<\/span> s.assign(str); \n<\/span> 3<\/span> s.assign(str,1<\/span>,3<\/span>);\/\/<\/span>\u5982\u679cstr\u662f”iamangel” \u5c31\u662f\u628a”ama”\u8d4b\u7ed9\u5b57\u7b26\u4e32<\/span>\n 4<\/span> s.assign(str,2<\/span>,string<\/span>::npos);\/\/<\/span>\u628a\u5b57\u7b26\u4e32str\u4ece\u7d22\u5f15\u503c2\u5f00\u59cb\u5230\u7ed3\u5c3e\u8d4b\u7ed9s<\/span>\n 5<\/span> s.assign(“gaint”); \n<\/span> 6<\/span> s.assign(“nico”,5<\/span>);\/\/<\/span>\u628a’n’ ‘i’ ‘c’ ‘o’ ‘\u0000’\u8d4b\u7ed9\u5b57\u7b26\u4e32<\/span>\n 7<\/span> s.assign(5<\/span>,’x’);\/\/<\/span>\u628a\u4e94\u4e2ax\u8d4b\u7ed9\u5b57\u7b26\u4e32<\/span>\n 8<\/span> b) swap()   \/\/<\/span>\u4ea4\u6362\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u5185\u5bb9<\/span>\n 9<\/span> c) +=,append(),push_back() \/\/<\/span>\u5728\u5c3e\u90e8\u6dfb\u52a0\u5b57\u7b26<\/span>\n10<\/span> d) insert() \/\/<\/span>\u63d2\u5165\u5b57\u7b26<\/span>\n11<\/span> e) erase() \/\/<\/span>\u5220\u9664\u5b57\u7b26<\/span>\n12<\/span> g) replace() \/\/<\/span>\u66ff\u6362\u5b57\u7b26<\/span>\n13<\/span> h) +\/\/<\/span>\u4e32\u8054\u5b57\u7b26\u4e32<\/span>\n14<\/span> ==,!=,<,<=,>,>=,compare()  \/\/<\/span>\u6bd4\u8f83\u5b57\u7b26\u4e32<\/span>\n15<\/span> string<\/span> s(“abcd”);\n<\/span>16<\/span>     s.compare(“abcd”); \/\/<\/span>\u8fd4\u56de0<\/span>\n17<\/span>     s.compare(“dcba”); \/\/<\/span>\u8fd4\u56de\u4e00\u4e2a\u5c0f\u4e8e0\u7684\u503c<\/span>\n18<\/span>     s.compare(“ab”); \/\/<\/span>\u8fd4\u56de\u5927\u4e8e0\u7684\u503c<\/span>\n19<\/span>     s.compare(s); \/\/<\/span>\u76f8\u7b49<\/span>\n20<\/span>     s.compare(0<\/span>,2<\/span>,s,2<\/span>,2<\/span>); \/\/<\/span>\u7528”ab”\u548c”cd”\u8fdb\u884c\u6bd4\u8f83 \u5c0f\u4e8e\u96f6<\/span>\n21<\/span>     s.compare(1<\/span>,2<\/span>,”bcx”,2<\/span>); \/\/<\/span>\u7528”bc”\u548c”bc”\u6bd4\u8f83\u3002<\/span>\n22<\/span> j) size(),length()  \/\/<\/span>\u8fd4\u56de\u5b57\u7b26\u6570\u91cf<\/span>\n23<\/span> r) copy() \/\/<\/span>\u5c06\u67d0\u503c\u8d4b\u503c\u4e3a\u4e00\u4e2ac_string<\/span>\n24<\/span> s) c_str() \/\/<\/span>\u5c06\u5185\u5bb9\u4ee5c_string\u8fd4\u56de<\/span>\n25<\/span> u) substr() \/\/<\/span>\u8fd4\u56de\u67d0\u4e2a\u5b50\u5b57\u7b26\u4e32<\/span>\n26<\/span>     s.substr(11<\/span>);\/\/<\/span>\u4ece\u7d22\u5f1511\u5f80\u540e\u7684\u5b50\u4e32<\/span>\n27<\/span>     s.substr(5<\/span>,6<\/span>);\/\/<\/span>\u4ece\u7d22\u5f155\u5f00\u59cb6\u4e2a\u5b57\u7b26<\/span>\n28<\/span> k\uff09find\uff08\uff09\n<\/span>29<\/span> string<\/span>::size_type position;  \n<\/span>30<\/span> position = s.find(\"<\/span>xx<\/span>\"<\/span>);  \n<\/span>31<\/span> \/\/<\/span>\u67e5\u627es \u4e2dflag \u51fa\u73b0\u7684\u6240\u6709\u4f4d\u7f6e\u3002  <\/span>\n32<\/span>  flag=\"<\/span>a<\/span>\"<\/span>;  \n<\/span>33<\/span> position=0<\/span>;  \n<\/span>34<\/span> while<\/span>((position=s.find_first_of(flag,position))!=string<\/span>::npos)  \n<\/span>35<\/span> {  \n<\/span>36<\/span> \/\/<\/span>position=s.find_first_of(flag,position);  <\/span>\n37<\/span> cout<<\"<\/span>position  : <\/span>\"<\/span><<position<<endl;  \n<\/span>38<\/span> position++;  \n<\/span>39<\/span>  }  <\/pre>\n<\/div>\n
gcd \uff1a<\/h3>\n
\n
int<\/span> gcd(int<\/span> x,int<\/span> y){\n    <\/span>return<\/span> y?gcd(y,x%y):x;\n} <\/span><\/pre>\n<\/div>\n
lcm :<\/h3>\n
\n
int<\/span> lcm(int<\/span> a,int<\/span> b) {return<\/span> a*b\/gcd(a,b);  }<\/pre>\n<\/div>\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5f97 \uff1a<\/strong><\/h3>\n
\n
 1<\/span> int<\/span> exgcd(int<\/span> a, int<\/span> b, int<\/span>& x, int<\/span>& y){\/\/<\/span>a*x+b*y=gcd(a,b)=d;(x,y)\u4e3a\u5176\u4e00\u7ec4\u6574\u6570\u89e3<\/span>\n 2<\/span>     int<\/span> d = a;\n<\/span> 3<\/span>     if<\/span>(b != 0<\/span>){\n<\/span> 4<\/span>         d = exgcd(b, a % b, y, x);\n<\/span> 5<\/span>         y -= (a \/ b) * x;\n<\/span> 6<\/span>     }else<\/span> {\n<\/span> 7<\/span>         x = 1<\/span>;\n<\/span> 8<\/span>         y = 0<\/span>;\n<\/span> 9<\/span>     }\n<\/span>10<\/span>     return<\/span> d;\n<\/span>11<\/span> }<\/pre>\n<\/div>\n
\u5feb\u901f\u5e42 \uff1a<\/strong><\/h3>\n
\n
 1<\/span> ll quick_power(ll base<\/span>, ll n){\n<\/span> 2<\/span>     ll res = 1<\/span>;\n<\/span> 3<\/span>     while<\/span> (n > 0<\/span>){\n<\/span> 4<\/span>         if<\/span> (n & 1<\/span>)\n<\/span> 5<\/span>             res *= base<\/span>; \/\/<\/span> res = (res * base) % mod;<\/span>\n 6<\/span>         base<\/span> *= base<\/span>; \/\/<\/span>base = (base * base) % mod;<\/span>\n 7<\/span>         n >>= 1<\/span>;\n<\/span> 8<\/span>     }\n<\/span> 9<\/span>     return<\/span> res;\n<\/span>10<\/span> }<\/pre>\n<\/div>\n
\u77e9\u9635\u5feb\u901f\u5e42 \uff1a<\/h3>\n
\n
 1<\/span> int<\/span> mod;\n<\/span> 2<\/span> int<\/span> n,m,sum;\n<\/span> 3<\/span> struct<\/span> mtix{\n<\/span> 4<\/span>     int<\/span> a[maxn][maxn];\n<\/span> 5<\/span>     mtix(){memset(a,0<\/span>,sizeof<\/span>(a));}\n<\/span> 6<\/span> }f;\n<\/span> 7<\/span> mtix mul(mtix a,mtix b){\n<\/span> 8<\/span>     mtix c;\n<\/span> 9<\/span>     for<\/span> (int<\/span> i=1<\/span>;i<=n;i++)\n<\/span>10<\/span>         for<\/span> (int<\/span> j=1<\/span>;j<=n;j++)\n<\/span>11<\/span>             for<\/span> (int<\/span> k=1<\/span>;k<=n;k++)\n<\/span>12<\/span>             {c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;c.a[i][j]%=mod;}\n<\/span>13<\/span>     return<\/span> c;\n<\/span>14<\/span> }\n<\/span>15<\/span> mtix mpow(int<\/span> y){\n<\/span>16<\/span>     mtix ans;\n<\/span>17<\/span>     mtix tem=f;\n<\/span>18<\/span>     for<\/span> (int<\/span> i=1<\/span>;i<=n;i++)\n<\/span>19<\/span>         ans.a[i][i]=1<\/span>;\n<\/span>20<\/span>     for<\/span> (;y;tem=mul(tem,tem),y>>=1<\/span>)\n<\/span>21<\/span>         if<\/span> (y&1<\/span>) ans=mul(ans,tem);\n<\/span>22<\/span>     for<\/span> (int<\/span> i=1<\/span>;i<=n;i++)\n<\/span>23<\/span>         sum+=ans.a[i][i];\n<\/span>24<\/span>     cout<<sum%mod<<endl;\n<\/span>25<\/span>     return<\/span> ans;\n<\/span>26<\/span> }\n<\/span>27<\/span> int<\/span> main(){\n<\/span>28<\/span>     cin>>n>>m;\n<\/span>29<\/span>     for<\/span> (int<\/span> i=1<\/span>;i<=n;i++)\n<\/span>30<\/span>         for<\/span> (int<\/span> k=1<\/span>;k<=n;k++)\n<\/span>31<\/span>             cin>>f.a[i][k];\n<\/span>32<\/span>     mpow(m);\n<\/span>33<\/span> }<\/pre>\n<\/div>\n
\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217lcs \uff1a<\/h3>\n
\n
 1<\/span> char<\/span> a[1010<\/span>],b[1010<\/span>];\n<\/span> 2<\/span> int<\/span> dp[1010<\/span>][1010<\/span>];\n<\/span> 3<\/span> int<\/span> main(){\n<\/span> 4<\/span>     int<\/span> lena,lenb,i,j;\n<\/span> 5<\/span>     while<\/span>(scanf(\"<\/span>%s%s<\/span>\"<\/span>,&a,&b)!=eof){\n<\/span> 6<\/span>         lena=strlen(a);\n<\/span> 7<\/span>         lenb=strlen(b);\n<\/span> 8<\/span>         memset(dp,0<\/span>,sizeof<\/span>(dp));\n<\/span> 9<\/span>         for<\/span>(i=1<\/span>;i<=lena;++i){\n<\/span>10<\/span>             for<\/span>(j=1<\/span>;j<=lenb;++j){\n<\/span>11<\/span>                 if<\/span>(a[i-1<\/span>]==b[j-1<\/span>])\n<\/span>12<\/span>                     dp[i][j]=dp[i-1<\/span>][j-1<\/span>]+1<\/span>;\n<\/span>13<\/span>                 else<\/span>\n14<\/span>                     dp[i][j]=max(dp[i-1<\/span>][j],dp[i][j-1<\/span>]);\n<\/span>15<\/span>             }\n<\/span>16<\/span>         }\n<\/span>17<\/span>         printf(\"<\/span>%dn<\/span>\"<\/span>,dp[lena][lenb]);\n<\/span>18<\/span>     }\n<\/span>19<\/span>     return<\/span> 0<\/span>;\n<\/span>20<\/span> }<\/pre>\n<\/div>\n
\u6700\u77ed\u8def<\/strong>floyd \uff1a<\/h3>\n
\n
1<\/span> for<\/span> (int<\/span> k = 1<\/span>; k <= n; k++) {\n<\/span>2<\/span>     for<\/span> (int<\/span> i = 1<\/span>; i <= n; i++) {\n<\/span>3<\/span>         if<\/span> (i == k) continue<\/span>;\n<\/span>4<\/span>         for<\/span> (int<\/span> j = 1<\/span>; j <= n; j++) {\n<\/span>5<\/span>             if<\/span> (i == j || k == j) continue<\/span>;\n<\/span>6<\/span>             dis[i][j] = min(dis[i][j], dis[i][k]+ dis[k][j]);\n<\/span>7<\/span>         }\n<\/span>8<\/span>     }\n<\/span>9<\/span> }<\/pre>\n<\/div>\n
\u5e76\u67e5\u96c6 \uff1a<\/h3>\n
\n
 1<\/span> int<\/span> pre[maxn];\n<\/span> 2<\/span> int<\/span> tot[maxn];\/\/<\/span>\u96c6\u5408\u5143\u7d20\u6570\u91cf<\/span>\n 3<\/span> int<\/span> rank[maxn];\/\/<\/span>\u96c6\u5408\u6392\u540d<\/span>\n 4<\/span> int<\/span> n,m,k;\n<\/span> 5<\/span> void<\/span> init(){\n<\/span> 6<\/span>     for<\/span>(int<\/span> i=1<\/span>;i<=n;++i){\n<\/span> 7<\/span>         pre[i]=i;\n<\/span> 8<\/span>         tot[i]=1<\/span>;\n<\/span> 9<\/span>     }\n<\/span>10<\/span>     mst(rank,0<\/span>);\n<\/span>11<\/span> }\n<\/span>12<\/span> int<\/span> find(int<\/span> x){\n<\/span>13<\/span>     if<\/span>(x==pre[x])\n<\/span>14<\/span>         return<\/span> x;\n<\/span>15<\/span>     else<\/span>\n16<\/span>         return<\/span> pre[x]=find(pre[x]);\n<\/span>17<\/span> }\n<\/span>18<\/span> \n19<\/span> void<\/span> join(int<\/span> x, int<\/span> y){\n<\/span>20<\/span>     x = find(x);\n<\/span>21<\/span>     y = find(y);\n<\/span>22<\/span>     if<\/span> (rank[x] > rank[y]){\n<\/span>23<\/span>         pre[y] = x;\n<\/span>24<\/span>         if<\/span> (x != y)\n<\/span>25<\/span>             tot[x] += tot[y];\n<\/span>26<\/span>     }\n<\/span>27<\/span>     else<\/span>{\n<\/span>28<\/span>         pre[x] = y;\n<\/span>29<\/span>         if<\/span> (x != y)\n<\/span>30<\/span>             tot[y] += tot[x];\n<\/span>31<\/span>         if<\/span> (rank[x] == rank[y])\n<\/span>32<\/span>             rank[y] += 1<\/span>;\n<\/span>33<\/span>     }\n<\/span>34<\/span> }<\/pre>\n<\/div>\n
sg \u6253\u8868 \uff1a<\/h3>\n
\n
\/\/<\/span>f[]\uff1a\u53ef\u4ee5\u53d6\u8d70\u7684\u77f3\u5b50\u4e2a\u6570\n<\/span>\/\/<\/span>sg[]:0~n\u7684sg\u51fd\u6570\u503c<\/span>\nint<\/span> f[maxn],sg[maxn],mex[maxn];\n<\/span>void<\/span> getsg(int<\/span> n){\n    <\/span>int<\/span> i,j;\n    memset(sg,<\/span>0<\/span>,sizeof<\/span>(sg));\n    <\/span>for<\/span>(i=1<\/span>;i<=n;i++){\n        memset(mex,<\/span>0<\/span>,sizeof<\/span>(mex));\n        <\/span>for<\/span>(j=1<\/span>;f[j]<=i&&f[j]<=m;j++) \/\/<\/span>\u6ce8\u610f\u52a0f[i]\u7684\u9650\u5b9a\u6761\u4ef6\uff0c\u6b64\u5904\u4e3af[j]<=m<\/span>\n            mex[sg[i-f[j]]]=1<\/span>;\n        <\/span>for<\/span>(j=0<\/span>;j<=n;j++){    \/\/<\/span>\u6c42mex\u4e2d\u672a\u51fa\u73b0\u7684\u6700\u5c0f\u7684\u975e\u8d1f\u6574\u6570<\/span>\n            if<\/span>(mex[j]==0<\/span>){\n                sg[i]<\/span>=j;\n                <\/span>break<\/span>;\n            }\n        }\n        <\/span>\/\/<\/span>cout<<i<<\" \"<<sg[i]<<endl;<\/span>\n    }\n}<\/span><\/pre>\n<\/div>\n
\n
 1<\/span> int<\/span> f[maxn],sg[maxn];bool<\/span> mex[maxn];\n<\/span> 2<\/span> void<\/span> getsg(int<\/span> k,int<\/span> n){\n<\/span> 3<\/span>     int<\/span> i,j;\n<\/span> 4<\/span>     memset(sg,0<\/span>,sizeof<\/span>(sg));\n<\/span> 5<\/span>     for<\/span>(i=1<\/span>;i<=n;i++){\n<\/span> 6<\/span>         memset(mex,0<\/span>,sizeof<\/span>(mex));\n<\/span> 7<\/span>         for<\/span>(j=1<\/span>;f[j]<=i&&j<=k;j++)\n<\/span> 8<\/span>             mex[sg[i-f[j]]]=true<\/span>;\n<\/span> 9<\/span>         for<\/span>(j=0<\/span>;j<=n;j++){\n<\/span>10<\/span>             if<\/span>(mex[j]==false<\/span>){\n<\/span>11<\/span>                 sg[i]=j;\n<\/span>12<\/span>                 break<\/span>;\n<\/span>13<\/span>             }\n<\/span>14<\/span>         }\n<\/span>15<\/span>     }\n<\/span>16<\/span> }\/\/<\/span>\u8fd9\u4e2a\u597d\u50cf\u66f4\u5feb<\/span><\/pre>\n<\/div>\n
sg_dfs :<\/h3>\n
\n
 1<\/span> 1<\/span> \/\/<\/span>\u6ce8\u610f s\u6570\u7ec4\u8981\u6309\u4ece\u5c0f\u5230\u5927\u6392\u5e8f sg\u51fd\u6570\u8981\u521d\u59cb\u5316\u4e3a-1 \u5bf9\u4e8e\u6bcf\u4e2a\u96c6\u5408\u53ea\u9700\u521d\u59cb\u53161\u904d<\/span>\n 2<\/span>  2<\/span> \/\/<\/span>n\u662f\u96c6\u5408s\u7684\u5927\u5c0f s[i]\u662f\u5b9a\u4e49\u7684\u7279\u6b8a\u53d6\u6cd5\u89c4\u5219\u7684\u6570\u7ec4<\/span>\n 3<\/span>  3<\/span> int<\/span> s[110<\/span>],sg[10010<\/span>],n;\n<\/span> 4<\/span>  4<\/span> int<\/span> sg_dfs(int<\/span> x)\n<\/span> 5<\/span>  5<\/span> {\n<\/span> 6<\/span>  6<\/span>     int<\/span> i;\n<\/span> 7<\/span>  7<\/span>     if<\/span>(sg[x]!=-1<\/span>)\n<\/span> 8<\/span>  8<\/span>         return<\/span> sg[x];\n<\/span> 9<\/span>  9<\/span>     bool<\/span> mex[110<\/span>];\n<\/span>10<\/span> 10<\/span>     memset(mex,0<\/span>,sizeof<\/span>(mex));\n<\/span>11<\/span> 11<\/span>     for<\/span>(i=0<\/span>;i<n;i++)\n<\/span>12<\/span> 12<\/span>     {\n<\/span>13<\/span> 13<\/span>         if<\/span>(x>=s[i])\n<\/span>14<\/span> 14<\/span>         {\n<\/span>15<\/span> 15<\/span>             sg_dfs(x-s[i]);\n<\/span>16<\/span> 16<\/span>             mex[sg[x-s[i]]]=1<\/span>;\n<\/span>17<\/span> 17<\/span>         }\n<\/span>18<\/span> 18<\/span>     }\n<\/span>19<\/span> 19<\/span>     int<\/span> e;\n<\/span>20<\/span> 20<\/span>     for<\/span>(i=0<\/span>;;i++)\n<\/span>21<\/span> 21<\/span>         if<\/span>(!mex[i])\n<\/span>22<\/span> 22<\/span>         {\n<\/span>23<\/span> 23<\/span>             e=i;\n<\/span>24<\/span> 24<\/span>             break<\/span>;\n<\/span>25<\/span> 25<\/span>         }\n<\/span>26<\/span> 26<\/span>     return<\/span> sg[x]=e;\n<\/span>27<\/span> 27<\/span> }<\/pre>\n<\/div>\n
\u7ebf\u6bb5\u6811 \uff1a<\/p>\n
\n
 1<\/span> \/\/<\/span>\u6c42\u548c\u4e3a\u4f8b\u5efa\u6811 <\/span>\n 2<\/span> 1<\/span> const<\/span> int<\/span> maxm=50000<\/span>;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5b9a\u4e49 maxm \u4e3a\u7ebf\u6bb5\u6700\u5927\u957f\u5ea6<\/span>\n 3<\/span>  2<\/span> \n 4<\/span>  3<\/span> int<\/span> a[maxm+5<\/span>],st[(maxm<<2<\/span>)+5<\/span>];\u3000\u3000\u3000\u3000\/\/<\/span> a \u6570\u7ec4\u4e3a main \u51fd\u6570\u4e2d\u8bfb\u5165\u7684\u5185\u5bb9\uff0cst \u6570\u7ec4\u4e3a\u9700\u8981\u67e5\u8be2\u7684\u6570\u7684\u4fe1\u606f\uff08\u5982\u548c\u3001\u6700\u503c\u7b49\uff09\uff0c\u6811\u7684\u7a7a\u95f4\u5927\u5c0f\u4e3a\u7ebf\u6bb5\u6700\u5927\u957f\u5ea6\u7684\u56db\u500d<\/span>\n 5<\/span>  4<\/span> \n 6<\/span>  5<\/span> void<\/span> build(int<\/span> o,int<\/span> l,int<\/span> r){\u3000\u3000\u3000\u3000\/\/<\/span>\u4f20\u5165\u7684\u53c2\u6570\u4e3a o:\u5f53\u524d\u9700\u8981\u5efa\u7acb\u7684\u7ed3\u70b9\uff1bl\uff1a\u5f53\u524d\u9700\u8981\u5efa\u7acb\u7684\u5de6\u7aef\u70b9\uff1br\uff1a\u5f53\u524d\u9700\u8981\u5efa\u7acb\u7684\u53f3\u7aef\u70b9<\/span>\n 7<\/span>  6<\/span>     if<\/span>(l==r)st[o]=a[l];\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5f53\u5de6\u7aef\u70b9\u7b49\u4e8e\u53f3\u7aef\u70b9\u5373\u5efa\u7acb\u53f6\u5b50\u7ed3\u70b9\u65f6\uff0c\u76f4\u63a5\u7ed9\u6570\u7ec4\u4fe1\u606f\u8d4b\u503c<\/span>\n 8<\/span>  7<\/span>     else<\/span>{\n<\/span> 9<\/span>  8<\/span>         int<\/span> m=l+((r-l)>>1<\/span>);\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span> m \u4e3a\u4e2d\u95f4\u70b9\uff0c\u5de6\u513f\u5b50\u7ed3\u70b9\u4e3a [l,m] \uff0c\u53f3\u513f\u5b50\u7ed3\u70b9\u4e3a [m+1,r]\uff1b<\/span>\n10<\/span>  9<\/span>         build(o<<1<\/span>,l,m);\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u6784\u5efa\u5de6\u513f\u5b50\u7ed3\u70b9<\/span>\n11<\/span> 10<\/span>         build((o<<1<\/span>)|1<\/span>,m+1<\/span>,r);\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u6784\u5efa\u53f3\u513f\u5b50\u7ed3\u70b9<\/span>\n12<\/span> 11<\/span>         st[o]=st[o<<1<\/span>]+st[(o<<1<\/span>)|1<\/span>];\u3000\u3000\/\/<\/span>\u9012\u5f52\u8fd4\u56de\u65f6\u7528\u513f\u5b50\u7ed3\u70b9\u66f4\u65b0\u7236\u8282\u70b9\uff0c\u6b64\u5904\u53ef\u8fdb\u884c\u66f4\u65b0\u6700\u5927\u503c\u3001\u6700\u5c0f\u503c\u3001\u533a\u95f4\u548c\u7b49\u64cd\u4f5c<\/span>\n13<\/span> 12<\/span>     }\n<\/span>14<\/span> 13<\/span> }\n<\/span>15<\/span> 14<\/span> \n16<\/span> 15<\/span> {\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5728 main \u51fd\u6570\u4e2d\u7684\u8bed\u53e5<\/span>\n17<\/span> 16<\/span>         build(1<\/span>,1<\/span>,n);\n<\/span>18<\/span> 17<\/span> }<\/pre>\n<\/div>\n
\n
 1<\/span> \/\/<\/span>\u5355\u70b9\u4fee\u6539<\/span>\n 2<\/span> void<\/span> update(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ind,int<\/span> ans){\u3000\u3000\/\/<\/span>o\u3001l\u3001r\u4e3a\u5f53\u524d\u66f4\u65b0\u5230\u7684\u7ed3\u70b9\u3001\u5de6\u53f3\u7aef\u70b9\uff0cind\u4e3a\u9700\u8981\u4fee\u6539\u7684\u53f6\u5b50\u7ed3\u70b9\u5de6\u7aef\u70b9\uff0cans\u4e3a\u9700\u8981\u4fee\u6539\u6210\u7684\u503c\uff1b<\/span>\n 3<\/span>     if<\/span>(l==r){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u5f53\u524d\u66f4\u65b0\u70b9\u7684\u5de6\u53f3\u7aef\u70b9\u76f8\u7b49\u5373\u5230\u53f6\u5b50\u7ed3\u70b9\u65f6\uff0c\u76f4\u63a5\u66f4\u65b0\u4fe1\u606f\u5e76\u8fd4\u56de<\/span>\n 4<\/span>         st[o]=ans;\n<\/span> 5<\/span>         return<\/span>;\n<\/span> 6<\/span>     }\n<\/span> 7<\/span>     int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span> 8<\/span>     if<\/span>(ind<=m){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u9700\u8981\u66f4\u65b0\u7684\u53f6\u5b50\u7ed3\u70b9\u5728\u5f53\u524d\u7ed3\u70b9\u7684\u5de6\u513f\u5b50\u7ed3\u70b9\u7684\u8303\u56f4\u5185\uff0c\u5219\u9012\u5f52\u66f4\u65b0\u5de6\u513f\u5b50\u7ed3\u70b9\uff0c\u5426\u5219\u66f4\u65b0\u53f3\u513f\u5b50\u7ed3\u70b9<\/span>\n 9<\/span>         update(o<<1<\/span>,l,m,ind,ans);\n<\/span>10<\/span>     }\n<\/span>11<\/span>     else<\/span>{\n<\/span>12<\/span>         update((o<<1<\/span>)|1<\/span>,m+1<\/span>,r,ind,ans);\n<\/span>13<\/span>     }\n<\/span>14<\/span>     st[o]=max(st[o<<1<\/span>],st[(o<<1<\/span>)|1<\/span>]);\/\/<\/span>\u9012\u5f52\u56de\u4e4b\u540e\u7528\u513f\u5b50\u7ed3\u70b9\u66f4\u65b0\u7236\u8282\u70b9\uff08\u6b64\u5904\u662f\u533a\u95f4\u6700\u5927\u503c\uff09<\/span>\n15<\/span> }\n<\/span>16<\/span> \n17<\/span> {\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5728main\u51fd\u6570\u4e2d\u7684\u8bed\u53e5<\/span>\n18<\/span>         update(1<\/span>,1<\/span>,n,ind,ans);\n<\/span>19<\/span> }<\/pre>\n<\/div>\n
\n
 1<\/span> \/\/<\/span>\u5355\u70b9\u4fee\u6539\u7684\u533a\u95f4\u67e5\u8be2<\/span>\n 2<\/span> int<\/span> query(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ql,int<\/span> qr){\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>ql\u3001qr\u4e3a\u9700\u8981\u67e5\u8be2\u7684\u533a\u95f4\u5de6\u53f3\u7aef\u70b9<\/span>\n 3<\/span>     if<\/span>(ql>r||qr<l) return<\/span> -1<\/span>;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u5f53\u524d\u7ed3\u70b9\u548c\u9700\u8981\u67e5\u627e\u7684\u533a\u95f4\u4e0d\u76f8\u4ea4\uff0c\u5219\u8fd4\u56de\u4e00\u4e2a\u5bf9\u4e8e\u533a\u95f4\u67e5\u8be2\u65e0\u5173\u7684\u503c\uff08\u5982\u6c42\u548c\u65f6\u8fd4\u56de0\uff0c\u6c42\u6700\u5927\u503c\u65f6\u8fd4\u56de-1\u7b49\uff09<\/span>\n 4<\/span>     if<\/span>(ql<=l&&qr>=r) return<\/span> st[o];\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u5f53\u524d\u7ed3\u70b9\u7684\u533a\u95f4\u88ab\u9700\u8981\u67e5\u8be2\u7684\u533a\u95f4\u8986\u76d6\uff0c\u5219\u8fd4\u56de\u5f53\u524d\u7ed3\u70b9\u7684\u4fe1\u606f<\/span>\n 5<\/span>     int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span> 6<\/span>     int<\/span> p1=query(o<<1<\/span>,l,m,ql,qr),p2=query((o<<1<\/span>)|1<\/span>,m+1<\/span>,r,ql,qr);\u3000\u3000\/\/<\/span>p1\u4e3a\u67e5\u8be2\u5de6\u513f\u5b50\u7ed3\u70b9\u5f97\u5230\u7684\u4fe1\u606f\uff0cp2\u4e3a\u67e5\u8be2\u53f3\u513f\u5b50\u7ed3\u70b9\u5f97\u5230\u7684\u4fe1\u606f<\/span>\n 7<\/span>     return<\/span> max(p1,p2);\u3000\u3000\u3000\u3000\/\/<\/span>\u7efc\u5408\u4e24\u4e2a\u513f\u5b50\u7ed3\u70b9\u7684\u4fe1\u606f\u5e76\u8fd4\u56de<\/span>\n 8<\/span> }\n<\/span> 9<\/span> \n10<\/span> {\u3000\u3000\u3000\u3000\/\/<\/span>main\u51fd\u6570\u4e2d\u7684\u8bed\u53e5<\/span>\n11<\/span>         printf(\"<\/span>%dn<\/span>\"<\/span>,query(1<\/span>,1<\/span>,n,a,b));\n<\/span>12<\/span> }<\/pre>\n<\/div>\n
\u7136\u540e\u662f\u7ebf\u6bb5\u6570\u7684\u533a\u95f4\u4fee\u6539\u4ee5\u53ca\u76f8\u5e94\u7684\u67e5\u8be2\uff1a<\/p>\n
\u533a\u95f4\u4fee\u6539\u7528\u5230\u4e86lazy\u7684\u601d\u60f3\uff0c\u5373\u5f53\u4e00\u4e2a\u533a\u95f4\u9700\u8981\u66f4\u65b0\u65f6\uff0c\u53ea\u9012\u5f52\u66f4\u65b0\u5230\u90a3\u4e00\u5c42\u7ed3\u70b9\uff0c\u5e76\u5c06\u5176\u4e0b\u5c42\u7ed3\u70b9\u6240\u9700\u8981\u66f4\u65b0\u7684\u4fe1\u606f\u4fdd\u5b58\u5728\u6570\u7ec4\u4e2d\uff0c\u7136\u540e\u8fd4\u56de\uff0c\u53ea\u6709\u5f53\u4e0b\u6b21\u904d\u5386\u5230\u90a3\u4e2a\u7ed3\u70b9\uff08\u66f4\u65b0\u8fc7\u7a0b\u4e2d\u6216\u67e5\u8be2\u8fc7\u7a0b\u4e2d\uff09\uff0c\u624d\u5c06\u90a3\u4e2a\u7ed3\u70b9\u7684\u4fee\u6539\u4fe1\u606f\u4f20\u9012\u4e0b\u53bb\uff0c\u8fd9\u6837\u5c31\u907f\u514d\u4e86\u533a\u95f4\u4fee\u6539\u7684\u6bcf\u4e2a\u503c\u7684\u4fee\u6539<\/p>\n
\u533a\u95f4\u4fee\u6539\uff08\u5305\u62ec\u533a\u95f4\u52a0\u503c\u548c\u533a\u95f4\u8d4b\u503c\uff09\u53ca\u76f8\u5e94\u67e5\u8be2\uff1a<\/p>\n
\n
 1<\/span> \/\/<\/span>\u533a\u95f4\u52a0\u503c<\/span>\n 2<\/span> void<\/span> pushup(int<\/span> o){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>pushup\u51fd\u6570\uff0c\u8be5\u51fd\u6570\u672c\u8eab\u662f\u5c06\u5f53\u524d\u7ed3\u70b9\u7528\u5de6\u53f3\u5b50\u8282\u70b9\u7684\u4fe1\u606f\u66f4\u65b0\uff0c\u6b64\u5904\u6c42\u533a\u95f4\u548c\uff0c\u7528\u4e8eupdate\u4e2d\u5c06\u7ed3\u70b9\u4fe1\u606f\u4f20\u9012\u5b8c\u8fd4\u56de\u540e\u66f4\u65b0\u7236\u8282\u70b9<\/span>\n 3<\/span>     st[o]=st[o<<1<\/span>]+st[o<<1<\/span>|1<\/span>];\n<\/span> 4<\/span> }\n<\/span> 5<\/span>   \n 6<\/span> void<\/span> pushdown(int<\/span> o,int<\/span> l,int<\/span> r){\u3000\u3000\/\/<\/span>pushdown\u51fd\u6570\uff0c\u5c06o\u7ed3\u70b9\u7684\u4fe1\u606f\u4f20\u9012\u5230\u5de6\u53f3\u5b50\u8282\u70b9\u4e0a<\/span>\n 7<\/span>     if<\/span>(add[o]){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5f53\u7236\u8282\u70b9\u6709\u66f4\u65b0\u4fe1\u606f\u65f6\u624d\u5411\u4e0b\u4f20\u9012\u4fe1\u606f<\/span>\n 8<\/span>         add[o<<1<\/span>]+=add[o];\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5de6\u53f3\u513f\u5b50\u7ed3\u70b9\u5747\u52a0\u4e0a\u7236\u8282\u70b9\u7684\u66f4\u65b0\u503c<\/span>\n 9<\/span>         add[o<<1<\/span>|1<\/span>]+=add[o];\n<\/span>10<\/span>         int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>11<\/span>         st[o<<1<\/span>]+=add[o]*(m-l+1<\/span>);\u3000\u3000\/\/<\/span>\u5de6\u53f3\u513f\u5b50\u7ed3\u70b9\u5747\u6309\u7167\u9700\u8981\u52a0\u7684\u503c\u603b\u548c\u66f4\u65b0\u7ed3\u70b9\u4fe1\u606f<\/span>\n12<\/span>         st[o<<1<\/span>|1<\/span>]+=add[o]*(r-m);\n<\/span>13<\/span>         add[o]=0<\/span>;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u4fe1\u606f\u4f20\u9012\u5b8c\u4e4b\u540e\u5c31\u53ef\u4ee5\u5c06\u7236\u8282\u70b9\u7684\u66f4\u65b0\u4fe1\u606f\u5220\u9664<\/span>\n14<\/span>     }\n<\/span>15<\/span> }\n<\/span>16<\/span>  \n17<\/span> void<\/span> update(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ql,int<\/span> qr,int<\/span> addv){\u3000\u3000\/\/<\/span>ql\u3001qr\u4e3a\u9700\u8981\u66f4\u65b0\u7684\u533a\u95f4\u5de6\u53f3\u7aef\u70b9\uff0caddv\u4e3a\u9700\u8981\u589e\u52a0\u7684\u503c<\/span>\n18<\/span>     if<\/span>(ql<=l&&qr>=r){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u4e0e\u5355\u70b9\u66f4\u65b0\u4e00\u6837\uff0c\u5f53\u5f53\u524d\u7ed3\u70b9\u88ab\u9700\u8981\u66f4\u65b0\u7684\u533a\u95f4\u8986\u76d6\u65f6<\/span>\n19<\/span>         add[o]+=addv;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u66f4\u65b0\u8be5\u7ed3\u70b9\u7684\u6240\u9700\u66f4\u65b0\u4fe1\u606f<\/span>\n20<\/span>         st[o]+=addv*(r-l+1<\/span>);\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u66f4\u65b0\u8be5\u7ed3\u70b9\u4fe1\u606f<\/span>\n21<\/span>         return<\/span>;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u6839\u636elazy\u601d\u60f3\uff0c\u7531\u4e8e\u4e0d\u9700\u8981\u904d\u5386\u5230\u4e0b\u5c42\u7ed3\u70b9\uff0c\u56e0\u6b64\u4e0d\u9700\u8981\u7ee7\u7eed\u5411\u4e0b\u66f4\u65b0\uff0c\u76f4\u63a5\u8fd4\u56de<\/span>\n22<\/span>     }\n<\/span>23<\/span>     \n24<\/span>     pushdown(o,l,r);\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5c06\u5f53\u524d\u7ed3\u70b9\u7684\u6240\u9700\u66f4\u65b0\u4fe1\u606f\u4f20\u9012\u5230\u4e0b\u4e00\u5c42\uff08\u5176\u5de6\u53f3\u513f\u5b50\u7ed3\u70b9\uff09<\/span>\n25<\/span>     int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>26<\/span>     if<\/span>(ql<=m)update(o<<1<\/span>,l,m,ql,qr,addv);\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5f53\u9700\u66f4\u65b0\u533a\u95f4\u5728\u5f53\u524d\u7ed3\u70b9\u7684\u5de6\u513f\u5b50\u7ed3\u70b9\u5185\uff0c\u5219\u66f4\u65b0\u5de6\u513f\u5b50\u7ed3\u70b9<\/span>\n27<\/span>     if<\/span>(qr>=m+1<\/span>)update(o<<1<\/span>|1<\/span>,m+1<\/span>,r,ql,qr,addv);\u3000\u3000\u3000\/\/<\/span>\u5f53\u9700\u66f4\u65b0\u533a\u95f4\u5728\u5f53\u524d\u7ed3\u70b9\u7684\u53f3\u513f\u5b50\u7ed3\u70b9\u5185\uff0c\u5219\u66f4\u65b0\u53f3\u513f\u5b50\u7ed3\u70b9<\/span>\n28<\/span>     pushup(o);\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u9012\u5f52\u56de\u4e0a\u5c42\u65f6\u4e00\u6b65\u4e00\u6b65\u66f4\u65b0\u56de\u7236\u8282\u70b9<\/span>\n29<\/span> }\n<\/span>30<\/span> \n31<\/span> ll query(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ql,int<\/span> qr){\u3000\u3000\u3000\u3000\/\/<\/span>ql\u3001qr\u4e3a\u9700\u8981\u67e5\u8be2\u7684\u533a\u95f4<\/span>\n32<\/span>     if<\/span>(ql<=l&&qr>=r) return<\/span> st[o];\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u5f53\u524d\u7ed3\u70b9\u8986\u76d6\u533a\u95f4\u5373\u4e3a\u9700\u8981\u67e5\u8be2\u7684\u533a\u95f4\uff0c\u5219\u76f4\u63a5\u8fd4\u56de\u5f53\u524d\u7ed3\u70b9\u7684\u4fe1\u606f<\/span>\n33<\/span>     pushdown(o,l,r);\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u5c06\u5f53\u524d\u7ed3\u70b9\u7684\u66f4\u65b0\u4fe1\u606f\u4f20\u9012\u7ed9\u5176\u5de6\u53f3\u5b50\u8282\u70b9<\/span>\n34<\/span>     int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>35<\/span>     ll ans=0<\/span>;\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u6240\u9700\u67e5\u8be2\u7684\u7ed3\u679c<\/span>\n36<\/span>     if<\/span>(ql<=m)ans+=query(o<<1<\/span>,l,m,ql,qr);\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u82e5\u6240\u9700\u67e5\u8be2\u7684\u533a\u95f4\u4e0e\u5f53\u524d\u7ed3\u70b9\u7684\u5de6\u5b50\u8282\u70b9\u6709\u4ea4\u96c6\uff0c\u5219\u7ed3\u679c\u52a0\u4e0a\u67e5\u8be2\u5176\u5de6\u5b50\u8282\u70b9\u7684\u7ed3\u679c<\/span>\n37<\/span>     if<\/span>(qr>=m+1<\/span>)ans+=query(o<<1<\/span>|1<\/span>,m+1<\/span>,r,ql,qr);\u3000\/\/<\/span>\u82e5\u6240\u9700\u67e5\u8be2\u7684\u533a\u95f4\u4e0e\u5f53\u524d\u7ed3\u70b9\u7684\u53f3\u5b50\u8282\u70b9\u6709\u4ea4\u96c6\uff0c\u5219\u7ed3\u679c\u52a0\u4e0a\u67e5\u8be2\u5176\u53f3\u5b50\u8282\u70b9\u7684\u7ed3\u679c<\/span>\n38<\/span> \u3000\u3000 return<\/span> ans; \n<\/span>39<\/span> }<\/pre>\n<\/div>\n
\n
 1<\/span> \/\/<\/span>\u533a\u95f4\u6539\u503c\uff08\u5176\u5b9e\u53ea\u6709pushdow\u51fd\u6570\u548cupdate\u4e2d\u4fee\u6539\u90e8\u5206\u4e0e\u533a\u95f4\u52a0\u503c\u4e0d\u540c\uff09<\/span>\n 2<\/span> void<\/span> pushup(int<\/span> o){\n<\/span> 3<\/span>      st[o]=st[o<<1<\/span>]+st[o<<1<\/span>|1<\/span>];\n<\/span> 4<\/span>  }\n<\/span> 5<\/span>  \n 6<\/span>  void<\/span> pushdown(int<\/span> o,int<\/span> l,int<\/span> r){\u3000\u3000\/\/<\/span>pushdown\u548c\u533a\u95f4\u52a0\u503c\u4e0d\u540c\uff0c\u6539\u503c\u65f6\u4fee\u6539\u7ed3\u70b9\u4fe1\u606f\u53ea\u9700\u8981\u5bf9\u4fee\u6539\u540e\u7684\u4fe1\u606f\u6c42\u548c\u5373\u53ef\uff0c\u4e0d\u7528\u52a0\u4e0a\u539f\u4fe1\u606f<\/span>\n 7<\/span>      if<\/span>(change[o]){\n<\/span> 8<\/span>          int<\/span> c=change[o];\n<\/span> 9<\/span>          change[o<<1<\/span>]=c;\n<\/span>10<\/span>          change[o<<1<\/span>|1<\/span>]=c;\n<\/span>11<\/span>          int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>12<\/span>          st[o<<1<\/span>]=(m-l+1<\/span>)*c;\n<\/span>13<\/span>          st[o<<1<\/span>|1<\/span>]=(r-m)*c;\n<\/span>14<\/span>          change[o]=0<\/span>;\n<\/span>15<\/span>      }\n<\/span>16<\/span>  }\n<\/span>17<\/span>  \n18<\/span>  void<\/span> update(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ql,int<\/span> qr,int<\/span> c){\n<\/span>19<\/span>      if<\/span>(ql<=l&&qr>=r){\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\u3000\/\/<\/span>\u540c\u6837\u66f4\u65b0\u7ed3\u70b9\u4fe1\u606f\u548c\u533a\u95f4\u52a0\u503c\u4e0d\u540c<\/span>\n20<\/span>          change[o]=c;\n<\/span>21<\/span>          st[o]=(r-l+1<\/span>)*c;\n<\/span>22<\/span>          return<\/span>;\n<\/span>23<\/span>      }\n<\/span>24<\/span>      \n25<\/span>      pushdown(o,l,r);\n<\/span>26<\/span>      int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>27<\/span>      if<\/span>(ql<=m)update(o<<1<\/span>,l,m,ql,qr,c);\n<\/span>28<\/span>      if<\/span>(qr>=m+1<\/span>)update(o<<1<\/span>|1<\/span>,m+1<\/span>,r,ql,qr,c);\n<\/span>29<\/span>      pushup(o);\n<\/span>30<\/span>  }\n<\/span>31<\/span>  \n32<\/span>  int<\/span> query(int<\/span> o,int<\/span> l,int<\/span> r,int<\/span> ql,int<\/span> qr){\n<\/span>33<\/span>      if<\/span>(ql<=l&&qr>=r) return<\/span> st[o];\n<\/span>34<\/span>      pushdown(o,l,r);\n<\/span>35<\/span>      int<\/span> m=l+((r-l)>>1<\/span>);\n<\/span>36<\/span>      int<\/span> ans=0<\/span>;\n<\/span>37<\/span>      if<\/span>(ql<=m)ans+=query(o<<1<\/span>,l,m,ql,qr);\n<\/span>38<\/span>      if<\/span>(qr>=m+1<\/span>)ans+=query(o<<1<\/span>|1<\/span>,m+1<\/span>,r,ql,qr);\n<\/span>39<\/span>      return<\/span> ans;\n<\/span>40<\/span>  }<\/pre>\n<\/div>\n
\u770b\u5230\u597d\u7684\u94fe\u63a5\uff1ahttps:\/\/blog.csdn.net\/zxzxzx0119\/article\/details\/79838261<\/a><\/p>\n
acwing\u6a21\u677f:https:\/\/www.acwing.com\/activity\/content\/11\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
string \u64cd\u4f5c\uff1a 1 =,assign() \/\/\u8d4b\u4ee5\u65b0\u503c 2 s.assign(str […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"\n\u4e00\u4e9b\u6a21\u677f - imwarming<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/imwarming.com\/?p=194\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u4e00\u4e9b\u6a21\u677f - imwarming\" \/>\n<meta property=\"og:description\" content=\"string \u64cd\u4f5c\uff1a 1 =,assign() \/\/\u8d4b\u4ee5\u65b0\u503c 2 s.assign(str […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/imwarming.com\/?p=194\" \/>\n<meta property=\"og:site_name\" content=\"imwarming\" \/>\n<meta property=\"article:published_time\" content=\"2019-08-07T13:28:00+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"warming\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/imwarming.com\/#website\",\"url\":\"https:\/\/imwarming.com\/\",\"name\":\"imwarming\",\"description\":\"\u6c38\u8fdc\u5e74\u8f7b\uff0c\u6c38\u8fdc\u70ed\u6cea\u76c8\u7736\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/imwarming.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/imwarming.com\/?p=194#webpage\",\"url\":\"https:\/\/imwarming.com\/?p=194\",\"name\":\"\u4e00\u4e9b\u6a21\u677f - imwarming\",\"isPartOf\":{\"@id\":\"https:\/\/imwarming.com\/#website\"},\"datePublished\":\"2019-08-07T13:28:00+00:00\",\"dateModified\":\"2019-08-07T13:28:00+00:00\",\"author\":{\"@id\":\"https:\/\/imwarming.com\/#\/schema\/person\/9d76869a558bac6dd0d6d58f420ee8ea\"},\"breadcrumb\":{\"@id\":\"https:\/\/imwarming.com\/?p=194#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/imwarming.com\/?p=194\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/imwarming.com\/?p=194#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/imwarming.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u4e00\u4e9b\u6a21\u677f\"}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/imwarming.com\/#\/schema\/person\/9d76869a558bac6dd0d6d58f420ee8ea\",\"name\":\"warming\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/imwarming.com\/#personlogo\",\"inLanguage\":\"zh-Hans\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/c4a913eed88f7601b76bbf2b103472621195b6fa2f742af89b5ea185b60e7cff?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/c4a913eed88f7601b76bbf2b103472621195b6fa2f742af89b5ea185b60e7cff?s=96&d=mm&r=g\",\"caption\":\"warming\"},\"sameAs\":[\"https:\/\/imwarming.com\"],\"url\":\"https:\/\/imwarming.com\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u4e00\u4e9b\u6a21\u677f - imwarming","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/imwarming.com\/?p=194","og_locale":"zh_CN","og_type":"article","og_title":"\u4e00\u4e9b\u6a21\u677f - imwarming","og_description":"string \u64cd\u4f5c\uff1a 1 =,assign() \/\/\u8d4b\u4ee5\u65b0\u503c 2 s.assign(str […]","og_url":"https:\/\/imwarming.com\/?p=194","og_site_name":"imwarming","article_published_time":"2019-08-07T13:28:00+00:00","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"warming","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"7 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebSite","@id":"https:\/\/imwarming.com\/#website","url":"https:\/\/imwarming.com\/","name":"imwarming","description":"\u6c38\u8fdc\u5e74\u8f7b\uff0c\u6c38\u8fdc\u70ed\u6cea\u76c8\u7736","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/imwarming.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":"WebPage","@id":"https:\/\/imwarming.com\/?p=194#webpage","url":"https:\/\/imwarming.com\/?p=194","name":"\u4e00\u4e9b\u6a21\u677f - imwarming","isPartOf":{"@id":"https:\/\/imwarming.com\/#website"},"datePublished":"2019-08-07T13:28:00+00:00","dateModified":"2019-08-07T13:28:00+00:00","author":{"@id":"https:\/\/imwarming.com\/#\/schema\/person\/9d76869a558bac6dd0d6d58f420ee8ea"},"breadcrumb":{"@id":"https:\/\/imwarming.com\/?p=194#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/imwarming.com\/?p=194"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/imwarming.com\/?p=194#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/imwarming.com\/"},{"@type":"ListItem","position":2,"name":"\u4e00\u4e9b\u6a21\u677f"}]},{"@type":"Person","@id":"https:\/\/imwarming.com\/#\/schema\/person\/9d76869a558bac6dd0d6d58f420ee8ea","name":"warming","image":{"@type":"ImageObject","@id":"https:\/\/imwarming.com\/#personlogo","inLanguage":"zh-Hans","url":"https:\/\/secure.gravatar.com\/avatar\/c4a913eed88f7601b76bbf2b103472621195b6fa2f742af89b5ea185b60e7cff?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c4a913eed88f7601b76bbf2b103472621195b6fa2f742af89b5ea185b60e7cff?s=96&d=mm&r=g","caption":"warming"},"sameAs":["https:\/\/imwarming.com"],"url":"https:\/\/imwarming.com\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/imwarming.com\/index.php?rest_route=\/wp\/v2\/posts\/194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/imwarming.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/imwarming.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/imwarming.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/imwarming.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=194"}],"version-history":[{"count":0,"href":"https:\/\/imwarming.com\/index.php?rest_route=\/wp\/v2\/posts\/194\/revisions"}],"wp:attachment":[{"href":"https:\/\/imwarming.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/imwarming.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/imwarming.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}