监狱逃亡

题目描述：

3 * n的地图，每个点都有一个权值，你现在在 $(1, 1)$，你要到 $(3, n)$，每次只能往下或者往右走，问走过的路径的权值总和大于等于0的不同的路径的数量，对1e9 + 7取模

思路：

不难发现只会往下走两次，我们假设第一次在第i个位置往下走，第二次在第j个位置往下走，这样根据前缀和我们可以得出路径的权值和是： $sum[1][i] + sum[2][j] - sum[2][i - 1] + sum[3][n] - sum[3][j - 1] >= 0$

我们将i 和 j分开,因为 $i <= j$ ，所以我们让符号也是 <=，就变成了 $sum[2][i-1] - sum[1][i]-sum[3][n] <= sum[2][j] - sum[3][j - 1]$

这样就可以直接用树状数组来统计答案，注意要离散化一下，我们遍历每个i，先查询 $sum[2][i] - sum[3][i - 1]$，看看有多少个小于他的，再插入 $sum[2][i-1] - sum[1][i]-sum[3][n]$

如果化简的时候符号选择的是>=，那就变成了类似于求逆序对了，就不是很好做

坑点是树状数组要加到2 * n才行，因为离散化的时候可能数字都不一样，所以要搞到2 * n，还有就是树状数组不能插入0，用vector的二分的时候第一个元素的下标是0，要加1

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m;
ll tr[5][MAX];
ll sum[5][MAX];
ll tree[MAX];

inline ll lowbit(ll x){
    return x & (-x);
}

inline void update(ll i, ll c){
    while (i <= 2 * n) {
        tree[i] += c;
        i += lowbit(i);
    }
}

inline ll getans(ll i){
    ll ans = 0;
    while (i) {
        ans += tree[i];
        i -= lowbit(i);
    }
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= 3; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> tr[i][j];
            sum[i][j] = sum[i][j - 1] + tr[i][j];
        }
    }
    vector<ll>ar;
    for(int i = 1; i <= n; ++i){
        ar.push_back(sum[2][i - 1] - sum[1][i] - sum[3][n]);
        ar.push_back(sum[2][i] - sum[3][i - 1]);
    }
    sort(ar.begin(), ar.end());
    ar.erase(unique(ar.begin(), ar.end()), ar.end());
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        int p = (int)((lower_bound(ar.begin(), ar.end(), sum[2][i - 1] - sum[1][i] - sum[3][n])) - ar.begin());
        update(p + 1, 1);
        p = (int)((lower_bound(ar.begin(), ar.end(), sum[2][i] - sum[3][i - 1])) - ar.begin());
        ans += getans(p + 1);
    }
    cout << ans % mod << endl;
    
}


int main(){
    io;
    work();
    return 0;
}