U300220 朵（dorr）

我多么想你能变成我永不凋零的花朵 但时间不会让你永远的停泊 $Subtask #0$ 为样例。

朵要离开的路上开满了桃花，这条路上有 $n$ 颗桃花树，对于每颗树 $i$ 有一个会使她开心的美丽值 $a_i$；同时，有一个会使她难过的回忆值 $b_i$。 朵在匆匆离去。在某一个时刻，走到某一棵树下时，她才开始留意这周围的环境。又在某一个时刻，走到某一棵树下时，她又不再观察这俗世，重新开始匆匆赶路；在这段时间中，她的开心值在累积，难过值也在累积。 具体的，当朵经过 $[l,r]$ 这段路时，我们记开心值 $H(l,r)= \sum\limits_{i=l}^{r} a_i$；伤心值 $S(l,r)=\mathop{\large\text{and}}\limits_{i=l}^{r} b_i$，其中 $\mathop{\text{and}}$ 表示按位与。 如果在朵经历这段时间过后，情感累积过多，朵的心理自然是承受不下的。所以给定一个情感最大值 $M$，只有 $H(l,r)-S(l,r)\leq M$ 她才可以承受。 所以你要求出所有满足条件的区间 $[l,r]$ 的长度和。 ### 简化题意 给出测试点类型 $id$，两个数 $n,M$，$n$ 个 $a_i,b_i$，求: $$\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n} \left[(\sum\limits_{i=l}^{r} a_i-\mathop{\large\text{and}}\limits_{i=l}^{r} b_i)\leq M\right]\times (r-l+1)$$ $\sum\limits_{i=l}^{r} f(i)$ 表示 $f(l)+f(l+1)+\cdots+f(r)$。 $\mathop{\large\text{and}}\limits_{i=l}^{r} f(i)$ 表示 $f(l)\mathop{\text{and}} f(l+1)\mathop{\text{and}}\cdots\mathop{\text{and}} f(r)$。 形如 $(x\leq y)$ 这样的为逻辑表达式，即括号中的条件若满足，则表达式的值为 $1$，否则为 $0$。

第一行一个整数 $id$，表示测试点类型，具体见下方提示说明。 第二行两个整数 $n,M$，表示树的个数和情感最大值。 第三行 $n$ 个整数 $a_i$，表示第 $i$ 棵树的开心值。 第四行 $n$ 个整数 $b_i$，表示第 $i$ 棵树的伤心值。

一行一个整数，表示满足条件的区间的长度和。

[附件](https://cncncloud.com/s/wJQ6WHd) 本题输入量较大，建议使用较快输入方式。 设 $T$ 为满足条件的区间个数。 | 测试点编号 | 测试点类型 | 数据点要求 | | :----------- | :----------- | :----------- | | $1$ | $1$ | 为样例 $1$ | | $2\sim 5$ | $2$ | $1\leq n\leq 200$ | | $6\sim 8$ | $3$ | $1\leq n\leq 1000$ | | $9\sim 10$ | $4$ | $1\leq n\leq 1\times 10^5,1\leq T\leq 1\times10^7$ | | $11\sim 14$ | $5$ | $1\leq n\leq 1\times 10^5$ | | $15\sim 17$ | $6$ | $1\leq n\leq 5\times 10^5$ | | $18$ | $7$ | $1\leq n\leq 1\times 10^6$，所有区间均满足条件 | | $19\sim 20$ | $8$ | $1\leq n\leq 1\times 10^6$ | 对于所有数据 $1\leq id\leq 8,1\leq n,a_i\leq 1\times10^6,0\leq M\leq 1\times 10^{12},1\leq b_i\leq 1\times 10^{12}$。 ### 后记 我多么想你能摆脱这世间给予的浮夸 就像我母亲年轻时那样的无华 ------------ 夹带私货：[赵雷的《朵》](https://music.163.com/#/song?id=447926063)好好听啊。 `By int_R`