[ 监狱逃亡]树状数组

D.监狱逃亡

大意：给定3*n的矩阵，。从(1,1)处走到(3,n)处，每次只能往右或者往下走，求走的格子的数字之和>=0 的方案数。

思路：记$su{m}_{k}sum\_k$为第k行的前缀和。通过读题我们不难发现实际上就是需要两个向下走的位置i,j 满足i<=j, 且 $su{m}_{1,i}+su{m}_{2,j}-su{m}_{2,i-1}+su{m}_{3,n}-su{m}_{3,j-1}>=0sum\_\{1,i\}+sum\_\{2,j\}-sum\_\{2,i-1\}+sum\_\{3,n\}-sum\_\{3,j-1\}>=0$

如果只有两行我们很容想到可以直接枚举从哪个位置开始往下走。所以我们可以尝试先枚举从哪一列（即枚举 i）到第二行，每次计算有多少个j满足$su{m}_{2,j}+su{m}_{3,n}-su{m}_{3,j-1}>=su{m}_{2,i-1}-su{m}_{1,i}sum\_\{2,j\}+sum\_\{3,n\}-sum\_\{3,j-1\}>=sum\_\{2,i-1\}-sum\_\{1,i\}$

即每次查询 $>=su{m}_{2,i-1}-su{m}_{1,i}>=sum\_\{2,i-1\}-sum\_\{1,i\}$的个数，树状数组的经典应用。

并且需要保证 i<=j，所以可以从后往前更新。

数组范围太大，需要离散化。

代码如下：

#include <bits/stdc++.h>
#define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
#define frep(i,bbb,eee) for(int i=bbb;i>=eee;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define AC signed
#define x first
#define y second
#define int long long 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N=1000010,M=1000000007;
int sum[5][N],a[5][N],n,tr[N],m;
vector<int> v;
int find(int x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void add(int x,int y)
{
	while(x<=m)tr[x]+=y,x+=x&-x;
}
int ask(int x)
{
	int res=0;
	while(x)res+=tr[x],x-=x&-x;
	return res;
}
void solve()
{
	cin>>n;
	rep(i,1,3)
		rep(j,1,n)
		{
			cin>>a[i][j];
			sum[i][j]=sum[i][j-1]+a[i][j];
		}
	for(int i=1;i<=n;i++)
	{
		v.pb(sum[2][i]+sum[3][n]-sum[3][i-1]);
		v.pb(sum[2][i-1]-sum[1][i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	m=v.size();
	int ans=0;
	frep(i,n,1)
	{
		add(find(sum[2][i]+sum[3][n]-sum[3][i-1]),1);
		int x=find(sum[2][i-1]-sum[1][i]);
		ans+=ask(m)-ask(x-1);
		ans%=M;
	}
	cout<<ans<<"\n";
}
AC main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _=1;
	//cin>>_;
	while(_--)solve();
	return 0;
}