题解 | 函数函数函

考虑莫队，假定我们已经处理出区间 [l,r][l,r] 的答案，考虑去扩展到 [l,r+1][l,r+1] 的答案。

定义

S0[k]=∑1≤i≤k,imod  2=0a[i]S_0[k]=\sum_{1\le i\le k,i\mod 2=0}a[i]
S1[k]=∑1≤i≤k,imod  2=1a[i]S_1[k]=\sum_{1\le i\le k,i\mod 2=1} a[i]

我们转移的代价为：

∑l≤i≤r+1max⁡(S0[r+1]−S0[i−1],S1[r+1]−S1[i−1])\sum_{l\le i\le r+1}\max(S_0[r+1] - S_0[i-1], S_1[r+1] - S_1[i-1])

将 S1[r+1]−S1[i−1]S_1[r+1] - S_1[i-1] 提出 max⁡\max 。

∑l≤i≤r+1max⁡((S0[r+1]−S0[i−1])−(S1[r+1]−S1[i−1]),0)+S1[r+1]−S1[i−1]\sum_{l\le i\le r+1}\max((S_0[r+1] - S_0[i-1])-(S_1[r+1] - S_1[i-1]), 0)+S_1[r+1] - S_1[i-1]

而对于

∑l≤i≤r+1S1[r+1]−S1[i−1]\sum_{l\le i\le r+1}S_1[r+1] - S_1[i-1]

的处理是平凡的。

令

S[i]=S0[i]−S1[i]S[i]=S_0[i]-S_1[i]

那么前面的部分即

∑l−1≤i≤rmax⁡(S[r+1]−S[i],0)\sum_{l-1\le i\le r}\max(S[r+1]-S[i], 0)

我们发现这样对这一部分的处理同样是平凡的。

具体地：

令 Pre[i]=∑j=1i[S[r+1]>S[i]],Ps[i]=∑j=1i[S[r+1]>S[i]]a[j]Pre[i]=\sum_{j=1}^i[S[r+1]>S[i]],Ps[i]=\sum_{j=1}^i[S[r+1]>S[i]]a[j]

那么

∑l−1≤i≤rmax⁡(S[r+1]−S[i],0)=(Pre[r]−Pre[l−2])×S[r+1]+(Ps[r]−Ps[l−2])\sum_{l-1\le i\le r}\max(S[r+1]-S[i], 0)=(Pre[r]-Pre[l-2])\times S[r+1]+(Ps[r]-Ps[l-2])

对于 Pre,PsPre,Ps 处理可以直接莫队二离做到 O(n1.5)O(n^{1.5}) 。