ABC468 扫描线|贡献法|二阶差分|线段树优化DP

E贡献法 扫描线 二阶差分求一个数组的所有子数组的平均数之和。等价于求所有子数组的加权和。对于长度iii的子数组权重就是1/i1/i1/i考虑贡献法有两种一种是每个元素的贡献一种是每个前缀的贡献。先来说第一个这个比较麻烦每个元素的贡献考虑对于每个长度iii的划窗划过整个数组每一步给窗口内加上1/i1/i1/i。对于一个iii只用考虑每个位置被加了多少次1/i1/i1/i。这个东西打表或者手玩可以发现贡献基本是一个梯形开始前缀部分单增的等差数列中间一段平台最后后缀是一个单减的等差数列。并且根据窗口长度是否超过nnn的一半中间平台区的高度不一样。但总之都是区间加等差数列这可以线段树也可以二阶差分。这里选择二阶差分做法所谓二阶差分就是需要做两次前缀和才能还原。以下代码封装了一个区间加等差数列的二阶差分更新函数传入区间l,r首项s公差d。具体根据窗口长度分讨两种情况加的等差数列值这里就不说了可以作为一个结论也可以手玩。另外这里有一堆乘法除法加减法为了取模简单用了modintvoidsolve(){intn;cinn;vectorMinta(n10);autoadd[](intl,intr,Mint s,Mint d)-void{if(lr)return;a[l]s;a[l1]d-s;Mint Ll,Rr;a[r1]-s(R-L1)*d;a[r2]s(R-L)*d;};rep(i,1,n){intcurinv(i,M2);if(i(n1)/2){add(1,i-1,cur,cur);add(n-i2,n,(i-1)*cur,-cur);add(i,n-i1,1,0);}else{inthn-i1;add(1,n-i,cur,cur);add(i1,n,(h-1)*cur,-cur);add(n-i1,i,h*cur,0);}}rep(i,1,n){a[i]a[i-1];}rep(i,1,n){a[i]a[i-1];}Mint ans0;rep(i,1,n){intx;cinx;ansMint(x)*a[i];}coutans.val\n;}另一个简单一点的做法是分析每个前缀的贡献每个区间的贡献实际上可以看成(si−sj)/(i−j)(s_i-s_j)/(i-j)(si​−sj​)/(i−j)那么对于前缀si,sjs_i,s_jsi​,sj​分别有1/(i−j),−1/(i−j)1/(i-j),-1/(i-j)1/(i−j),−1/(i−j)的贡献。考虑一个sks_ksk​的贡献他作为sis_isi​的时候是对于j∈[0,k]j∈[0,k]j∈[0,k]这些时候的贡献之和是∑j0k1/j\sum_{j0}^k 1/j∑j0k​1/j。他作为−sj-s_j−sj​的时候同理是对于j∈[k,n]j∈[k,n]j∈[k,n]这些时候的贡献之和是∑jkn1/j\sum_{jk}^n 1/j∑jkn​1/j。注意到这两个贡献都是1/j1/j1/j的区间和维护一个1/j1/j1/j的前缀和即可快速计算贡献。voidsolve(){intn;cinn;vectorMinta(n10),b(n10);rep(i,1,n){intx;cinx;b[i]b[i-1]inv(i,M2);a[i]a[i-1]x;}Mint ans0;rep(i,1,n){ans(b[i]-b[n-i])*a[i];}coutans.val\n;}Fdp 线段树手上两个变量xy0扫一个排列p对每个pip_ipi​可以决定使用x或y中的一个令使用的这个变量t变成max⁡(pi,t)\max(p_i,t)max(pi​,t)如果t在这一步变大了答案计数器1。问答案最大多少。看到这个朴素的想法就是f(i,x,y)f(i,x,y)f(i,x,y)表示考虑前i个两个变量的值分别为x,y能得到的最大答案。这状态太多了考虑压缩。注意到前缀里的每个元素都必须操作那么对于前缀最大值mximx_imxi​一定也被x或y操作了那么我们永远可以确定第i步后max⁡(x,y)mxi\max(x,y)mx_imax(x,y)mxi​。于是x,y中较大元素永远是确定的只需要在状态里维护较小元素即可f(i,j)f(i,j)f(i,j)表示考虑前i个x,y里较小值为j时的最大答案。这还是太多了转移会是O(n)O(n)O(n)的总复杂度O(n2)O(n^2)O(n2)。仔细分析转移看看能不能数据结构优化。如果pip_ipi​大于x,y的较大值那么让x,y哪个来都能答案1,并且操作的那个会变成pip_ipi​。那么贪心的思考一定让较大变量变这样较小值还能保持很小后面变大的次数更多答案更大。如果pip_ipi​位于x,y之间那么可以让x来也可以让y来。如果让较大值来答案不变x,y也都不变无事发生。如果让较小值来较小值会变大为pip_ipi​答案1如果pip_ipi​小于较小值也是无事发生。发现对于上面第一个情况就是对于所有较小值答案都会加1也就是f(i,j)f(i−1,j)1,1≤j≤nf(i,j)f(i-1,j)1,1\le j\le nf(i,j)f(i−1,j)1,1≤j≤n对于第二个情况可以从较小变量小于pip_ipi​的状态转移到pip_ipi​并且答案1也就是f(i,pi)max⁡f(i−1,j)1,j≤pif(i,p_i)\max f(i-1,j)1,j\le p_if(i,pi​)maxf(i−1,j)1,j≤pi​可以发现这两个情况就是区间加区间查询最值可以用线段树优化转移复杂度为O(nlog⁡n)O(n\log n)O(nlogn)。对于第二种情况计算出f(i,pi)f(i,p_i)f(i,pi​)后还需要插入线段树也就是还需要实现一个单点赋值操作。这和前面的全局1操作并不冲突。structTree{#definelsu1#definersu1|1structNode{intl,r;ll mx,add;}tr[N2];voidpushup(intu){tr[u].mxmax(tr[ls].mx,tr[rs].mx);}voidpushdown(intu){if(tr[u].add){tr[ls].mxtr[u].add;tr[rs].mxtr[u].add;tr[ls].addtr[u].add;tr[rs].addtr[u].add;tr[u].add0;}}voidbuild(intu,intl,intr){tr[u]{l,r,0,0};if(lr){tr[u].mx-inf;return;}intmid(lr)1;build(ls,l,mid);build(rs,mid1,r);pushup(u);}voidmodify(intu,intl,intr,intval){if(tr[u].lltr[u].rr){tr[u].mxval;tr[u].addval;return;}else{intmid(tr[u].ltr[u].r)1;pushdown(u);if(midl)modify(ls,l,r,val);if(rmid)modify(rs,l,r,val);pushup(u);}}voidmodify1(intu,intl,intr,intval){if(tr[u].lltr[u].rr){tr[u].mxmax(tr[u].mx,val);return;}else{intmid(tr[u].ltr[u].r)1;pushdown(u);if(midl)modify1(ls,l,r,val);if(rmid)modify1(rs,l,r,val);pushup(u);}}llquery(intu,intl,intr){if(ltr[u].ltr[u].rr)returntr[u].mx;pushdown(u);intmid(tr[u].ltr[u].r)1;if(rmid)returnquery(ls,l,r);if(lmid)returnquery(rs,l,r);returnmax(query(ls,l,r),query(rs,l,r));}}t;voidsolve(){intn;cinn;intmx0;t.build(1,0,n);intx;cinx;t.modify1(1,0,0,1);mxx;rep(i,2,n){intx;cinx;if(xmx){t.modify(1,0,n,1);}else{intrest.query(1,0,x);t.modify1(1,x,x,res1);}mxmax(mx,x);}coutt.query(1,0,n)\n;}