7038 – t4

这不是跳舞增强版吗

考虑把原来两种做法优化

分治

单组询问分治，对于每一层处理经过当前层mid的区间贡献
预处理[l,mid]的后缀min和max，枚举右端点，对于[mid+1,r]的min和max是确定的，分类讨论拼起来的区间的min和max在哪一边

发现对于min和max都各有一个分界点k
∀ i ∈ [ k , m i d ] ， m i n [ i , r ] = m i n [ m i d + 1 , r ] \forall i\in[k,mid]，min[i,r]=min[mid+1,r] ∀i∈[k,mid]，min[i,r]=min[mid+1,r]
∀ i ∈ [ l , k − 1 ] , m i n [ i , r ] = m i n [ i , m i d ] \forall i\in[l,k-1], min[i,r]=min[i,mid] ∀i∈[l,k−1],min[i,r]=min[i,mid]
然后发现二者的分界点把[l,mid]分成了三部分

对于第一部分， a n s = ∑ m i n ⋅ m a x ans=\sum min\cdot max ans=∑min⋅max
对于第二部分， a n s = m i n R ⋅ ∑ m a x 或 m a x R ⋅ m i n ans=minR\cdot\sum max 或maxR\cdot min ans=minR⋅∑max或maxR⋅min
对于第三部分， a n s = m i n R ⋅ m i n L ⋅ l e n ans=minR\cdot minL\cdot len ans=minR⋅minL⋅len
所以分别预处理四者的后缀和即可

---

考虑扩展到多组询问，先离线询问，然后还是分治做法，先处理经过当前中点的区间的贡献，再递归下去解决（相当于把一个询问区间拆成log段）

对于一个区间[x,y]，在处理[l,r]时已经处理了经过mid的贡献，所以只需要再分别考虑[x,mid]和[mid+1,y]的贡献即可

对于区间[l,r]，还是预处理4个后缀和，枚举右端点然后用线段树去维护总和。先对节点预处理区间和num，每次分成3段区间打add标记，表示sum(贡献)+=add*num，然后维护区间和。询问按右端点排序，枚举到当前右端点时更新ans= ∑ \sum ∑t[0/1/2/3].query(l,mid)

线段树

还是先离线询问，枚举右端点，考虑暴力就是用两个数组mn,mx去表示[l,r]的min和max，每次r++时更新数组

考虑用线段树去优化这个过程，用单调栈（存下标）去维护，每次先弹栈，再把[q[top]+1,r]这段区间的mn数组改成a[i]，每个a[i]只会进一次出一次，维护区间min/max覆盖标记和区间答案

然后如果把不同的r对应的mn数组看成是mn数组的不同版本（r=1就是版本1，r=2就是版本2）
那么询问L,R，其实就是对[L,R]的每个版本询问[L,R]的和

然后就变成了维护历史和的一个操作
并没有想到覆盖标记怎么搞，先把覆盖标记转化成加标记，每次弹栈的时候把对应区间减去a[q[top]]，最后再把[q[top]+1,r]加上a[i]

然后考虑维护几个标记，首先是mn和mx的加标记
m x = m x + a , m n = m n + b mx = mx+a, mn = mn+b mx=mx+a,mn=mn+b
∑ m x = ∑ m x + a ⋅ s z \sum mx=\sum mx+a\cdot sz ∑mx=∑mx+a⋅sz
∑ m n = ∑ m n + b ⋅ s z \sum mn=\sum mn+b\cdot sz ∑mn=∑mn+b⋅sz
∑ m x ⋅ m n = ∑ ( m x + a ) ( m n + b ) = ∑ m x ⋅ m n + a ∑ m n + b ∑ m x + a b ⋅ s z \sum mx\cdot mn = \sum (mx+a)(mn+b)=\sum mx\cdot mn+a\sum mn+b\sum mx+ab\cdot sz ∑mx⋅mn=∑(mx+a)(mn+b)=∑mx⋅mn+a∑mn+b∑mx+ab⋅sz

然后是更新s(历史和)的标记
s = s + c ∑ m x ⋅ m n s=s+c\sum mx\cdot mn s=s+c∑mx⋅mn

问题是在合并标记的时，会发现标记不够用

后面那一堆东西没办法只用一个c表示出来

所以维护c,d,e,f表示 s = s + c ∑ m x m n + d ∑ m n + e ∑ m x + f ⋅ s z s=s+c\sum mxmn+d\sum mn+e\sum mx+f\cdot sz s=s+c∑mxmn+d∑mn+e∑mx+f⋅sz
然后是标记合并：
对mx加就打(k,0,0,0,0,0)的标记
对mn加就打(0,k,0,0,0,0)的标记
每次更新完打(0,0,1,0,0,0)的标记表示更新历史和