1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
|
#include <cstring> #include <algorithm>
using namespace std;
typedef long long ll;
template <class T> inline bool (T &ret) { char c; int sgn; if(c = getchar() , c == EOF) return false; while(c != '-' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while(c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return true; } const int MAX_N = 500007; const int N = MAX_N; const int MOD = (int)1e9 + 7;
struct Bit { int bit[N]; void clear() { memset(bit, 0, sizeof bit); } void add(int i, int v) { for (;i < N; i += i & -i) if (v > bit[i]) bit[i] = v; } int query(int i) { int re = 0; for (;i > 0; i -= i & -i) re = max(re, bit[i]); return re; } };
int n; int a[MAX_N], b[MAX_N], dp[MAX_N]; int pre[MAX_N];
#include <vector> vector<int> v[MAX_N];
void Main() { rd(n); for (int i = 0; i < n; ++i) rd(a[i]), b[i] = a[i]; sort(b, b + n); int m = unique(b, b + n) - b; for (int i = 0; i < n; ++i) a[i] = lower_bound(b, b + m, a[i]) - b + 2; Bit B; int ans = 0; for (int i = 0; i < n; ++i) { dp[i] = B.query(a[i] - 1); int now = 0; for (int j = 0; j < v[dp[i]].size(); ++j) { int u = v[dp[i]][j]; if (a[u] < a[i]) { now = (now + pre[u]) % MOD; } } if (dp[i] == 0) pre[i] = 1; else pre[i] = now; ans = max(ans, dp[i] + 1); v[dp[i] + 1].push_back(i); B.add(a[i], dp[i] + 1); } int res = 0; for (int i = 0; i < n; ++i) if (ans == dp[i] + 1) res = (res + pre[i]) % MOD; printf("%dn", res); return ; }
int main() { Main(); return 0; }
|
近期评论