9.22字节跳动笔试

第4题，离散化后权值线段树。

#define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bug(x) cout<<#x<<" is "<<x<<endl
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define rs o * 2 + 1
#define ls o * 2
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
int a[N];
int b[N];
ll d[N * 4];
void up(int o, int l, int r, int pos, int val){
    if(l == r){
        d[o] = (d[o] + val) % mod;
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m) up(ls, l, m, pos, val);
    else up(rs, m + 1, r, pos, val);
    d[o] = (d[ls] + d[rs]) % mod;
}
int qu(int o, int l, int r, int ql, int qr){
    if(l >= ql && r <= qr) return d[o];
    int m = (l + r) / 2;
    int res1 = 0, res2 = 0;
    if(ql <= m) res1 = qu(ls, l, m, ql, qr);
    if(qr > m) res2 = qu(rs, m + 1, r, ql, qr);
    return (res1 + res2) % mod;
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int n1 = unique(b + 1, b + 1 + n) - b - 1;
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + 1 + n1, a[i]) - b;
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll res = 0;
        if(a[i] + 1 <= n1){
            res = qu(1, 1, n1, a[i] + 1, n1);
        }
        ans = (ans + res + 1) % mod;
        up(1, 1, n1, a[i], (res + 1) % mod);
    }
    cout << ans << endl;
}
int main(){
    IO;
    solve();
}