高级DP汇总-动态DP-整体DP-个人总结

动态DP-链分治-[清华集训2016]数据交互-解题报告 动态DP+字典序-「LibreOJ NOI Round #1」验题-解题报告 整体DP-线段树合并-[九省联考2018]秘密袭击coat-解题报告 ### EOJ 634 ~~线段树合并要写pushup...调试的血的教训。cao，线段树的len调试时开成5，忘了改回来了~~ 线段树合并对应相乘，维护区间和 具体看寒假的课程 ```cpp struct Data { int a,b; Data(int _a=1,int _b=0) {a=_a,b=_b;} friend Data operator+(const Data &x,const Data &y) { return Data(mul(x.a,y.a),add(mul(x.b,y.a),y.b)); } void operator+=(const Data &v) {(*this)=(*this)+v;} } dat[M]; int tot,ls[M],rs[M],sum[M]; int ans; int rt[N]; il void up(int x) { sum[x]=add(sum[ls[x]],sum[rs[x]]); } il void give(int x,int len,const Data &v) { dat[x]+=v; sum[x]=add(mul(v.a,sum[x]),mul(v.b,len)); } il void down(int x,int l,int r) { if(!ls[x]) ls[x]=++tot; if(!rs[x]) rs[x]=++tot; if(dat[x].a==1&&dat[x].b==0) return; gm; give(ls[x],mid-l+1,dat[x]); give(rs[x],r-mid,dat[x]); dat[x]=Data(); } void upd(int &x,int l,int r,int ql,int qr,const Data &v) { if(!x) x=++tot; if(ql<=l&&r<=qr) return give(x,r-l+1,v); gm; down(x,l,r); if(ql<=mid) upd(ls[x],l,mid,ql,qr,v); if(qr>mid) upd(rs[x],mid+1,r,ql,qr,v); up(x); } void merge(int &x,int &y,int l,int r) { if(!ls[x]&&!rs[x]) swap(x,y); if(!ls[y]&&!rs[y]) { give(x,r-l+1,Data(dat[y].b,0)); return; } gm; down(x,l,r),down(y,l,r); merge(ls[x],ls[y],l,mid); merge(rs[x],rs[y],mid+1,r); up(x); } int ask(int x,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) return sum[x]; gm; down(x,l,r); if(qr<=mid) return ask(ls[x],l,mid,ql,qr); if(ql>mid) return ask(rs[x],mid+1,r,ql,qr); return ask(ls[x],l,mid,ql,qr)+ask(rs[x],mid+1,r,ql,qr); } void dfs(int x) { upd(rt[x],1,len,1,len,Data(0,1)); for(solid v:sn[x]) { dfs(v); if(col[v]==col[x]) { upd(rt[v],1,len,1,len,Data(1,1)); merge(rt[x],rt[v],1,len); } else { LL res=ask(rt[v],1,len,col[x],col[x]); upd(rt[x],1,len,col[v],col[v],Data(add(res,1),0)); } } inc(ans,sub(ask(rt[x],1,len,1,len),mul(len-1,ask(rt[x],1,len,col[x],col[x])))); } ```