[{"type":"Paragraph","children":[{"text":"大家好，我是一个算法爱好者。今后我会分享一些还不错/典型/值得学习的题，难度从mid - hard - 竞赛都有。欢迎关注哦"}],"slateId":"gIwNYQcb2cReUhfdKXZBO"},{"type":"Paragraph","slateId":"Vlye1pImJ3-7dOaCZZPb-","children":[{"text":"这是我的第一篇分享，题目来源 2023-2024 ICPC亚洲雅加达区域赛"}]},{"type":"Paragraph","slateId":"jgz59NhL367RF-NwxCLX3","children":[{"text":""},{"type":"Link","href":"https://codeforces.com/contest/1906/problem/F","title":"链接: Maximize The Value","children":[{"text":""}],"slateId":"kHs5ylBZYZM9rfHSc_BaF"},{"text":""}]},{"type":"Heading1","children":[{"text":"描述"}],"slateId":"x58O05Vvpm4f_ogs_EuS7"},{"type":"Paragraph","children":[{"text":"给定一个由 "},{"type":"Latex","tex":"N","children":[{"text":""}],"slateId":"hswCEQ9pmBF3fJxA1_YHo"},{"text":" 个整数构成的一维数组 "},{"type":"Latex","tex":"A_1, A_2, \\cdots, A_N","children":[{"text":""}],"slateId":"kScwslE3MC3lw3Pm5ibE1"},{"text":"，初始时每个元素的值均为 "},{"type":"Latex","tex":"0","children":[{"text":""}],"slateId":"1r5KA2hos5vZEZuxntlTd"},{"text":"。"}],"slateId":"VYT6dYOn8TwCD2StxvfNA"},{"type":"Paragraph","children":[{"text":"有 "},{"type":"Latex","tex":"M","children":[{"text":""}],"slateId":"oovQngZ64RtpzX8fv7yoX"},{"text":" 个操作（编号从 "},{"type":"Latex","tex":"1","children":[{"text":""}],"slateId":"7oMMFLvPjcSOTlmNJ917v"},{"text":" 到 "},{"type":"Latex","tex":"M","children":[{"text":""}],"slateId":"t0YEbAscuBEIKfUq6IDYo"},{"text":"）。第 "},{"type":"Latex","tex":"i","children":[{"text":""}],"slateId":"6mlzlOYqMIqiLAqh7zmdz"},{"text":" 个操作表示为 "},{"type":"Latex","tex":"\\langle L_i, R_i, X_i \\rangle","children":[{"text":""}],"slateId":"s52DwgblerYxuVLIEH-Ix"},{"text":"。执行第 "},{"type":"Latex","tex":"i","children":[{"text":""}],"slateId":"6nbhYvsHTrbm_SfPR1bp9"},{"text":" 个操作时，所有满足 "},{"type":"Latex","tex":"L_i \\leq j \\leq R_i","children":[{"text":""}],"slateId":"Zi2Dw1kOmotRaVMDvQNd2"},{"text":" 的 "},{"type":"Latex","tex":"A_j","children":[{"text":""}],"slateId":"igzcWkU6aO9o5mbpD-0Di"},{"text":" 都会增加 "},{"type":"Latex","tex":"X_i","children":[{"text":""}],"slateId":"HY0QUiy9WDUujuAVU-9Sb"},{"text":"。"}],"slateId":"TmXKWeLcH3ZmdM9Xl-_Z4"},{"type":"Paragraph","children":[{"text":"你需要回答 "},{"type":"Latex","tex":"Q","children":[{"text":""}],"slateId":"uefTDKNjISDMxJbTWaffD"},{"text":" 个独立的询问。每个询问表示为 "},{"type":"Latex","tex":"\\langle K, S, T \\rangle","children":[{"text":""}],"slateId":"82FfrpTPmDuwZuB6IMBKX"},{"text":"，其含义如下：选择一个区间 "},{"type":"Latex","tex":"[l, r]","children":[{"text":""}],"slateId":"Vm-9oOg_ctDvIU2Gg7zY8"},{"text":"，满足 "},{"type":"Latex","tex":"S \\leq l \\leq r \\leq T","children":[{"text":""}],"slateId":"ATo386b_p7xxum6Sdt_Ej"},{"text":"，并依次执行操作 "},{"type":"Latex","tex":"l, l+1, \\dots, r","children":[{"text":""}],"slateId":"SvTcEo8YjUyD6xD9xfMOg"},{"text":"。对于所有可能的 "},{"type":"Latex","tex":"l","children":[{"text":""}],"slateId":"2Vsyl7_4TPoG4jdDKkhuI"},{"text":" 和 "},{"type":"Latex","tex":"r","children":[{"text":""}],"slateId":"ZvSncS4Gpm0GWUM5UormU"},{"text":"，询问的答案为执行这些操作后 "},{"type":"Latex","tex":"A_K","children":[{"text":""}],"slateId":"y5ZD3f0ndaoF--oK3dKto"},{"text":" 的最大值。"}],"slateId":"DVF3i-8AKWMsJ4sEkLD1Y"},{"type":"Paragraph","children":[{"text":""},{"type":"Span","children":[{"text":"输入","italic":true}],"slateId":"Ff96qc26LLUiRL9iWWYVn"},{"text":""}],"slateId":"gW88I_sIEOjBkHYBrDa-F"},{"type":"Paragraph","children":[{"text":"第一行包含两个整数 "},{"type":"Latex","tex":"N","children":[{"text":""}],"slateId":"5sAWMEWdOnKAVmCETZJwz"},{"text":" 和 "},{"type":"Latex","tex":"M","children":[{"text":""}],"slateId":"LOzzJ0kw6B610ufdUaGA2"},{"text":"（"},{"type":"Latex","tex":"1 \\leq N, M \\leq 10^5","children":[{"text":""}],"slateId":"PpGIy96oew4QYGwyg6m4i"},{"text":"）。\n接下来的 "},{"type":"Latex","tex":"M","children":[{"text":""}],"slateId":"oWc43KUU_FuBk-hELKRuS"},{"text":" 行，每行包含三个整数 "},{"type":"Latex","tex":"L_i","children":[{"text":""}],"slateId":"a5YNm_4651iP7itQmTVQE"},{"text":"、"},{"type":"Latex","tex":"R_i","children":[{"text":""}],"slateId":"e6bMUfrnRyJIE4AOgnD7x"},{"text":"、"},{"type":"Latex","tex":"X_i","children":[{"text":""}],"slateId":"JUFcCEyCKMpqGUHoeZFxG"},{"text":"（"},{"type":"Latex","tex":"1 \\leq L_i \\leq R_i \\leq N; -100\\,000 \\leq X_i \\leq 100\\,000","children":[{"text":""}],"slateId":"QYIIByg99mj4wW-zEGos0"},{"text":"）。\n接下来一行包含一个整数 "},{"type":"Latex","tex":"Q","children":[{"text":""}],"slateId":"XFIXEDVqbYkian8_bi6fG"},{"text":"（"},{"type":"Latex","tex":"1 \\leq Q \\leq 10^5","children":[{"text":""}],"slateId":"i8IcbYxP4R4t7pqwWH630"},{"text":"）。\n接下来的 "},{"type":"Latex","tex":"Q","children":[{"text":""}],"slateId":"QtqcaksM8KgfaxHBQp3Np"},{"text":" 行，每行包含三个整数 "},{"type":"Latex","tex":"K","children":[{"text":""}],"slateId":"tHNlIfd2jV9CumUdq14Qo"},{"text":"、"},{"type":"Latex","tex":"S","children":[{"text":""}],"slateId":"_0KEBLQ07lB9W9SVUdyJ1"},{"text":"、"},{"type":"Latex","tex":"T","children":[{"text":""}],"slateId":"Hhyb5hVW1pDGAS2Hb9YDH"},{"text":"（"},{"type":"Latex","tex":"1 \\leq K \\leq N; 1 \\leq S \\leq T \\leq M","children":[{"text":""}],"slateId":"h-qc5ZWnM1nrK8v4IKSlI"},{"text":"）。\n"},{"type":"Span","children":[{"text":"输出","italic":true}],"slateId":"gYTdoXcxfga-_YMaHr45g"},{"text":"\n对于每个询问，输出一行，表示该询问的答案。\n"},{"type":"Span","children":[{"text":"样例","italic":true}],"slateId":"SC7-twcGQrN-WIcH20wuv"},{"text":" "}],"slateId":"0HEOl8BXJTDK2kY5hCGqw"},{"type":"Paragraph","children":[{"text":""},{"type":"Span","children":[{"text":"输入","bold":true}],"slateId":"KW6MXtHTzwnt14URMyvSm"},{"text":" "}],"slateId":"sRufrUVTs-gLecpCyuQ_U"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"plainText","name":"","children":[{"text":"2 6\n1 1 -50\n1 2 -20\n2 2 -30\n1 1 60\n1 2 40\n2 2 10\n5\n1 1 6\n2 1 6\n1 1 3\n2 1 3\n1 1 2"}],"slateId":"p_CmRk_2DnLtIymi3Ma0q"}],"slateId":"kqi0oiW9e3XVqo1zy6uX_"},{"type":"Paragraph","children":[{"text":""},{"type":"Span","children":[{"text":"输出","bold":true}],"slateId":"tdkLAaKiMaAP9VTxjENMS"},{"text":" "}],"slateId":"GDgs6Gq1FTCsWT6Vfr2d5"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"plainText","name":"","children":[{"text":"100\n50\n0\n0\n-20"}],"slateId":"XnapvZe-p8a8oDGW11WtQ"}],"slateId":"Ty-ZNiAhnQDdudRZRuqKZ"},{"type":"Paragraph","children":[{"text":""},{"type":"Span","children":[{"text":"说明","bold":true}],"slateId":"ZwKNYzBKroL8k86ZmiZBX"},{"text":"\n样例输入输出说明：\n对于第 "},{"type":"Latex","tex":"1","children":[{"text":""}],"slateId":"hq-fJxobGUoN1v50Rio7J"},{"text":" 个询问，其中一种方案是执行操作 "},{"type":"Latex","tex":"4","children":[{"text":""}],"slateId":"EoQel0ryBUjpspQoGKLFH"},{"text":" 和 "},{"type":"Latex","tex":"5","children":[{"text":""}],"slateId":"gmkPpUCREywGohXVimyIW"},{"text":"。\n对于第 "},{"type":"Latex","tex":"2","children":[{"text":""}],"slateId":"plC0D3M2T8WznKtloWHk9"},{"text":" 个询问，其中一种方案是执行操作 "},{"type":"Latex","tex":"4","children":[{"text":""}],"slateId":"wq3pRlI1RyN6092PSgnCs"},{"text":"、"},{"type":"Latex","tex":"5","children":[{"text":""}],"slateId":"-WInwzor_ee2XR5RnFaiT"},{"text":" 和 "},{"type":"Latex","tex":"6","children":[{"text":""}],"slateId":"4TiUfwUWqmJUOG4EuKS74"},{"text":"。\n对于第 "},{"type":"Latex","tex":"3","children":[{"text":""}],"slateId":"hzecQ-R0qHsgmNYssLxzN"},{"text":" 个询问，唯一的方案是执行操作 "},{"type":"Latex","tex":"3","children":[{"text":""}],"slateId":"s8YnsFTvTQIJ1os2ku7xS"},{"text":"。\n对于第 "},{"type":"Latex","tex":"4","children":[{"text":""}],"slateId":"X0VltbSBFrgimAasIFOj7"},{"text":" 个询问，唯一的方案是执行操作 "},{"type":"Latex","tex":"1","children":[{"text":""}],"slateId":"J_xGR2xWveo2vDvUZMhbb"},{"text":"。\n对于第 "},{"type":"Latex","tex":"6","children":[{"text":""}],"slateId":"fKTrhrDQOUv6ROsD1RZYG"},{"text":" 个询问，唯一的方案是执行操作 "},{"type":"Latex","tex":"2","children":[{"text":""}],"slateId":"a-qbD1Pg8p26QeIoKR8-A"},{"text":"。"}],"slateId":"-dKQt25fVl861MYfM81IO"},{"type":"Heading2","children":[{"text":"思路"}],"slateId":"B7kVjH0ychq7v7YEw_zwE"},{"type":"Paragraph","children":[{"text":"A[K]","code":true},{"text":" 的最终值，只取决于哪些操作覆盖了位置 "},{"text":"K","code":true},{"text":"。\n 对于操作 "},{"text":"i","code":true},{"text":"，它对 "},{"text":"A[K]","code":true},{"text":" 的贡献是："}],"slateId":"03WjZrOJ3xz_UbIW2G1Qi"},{"type":"LatexBlock","tex":"contrib_i(K) = \n\\begin{cases}\nX_i, & \\text{if } L_i \\leq K \\leq R_i \\\\\n0, & \\text{otherwise}\n\\end{cases}","children":[{"text":""}],"slateId":"knXHdYBHA7SdE-OffOQ8r"},{"type":"Paragraph","children":[{"text":"于是，对固定的 "},{"text":"K","code":true},{"text":"，我们可以构造一个长度为 "},{"text":"M","code":true},{"text":" 的贡献序列 "},{"type":"Latex","tex":"C_K[1..M]","children":[{"text":""}],"slateId":"FgfK2cniu_pbTefcpDSFz"},{"text":"，其中："}],"slateId":"6jxpq80zkMmqmD1Xl91oq"},{"type":"BulletedList","children":[{"type":"ListItem","children":[{"text":""},{"type":"Latex","tex":"C_K[i] = X_i","children":[{"text":""}],"slateId":"Sz3T_FaMC_W9zMmOpn0A6"},{"text":"，如果操作 "},{"text":"i","code":true},{"text":" 覆盖 "},{"text":"K","code":true}],"slateId":"TQlwuADqvQ＊＊＊rluE7IAo"},{"type":"ListItem","children":[{"text":""},{"type":"Latex","tex":"C_K[i] = 0","children":[{"text":""}],"slateId":"LznoX8FebZTLoX2Twz5u3"},{"text":"，否则"}],"slateId":"CuX8iCMtp66f032mGIh_4"}],"slateId":"TGV7ThOBcQGRJ-iHV7rC8"},{"type":"Paragraph","children":[{"text":"那么，在操作区间 "},{"text":"[S, T]","code":true},{"text":" 中选连续子区间 "},{"text":"[l, r]","code":true},{"text":" 执行，等价于在 "},{"type":"Latex","tex":"C_K[S..T]","children":[{"text":""}],"slateId":"K6hrbvrbi_Qc5Cj8hgMq8"},{"text":" 中选一个子数组，使其和最大！\n那么，如何维护贡献序列"},{"type":"Latex","tex":"C_k","children":[{"text":""}],"slateId":"UQ8owyBLhZbi7oM_fteT5"},{"text":"，考虑将询问离线后进行扫描线处理\n具体:\n 离线所有查询,将所有查询按 "},{"type":"Latex","tex":"K","children":[{"text":""}],"slateId":"16LR7IMfWvqsROBcws5Am"},{"text":" 升序排序,同时，将所有操作按 "},{"type":"Latex","tex":"L_i","children":[{"text":""}],"slateId":"OR9IkXmX3Tlx37OClxKdE"},{"text":" 升序排序。从左到右扫描 "},{"type":"Latex","tex":"K = 1 → N","children":[{"text":""}],"slateId":"pRmj4-A-Ekv8GI_rPYfmd"},{"text":",用一个小根堆维护当前激活和撤销的操作，一旦"},{"type":"Latex","tex":"L_i<=K","children":[{"text":""}],"slateId":"uXtL5zmovYqk8NEGZaiLe"},{"text":"，当前操作就对"},{"type":"Latex","tex":"C_k","children":[{"text":""}],"slateId":"9RsFrMno_e0TLqKg4VwrV"},{"text":"序列有贡献，插入堆并在"},{"type":"Latex","tex":"C_k","children":[{"text":""}],"slateId":"hoyvI2CpM91_oAG9kEp2E"},{"text":"序列对应处加上贡献。堆顶为此时最小的"},{"type":"Latex","tex":"R_i","children":[{"text":""}],"slateId":"Ocl9JBykq9N_yIw4goSPo"},{"text":",一旦堆顶 "},{"type":"Latex","tex":"R_i < K","children":[{"text":""}],"slateId":"lAe54aOTbz9fOBoiqpP5k"},{"text":" 就弹出并撤销贡献。\n要在"},{"type":"Latex","tex":"C_K[S..T]","children":[{"text":""}],"slateId":"oesAd4ieZ_Tvfh-rGcm9Y"},{"text":" 中选一个子数组，使其和最大。"},{"type":"Latex","tex":"C_k","children":[{"text":""}],"slateId":"TY6rjXAHPSmHYX723BUNA"},{"text":"是动态维护和查询的，因此需要 "},{"type":"Latex","tex":"最大子段和线段树","children":[{"text":""}],"slateId":"w2dyyUnl7EqdTBD6KAtNu"},{"text":"("},{"type":"Link","href":"https://www.luogu.com.cn/problem/P4513","title":"点击看模板题","children":[{"text":""}],"slateId":"lDmvyCVVPpUpb0K3ZQgWM"},{"text":")，来维护"},{"type":"Latex","tex":"C_k","children":[{"text":""}],"slateId":"-2vqS7SorUPf8dsfAH35T"},{"text":"序列，即在激活/撤销操作时对操作编号处单点加上/减去贡献。对于询问<"},{"type":"Latex","tex":"K,S,T","children":[{"text":""}],"slateId":"Id3zKksIFopO1yST2s_nL"},{"text":"> 查询"},{"type":"Latex","tex":"[S,T]","children":[{"text":""}],"slateId":"UE5t80B7_9y-dbURD1zOu"},{"text":"内最大子段和即为"},{"type":"Latex","tex":"A_k","children":[{"text":""}],"slateId":"OVL35STIZ2sRBcV9kkHH0"},{"text":"最大值"}],"slateId":"LgS-Jza4oHLHWUiEVPp-t"},{"type":"CodeBlock","activeTabIndex":0,"children":[{"type":"CodeTab","language":"cpp","name":"","children":[{"text":"using ll = long long;\nusing pii = pair;\nconst ll INF=1e10+2;\nconst int maxn=1e5+20;\ntemplatestruct Segment_tree{ \n struct Tree{ \n int l,r; \n ll lmx=-INF,rmx=-INF,mx=-INF;\n ll sum=-INF;\n }tr[N*4];\n void push_up(Tree& pa,Tree& ls,Tree& rs){\n pa.mx=max(max(ls.mx,rs.mx),ls.rmx+rs.lmx);\n pa.lmx=max(ls.lmx,ls.sum+rs.lmx);\n pa.rmx=max(rs.rmx,rs.sum+ls.rmx);\n pa.sum=ls.sum+rs.sum;\n return;\n }\n void Build(int p,int lo,int ro, const vector& init = {}){ \n tr[p].l=lo,tr[p].r=ro; \n if(lo==ro){ \n ll _v = init.empty() ? ll(0) : init[lo];\n tr[p].lmx=tr[p].rmx=tr[p].mx=_v; \n tr[p].sum=_v;\n return; \n } \n int mid=(lo+ro)>>1; \n Build(lson,lo,mid,init); \n Build(rson,mid+1,ro,init); \n push_up(tr[p],tr[lson],tr[rson]);\n } \n void Fix(int p,int k,ll x){ //k点单点加x\n if(tr[p].l==tr[p].r){\n tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=tr[p].sum+x;\n return;\n } \n int ndmid=(tr[p].l+tr[p].r)>>1; \n if(k<=ndmid) Fix(lson,k,x); \n else Fix(rson,k,x); \n push_up(tr[p],tr[lson],tr[rson]);\n } \n Tree query(int p,int lo,int ro){ \n if(lo<=tr[p].l && ro>=tr[p].r) return tr[p]; \n Tree res,lres,rres;\n int ndmid=(tr[p].l+tr[p].r)>>1; \n if(lo<=ndmid) lres=query(lson,lo,ro);\n if(ro>ndmid) rres=query(rson,lo,ro); \n push_up(res,lres,rres);\n return res; \n } \n ll Ask(int l,int r){ //查l~r的最大子段和\n return query(1,l,r).mx;\n }\n}; \nstruct Z1{\n int L,R,id;\n};\nstruct Z2{\n int K,X,T,id;\n};\nZ1 a[maxn];\nZ2 b[maxn];\nll ans[maxn],val[maxn];\nSegment_tree Te;\nvoid solve(){\n\tint n,m;\n\tcin >> n >> m;\n Te.Build(1,1,m);\n for(int i=1;i<=m;++i){\n auto& [L,R,id]=a[i];\n cin >> L >> R >> val[i];\n id=i;\n }\n int q;\n cin >> q;\n for(int i=1;i<=q;++i){\n auto& [k,x,t,id]=b[i];\n cin >> k >> x >> t;\n id=i;\n }\n sort(a+1,a+1+m,[&](Z1& t1,Z1& t2){\n return t1.L,greater> pq; \n for(int i=1,j=0;i<=q;++i){\n auto [K,X,T,id]=b[i];\n while(j+1<=m && a[j+1].L<=K){\n pq.push({a[j+1].R,a[j+1].id});\n Te.Fix(1,a[j+1].id,val[a[j+1].id]);\n ++j;\n }\n while(!pq.empty() && pq.top().ft<=K-1){\n Te.Fix(1,pq.top().sd,-val[pq.top().sd]);\n pq.pop();\n }\n ans[id]=Te.Ask(X,T);\n }\n for(int i=1;i<=q;++i) cout << ans[i] << '\\n';\n}"}],"slateId":"zKVkoGRu7zo9q1I0DkqxT"}],"slateId":"GpoSrXKluJgi6ki1YG7TS"}]