P11763 [IAMOI R1] Family Conflict

Xiao L and Xiao C have had some family conflicts, and they are on the verge of breaking up.

Each day that Xiao L and Xiao C spend together can be represented by a tuple $(a_i, c_i)$. Here, $c_i$ is either $0$ or $1$, indicating whether Xiao L and Xiao C had a quarrel on that day. $a_i$ is an integer representing Xiao C's mood value on that day. Xiao L and Xiao C are simultaneously engaged in $m$ family wars. The $k$-th war starts on the $l_k$-th day. Since their wars are very intense, you do not know on which day they will end. However, if the war ends on the $r$-th day, and the number of quarrel days from the $l_k$-th day to the $r$-th day is exactly $d_k$, then this war will bring Xiao C a certain amount of resentment value. The resentment value is the number of inversion pairs in Xiao C's mood values from the $l_k$-th day to the $r$-th day. Otherwise, Xiao C's resentment value is $0$. Now, Xiao L has provided you with the $(a_i, c_i)$ for all $n$ days and the $l_k$ and $d_k$ for the $m$ wars. For each war, Xiao L wants to know the sum of Xiao C's resentment values over all possible ending times, so he can try to mend their relationship. He will be very grateful for your help and reward you with $7420738134810 \bmod 12673$ yuan as thanks. ### Formal Description You have $n$ tuples $(a_{i}, c_{i})$, where $c_{i} \in \{0,1\}$. There are $m$ queries. Each query provides two integers $l_{k}$ and $d_{k}$. Compute: $$ \sum_{r=l_{k}}^{n} \left[\left(\sum_{i=l_{k}}^{r} c_{i}\right)=d_{k}\right] \sum_{i=l_{k}}^{r} \sum_{j=i+1}^{r} [a_{j}

N/A

N/A

### Sample Explanation 1 For the first query, only the interval $[3,4]$ meets the condition, so the answer is $1$. For the second query, only the interval $[1,4]$ meets the condition, so the answer is $5$. ### Data Range | Test Case ID | $n,m \leq$ | Special Properties | | :----------: | :--------: | :----------------: | | $1$ | $100$ | None | | $2,3$ | $10^3$ | None | | $4,5$ | $10^5$ | A | | $6\sim8$ | $10^5$ | B | | $9,10$ | $10^5$ | CD | | $11,12$ | $5\times10^4$ | C | | $13,14$ | $10^5$ | C | | $15\sim17$ | $10^5$ | D | | $18\sim20$ | $5\times10^4$ | None | | $21\sim25$ | $10^5$ | None | Special Property A: All $c_i=0$. Special Property B: All $d_{k}=1$. Special Property C: All $c_i=1$. Special Property D: For all queries, $\forall k