P11763 [IAMOI R1] 家庭矛盾

小 L 和小 C 发生了一些家庭矛盾，小 C 和小 L 徘徊在分手的边缘。

小 L 和小 C 在一起生活的的每一天都可以用一个二元组 $(a_i,c_i)$ 表示。$c_i$ 要么是 $0$ ，要么是 $1$，代表这天小 L 和小 C 有没有吵架。而 $a_i$ 则是一个整数，代表这一天小 C 的心情值。 小 L 和小 C 正在同时进行 $m$ 场家庭战争。第 $k$ 场战争从第 $l_k$ 天开始。 由于他们的战争非常激烈，你不知道他们在第几天会结束这场战争。但如果这场战争于第 $r$ 天结束，且从第 $l_k$ 天到第 $r$ 天吵架的天数恰好为 $d_k$，那么这场战争就会给小 C 带来一定的怨气值。怨气值为第 $l_k$ 天到第 $r$ 天小 C 心情值的逆序对个数。否则，小 C 的怨气值就为 $0$。 现在，小 L 把这 $n$ 天的 $(a_i,c_i)$ 和 $m$ 场战争的 $l_k$ 和 $d_k$ 告诉了你。对于每场战争，小 L 希望知道对于所有可能的结束时间，小 C 的怨气值之和，以便他挽回和小 L 的感情。他会非常感激你的帮助，并给你 $7420738134810 \bmod 12673$ 元作为感谢。 ### 形式化题意 你有 $n$ 个二元组 $(a_{i},c_{i})$，其中满足 $c_{i} \in \{0,1\}$。 现在有 $m$ 个询问，每次询问给出两个整数 $l_{k},d_{k}$，求： $$ \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}

无

无

### 样例解释 $1$ 对于询问 $1$，只有区间 $[3,4]$ 符合条件，所以答案为 $1$。 对于询问 $2$，只有区间 $[1,4]$ 符合条件，所以答案为 $5$。 ### 数据范围 |测试点编号| $n,m\le$ | 特殊性质 | | :-----------: | :-----------: | :-----------: | | $1$ | $100$ | 无 | | $2,3$ | $10^3$ | 无 | | $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\sim 17$ | $10^5$ | D | | $18\sim20$ | $5\times10^4$ | 无 | | $21\sim25$ | $10^5$ | 无 | 特殊性质 A：保证 $c_i=0$。 特殊性质 B：保证 $d_{k}=1$。 特殊性质 C：保证 $c_i=1$。 特殊性质 D：保证询问中 $\forall k