牛客练习赛91 D 监狱逃亡（前缀和，离散化，树状数组）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

勇者为救公主杀入魔塔，不料在魔塔三层遭遇魔王偷袭，失去了神圣剑与神圣盾，而自身也被关入监狱。

监狱是一块3×n的区域，每块格子都有一个价值。勇者目前在监狱的左上角(1,1)处，而他需要逃亡到监狱的右下角(3,n)处。

勇者每次可以向右或者向下移动一格，请问勇者逃亡到右下角，其路径价值和大于等于0的不同方法数一共有多少种，答案对1000000007取模。

题解：存下每行的前缀和sum[i][j];

则最终就是求满足： sum[1][L]+sum[2][R]-sum[2][L-1]+sum[3][n]-sum[3][R-1]>=0&&L<=R

的L，R有几对

原式子——》 sum[1][L]-sum[2][L-1]   >=   sum[3][R-1]-sum[2][R]-sum[3][n];

用a[i] 和b[j] 存下左右

a[i]=sum[1][i]-sum[2][i-1];
  b[i]=sum[3][i-1]-sum[2][i]-sum[3][n];

即：a[i]>=b[j] && i<=j;

将a[i]和b[j]合并离散化

***将b[i]倒着存入到树状数组中

这时可以发现每插入一个数b[i],树状数组中所有比a[i] 小的数正好就是所有 j>=i 的b[j] 里的数

因为i~n里的数刚刚枚举完，

#include
#include
using namespace std;
const long long N=5e6+10,mod=1e9+7;
vector vs;
long long sum[5][N],z[5][N],a[N],b[N],tr[N],n;

int find(long long x)
{
	return lower_bound(vs.begin() ,vs.end() ,x)-vs.begin()+1;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x)
{
	while(x<=2*n)
	{
		tr[x]++;
		x+=lowbit(x);
	}
}
long long query(long long x)
{
	long long sum1=0;
	while(x)
	{
		sum1=(tr[x]+sum1)%mod;
		x-=lowbit(x);
	}
	return sum1;
}
int main()
{
	long long j,i;
	long long ans;
	scanf("%lld",&n);
	for(i=1; i<=3; i++)
		for(j=1; j<=n; j++)
		{
			scanf("%lld",&z[i][j]);
			sum[i][j]=sum[i][j-1]+z[i][j];

		}
	
	for(i=1; i<=n; i++)
	{
		a[i]=sum[1][i]-sum[2][i-1];
		b[i]=sum[3][i-1]-sum[2][i]-sum[3][n];
		vs.push_back(a[i]) ;
		vs.push_back(b[i]) ;
	}
	sort(vs.begin() ,vs.end());
	vs.erase(unique(vs.begin() ,vs.end() ),vs.end() );
	
	ans=0;
	for(i=n; i>=1; i--)
	{
		add(find(b[i]));
		ans=(ans+query(find(a[i])))%mod;
	}
	printf("%lld",ans%mod);
	return 0;
}