首先，題目要的列成式子就是

$ L \le sum(i,j) \le R$ 的數量

最明顯的優化是把sum(i,j)的部分換成前綴和，讓$p(i)$代表前綴和的第i項

於是變成 $L \le p(j) - p(i-1) \le R$，把L和R拆開

$L \le p(j) - p(i-1)$ 聯集 $p(j)-p(i-1) \le R$，不過前綴和自帶 $j>i$，所以就是這三條聯集

分開來個別討論

如果把 a 陣列中每項減去 L，讓他叫 al 陣列，會變成

$0 \le sum(al(i),al(j))$帶上前綴和，讓前綴和叫$pl$，變成$0 \le pl(j) - pl(i-1)$

移項後發現會是個很漂亮的$pl(j) \ge pl(i-1)$

把R的部分做一樣的事情，會得到

$pr(i-1) \ge pr(j)$同乘負號就變成，$-pr(j) \ge -pr(i-1)$

於是題目被化簡為 $pl(j) \ge pl(i-1)$聯集$-pr(j) \ge -pr(i-1)$聯集$j>i$

變得好熟悉?! 他就是三維偏序!! 模板貼上去就過了!!

主流作法是 cdq分治、樹套樹 甚至有 bitset壓常，但我都不會 照常用整體二分+BIT

時間複雜度$O(nlog^2n)$

首先，題目要的列成式子就是

$ L \le sum(i,j) \le R$ 的數量

最明顯的優化是把sum(i,j)的部分換成前綴和，讓$p(i)$代表前綴和的第i項

於是變成 $L \le p(j) - p(i-1) \le R$，把L和R拆開

$L \le p(j) - p(i-1)$ 聯集 $p(j)-p(i-1) \le R$，不過前綴和自帶 $j>i$，所以就是這三條聯集

分開來個別討論

如果把 a 陣列中每項減去 L，讓他叫 al 陣列，會變成

$0 \le sum(al(i),al(j))$帶上前綴和，讓前綴和叫$pl$，變成$0 \le pl(j) - pl(i-1)$

移項後發現會是個很漂亮的$pl(j) \ge pl(i-1)$

把R的部分做一樣的事情，會得到

$pr(i-1) \ge pr(j)$同乘負號就變成，$-pr(j) \ge -pr(i-1)$

於是題目被化簡為 $pl(j) \ge pl(i-1)$聯集$-pr(j) \ge -pr(i-1)$聯集$j>i$

變得好熟悉?! 他就是三維偏序!! 模板貼上去就過了!!

主流作法是 cdq分治、樹套樹 甚至有 bitset壓常，但我都不會 照常用整體二分+BIT

時間複雜度$O(nlog^2n)$

以$c()$代表數量

陣列$A$的子陣列$a$平均$L\leq\bar a\leq R$的數量$c(L\leq\bar a\leq R)=c(\bar a\geq L)-c(\bar a> R)$

先求出陣列$A$每項減$L$後的陣列$A_L$、$A$每項減$R$後的陣列$A_R$；以$a_L, a_R$分別代表$A_L, A_R$的某個子陣列，則所求$=c(\bar a_L\geq 0)-c(\bar a_R> 0)$

平均數$\bar X=\frac{\sum(X)}{\text{len}(X)}\geq0$即代表總和$\sum(X)\geq0$；故所求$=c(\sum a_L\geq 0)-c(\sum a_R>0)$

於是原題轉換成計算子陣列和大於(等於)$K$的題目Subarray sum greater than (or equal to) $K$。算出$A_L, A_R$的前綴和$P_L, P_R$，則所求$=c_{j\geq i}(P_L(j)-P_L(i)\geq0)-c_{j\geq i}(P_R(j)-P_R(i)>0)$
移項，所求$=c_{j\geq i}(P_L(j)\geq P_L(i))-c_{j\geq i}(P_R(j)>P_R(i))$。

故原題轉換成計算逆序對Count inversions的"幾乎"模板題(注意有$\geq$也有$>$)，利用資節或Merge sort過。

複雜度：$O(n)[算A_L, A_R, P_L, P_R]+O(n\log n)[逆序對]$
$=O(n\log n)$

首先，題目要的列成式子就是

$ L \le sum(i,j) \le R$ 的數量

最明顯的優化是把sum(i,j)的部分換成前綴和，讓$p(i)$代表前綴和的第i項

於是變成 $L \le p(j) - p(i-1) \le R$，把L和R拆開

$L \le p(j) - p(i-1)$ 聯集 $p(j)-p(i-1) \le R$，不過前綴和自帶 $j>i$，所以就是這三條聯集

分開來個別討論

如果把 a 陣列中每項減去 L，讓他叫 al 陣列，會變成

$0 \le sum(al(i),al(j))$帶上前綴和，讓前綴和叫$pl$，變成$0 \le pl(j) - pl(i-1)$

移項後發現會是個很漂亮的$pl(j) \ge pl(i-1)$

把R的部分做一樣的事情，會得到

$pr(i-1) \ge pr(j)$同乘負號就變成，$-pr(j) \ge -pr(i-1)$

於是題目被化簡為 $pl(j) \ge pl(i-1)$聯集$-pr(j) \ge -pr(i-1)$聯集$j>i$

變得好熟悉?! 他就是三維偏序!! 模板貼上去就過了!!

主流作法是 cdq分治、樹套樹 甚至有 bitset壓常，但我都不會 照常用整體二分+BIT

時間複雜度$O(nlog^2n)$

以$c()$代表數量

陣列$A$的子陣列$a$平均$L\leq\bar a\leq R$的數量$c(L\leq\bar a\leq R)=c(\bar a\geq L)-c(\bar a> R)$

先求出陣列$A$每項減$L$後的陣列$A_L$、$A$每項減$R$後的陣列$A_R$；以$a_L, a_R$分別代表$A_L, A_R$的某個子陣列，則所求$=c(\bar a_L\geq 0)-c(\bar a_R> 0)$

平均數$\bar X=\frac{\sum(X)}{\text{len}(X)}\geq0$即代表總和$\sum(X)\geq0$；故所求$=c(\sum a_L\geq 0)-c(\sum a_R>0)$

於是原題轉換成計算子陣列和大於(等於)$K$的題目Subarray sum greater than (or equal to) $K$。算出$A_L, A_R$的前綴和$P_L, P_R$，則所求$=c_{j\geq i}(P_L(j)-P_L(i)\geq0)-c_{j\geq i}(P_R(j)-P_R(i)>0)$
移項，所求$=c_{j\geq i}(P_L(j)\geq P_L(i))-c_{j\geq i}(P_R(j)>P_R(i))$。

故原題轉換成計算逆序對Count inversions的"幾乎"模板題(注意有$\geq$也有$>$)，利用資節或Merge sort過。

複雜度：$O(n)[算A_L, A_R, P_L, P_R]+O(n\log n)[逆序對]$
$=O(n\log n)$

哇這個更神了

我沒注意到這個

我還是太弱了qwq

學長orz

首先，題目要的列成式子就是

$ L \le sum(i,j) \le R$ 的數量

最明顯的優化是把sum(i,j)的部分換成前綴和，讓$p(i)$代表前綴和的第i項

於是變成 $L \le p(j) - p(i-1) \le R$，把L和R拆開

$L \le p(j) - p(i-1)$ 聯集 $p(j)-p(i-1) \le R$，不過前綴和自帶 $j>i$，所以就是這三條聯集

分開來個別討論

如果把 a 陣列中每項減去 L，讓他叫 al 陣列，會變成

$0 \le sum(al(i),al(j))$帶上前綴和，讓前綴和叫$pl$，變成$0 \le pl(j) - pl(i-1)$

移項後發現會是個很漂亮的$pl(j) \ge pl(i-1)$

把R的部分做一樣的事情，會得到

$pr(i-1) \ge pr(j)$同乘負號就變成，$-pr(j) \ge -pr(i-1)$

於是題目被化簡為 $pl(j) \ge pl(i-1)$聯集$-pr(j) \ge -pr(i-1)$聯集$j>i$

變得好熟悉?! 他就是三維偏序!! 模板貼上去就過了!!

主流作法是 cdq分治、樹套樹 甚至有 bitset壓常，但我都不會 照常用整體二分+BIT

時間複雜度$O(nlog^2n)$

https://github.com/kzzz-jpg/CP/blob/main/cpp/cchs/a277.cpp
附個程式，離散化的地方有點醜