题解 | #监狱逃亡#

考虑把逃亡的过程分成三段：

• 在第一行 $1\to 2\to 3\to \cdots \to i1\backslash rightarrow2\backslash rightarrow3\backslash rightarrow\backslash cdots\backslash rightarrow\; i$
• 在第二行 $i\to \cdots \to ji\backslash rightarrow\backslash cdots\backslash rightarrow\; j$
• 在第三行 $j\to \cdots \to nj\backslash rightarrow\backslash cdots\backslash rightarrow\; n$

然后顺理成章地想到前缀和一下，推一推式子：

• 假设第一行前缀和 $s{1}_i=s{1}_{i-1}+a_{1,i}s1\_i=s1\_\{i-1\}+a\_\{1,i\}$
• 假设第二行前缀和 $s{2}_i=s{2}_{i-1}+a_{2,i}s2\_i=s2\_\{i-1\}+a\_\{2,i\}$
• 假设第三行前缀和 $s{3}_i=s{3}_{i-1}+a_{3,i}s3\_i=s3\_\{i-1\}+a\_\{3,i\}$

那么上面的过程就可以写成这样的区间和式子：

$s{1}_{1\cdots i}+s{2}_{i\cdots j}+s{3}_{j\cdots n}s1\_\{1\backslash cdots\; i\}+s2\_\{i\backslash cdots\; j\}+s3\_\{j\backslash cdots\; n\}$

其中形如 $s_{l\cdots r}s\_\{l\backslash cdots\; r\}$ 可以用 $s_r-s_{l-1}s\_r-s\_\{l-1\}$ 表示，不明白为什么的同学可以参见 这里。

至此我们推出一个与前缀和密切相关的式子：

$s1[i]-s1[0]+s2[j]-s2[i-1]+s3[n]-s3[j-1]\ge 0s1[i]-s1[0]+s2[j]-s2[i-1]+s3[n]-s3[j-1]\backslash ge0$

分析一下这个式子，首先 $s1[0]s1[0]$ 和 $s3[n]s3[n]$ 是固定且已知的，可以暂时扔掉不看，因为待会就能视作常量来分析。

接着我们可以考虑枚举第一维的 $ii$，这样 $s1[i]s1[i]$ 和 $s2[i-1]s2[i-1]$ 也就变成已知量了。

后面还剩下一个 $s2[j]-s3[j-1]s2[j]-s3[j-1]$，这个东西我们暂且把它记作 $b[j]b[j]$。

也就是说，我们枚举了 $ii$ 之后，就是要找所有的 $j\ge ij\backslash ge\; i$ 且 $b[j]\ge tmpb[j]\backslash ge\; tmp$ 的 $jj$ 的个数，那么 $tmptmp$ 就是前面我固定下来的那一大坨东西全部扔到不等号右边后的结果。

考虑这个东西怎么维护，其实很简单，离线处理 + 离散化一下，然后权值线段树就可以简单地查询这个东西了，注意到随着 $ii$ 增加满足 $j\ge ij\backslash ge\; i$ 的 $jj$ 越来越少，我们不妨倒着枚举 $ii$，这样全是加点看起来好做一点（其实正着做也没什么，顶多就是全是加一遍然后按着顺序减一减）。

时间复杂度 $O(n\log n)O(n\backslash log\; n)$，具体细节参见代码：

#include<cstdio>
#include<algorithm>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e6 + 5, Mod = (int) 1e9 + 7;
int s1[N], s2[N], s3[N];
int b[N], c[N];
int L[N << 2], R[N << 2], tree[N << 2];
void build(int root, int l, int r){
	L[root] = l, R[root] = r;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(root << 1, l, mid), build(root << 1 | 1, mid + 1, r);
}
void rebuild(int root, int id, int x){
	int nL = L[root], nR = R[root];
	if (nL == nR) {tree[root] += x; return; }
	int mid = (nL + nR) >> 1;
	if (id <= mid) rebuild(root << 1, id, x);
	if (id >= mid + 1) rebuild(root << 1 | 1, id, x);
	tree[root] = tree[root << 1] + tree[root << 1 | 1];
}
int search(int root, int l, int r){
	int nL = L[root], nR = R[root];
	if (l <= nL && nR <= r) return tree[root];
	int mid = (nL + nR) >> 1, ans = 0;
	if (l <= mid) ans += search(root << 1, l, r);
	if (r >= mid + 1) ans += search(root << 1 | 1, l, r);
	return ans;
}
signed main(){
	int n = init();
	for (int i = 1; i <= n; ++i)
		s1[i] = s1[i - 1] + init();
	for (int i = 1; i <= n; ++i)
		s2[i] = s2[i - 1] + init();
	for (int i = 1; i <= n; ++i)
		s3[i] = s3[i - 1] + init();
	int cLen = n;
	for (int j = 1; j <= n; ++j)
		b[j] = c[j] = s2[j] - s3[j - 1];
	for (int i = n; i >= 1; --i)
		c[++cLen] = -s1[i] - s3[n] + s2[i - 1];
	std::stable_sort(c + 1, c + 1 + cLen);
	int len = std::unique(c + 1, c + 1 + cLen) - (c + 1), ans = 0;
	build(1, 1, len);
	c[++len] = 999999999999999999ll;
	for (int i = n; i >= 1; --i) {
		int now = s1[i] + s3[n] - s2[i - 1];
		/* 枚举到 i，把 j = i 加进去 */
		int ID = std::upper_bound(c + 1, c + 1 + len, b[i]) - (c + 1);
		rebuild(1, ID, 1);
		int ID2 = std::upper_bound(c + 1, c + 1 + len, -now) - (c + 1);
		if (ID2 <= len) ans = (ans + search(1, ID2, len)) % Mod;
	}
	print(ans % Mod), putchar('\n');
}