Range Multiplication Sum

2 secs 1024 MB
bayashiko's icon bayashiko

愚直に処理すると計算量は O(N2Q)O(N^2 Q) となり、間に合いません。
i=lr1j=i+1r(Ai×Aj)=((i=lrAi)2(i=lrAi2))/2\sum_{i=l}^{r-1} \sum_{j=i+1}^{r} (A_i×A_j)=((\sum_{i=l}^{r}A_i)^2-(\sum_{i=l}^{r}A_i^2))/2 なので、一点更新・区間和を処理できるセグメント木を 22 つ用意し、それぞれ A=(A1,A2,,AN)A=(A_1,A_2,\ldots,A_N)A=(A12,A22,,AN2) A'=(A_1^2,A_2^2,\ldots,A_N^2) を載せることにすると各クエリを O(logN)O(logN) で処理できます。
全体の計算量は O(N+QlogN)O(N+QlogN) です。