P11625 [迷宫寻路 Round 3] 迷宫寻路大赛

给定参数 $c,d$ 和一个长度为 $n$ 的序列 $\{a\}$。有 $q$ 个区间，对于每个区间 $[l,r]$，求出 $\sum\limits_{x=l}^{r} \sum\limits_{y=x}^r [c\le (\sum\limits_{i=x}^{y} \sum\limits_{j=i+1}^{y} [a_i>a_j])\le d]$。 注意区别以上两种中括号： 1. $[l,r]$ 代表一个区间。 2. $[p]$ 为艾弗森括号，其中 $p$ 是一个仅有真假两种取值的表达式。若 $p$ 为真，则 $[p]=1$，否则 $[p]=0$。 通俗的讲，对于每个区间 $[l,r]$，求出区间内有多少非空子区间的逆序对个数在 $c$ 到 $d$ 之间（含 $c$ 和 $d$）。

无

无

**本题采用捆绑测试。** 对于所有数据，$1\le n,q,a_i\le 5\times 10^5$，$1\le c,d\le 10^{12}$，对于每个 $1\le i\le q$，满足 $1\le l_i\le r_i\le n$。 | 子任务编号 | $n\leq$ | $q\leq$ | 分数 | | :----------: | :----------: | :----------: | :----------: | | $0$ | $10$ | $10$ | $5$ | | $1$ | $100$ | $100$ | $10$ | | $2$ | $1000$ | $1000$ | $10$ | | $3$ | $5000$ | $5000$ | $15$ | | $4$ | $50000$ | $50000$ | $25$ | | $5$ | $5\times 10^5$ | $5\times 10^5$ | $35$ |