#include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 1e9 + 7; void rec_update(int const node, vector<int> & tree) { if(node == 0) return; tree[node] = tree[2*node] + tree[2*node + 1]; tree[node] %= MOD; rec_update(node/2, tree); } void tree_update(int const node, int const val, int const pow, vector<int> & tree) { tree[pow + node - 1] += val; tree[pow + node - 1] %= MOD; rec_update((pow + node - 1) / 2, tree); } int rec_query(int const node, int const node_beg, int const node_end, int const beg, int const end, vector<int> const & tree) { if(beg <= node_beg && end >= node_end) { return tree[node]; } int mid = (node_beg + node_end) / 2; int result = 0; if(beg <= mid) result += rec_query(2*node, node_beg, mid, beg, end, tree); result %= MOD; if(end > mid) result += rec_query(2*node+1, mid+1, node_end, beg, end, tree); result %= MOD; return result; } int tree_query(int const beg, int const end, int const pow, vector<int> const & tree) { return rec_query(1, 1, pow, beg, end, tree); } void solve(){ int n; cin >> n; vector<int> numbers(n); for(int i = 0; i < n; i++) { cin >> numbers[i]; } vector<int> sum_pref(n); sum_pref[0] = numbers[0]; for(int i = 1; i < n; i++) { sum_pref[i] = (sum_pref[i-1] + numbers[i]) % MOD; } vector<int> sort_sum_pref = sum_pref; sort(sort_sum_pref.begin(), sort_sum_pref.end()); vector<int> unique_sort_sum_pref[2]; unique_sort_sum_pref[0].push_back(-2); unique_sort_sum_pref[1].push_back(-1); for(int i = 0; i < n; i++) { if(sort_sum_pref[i] % 2 == 0) { if(sort_sum_pref[i] != unique_sort_sum_pref[0].back()) unique_sort_sum_pref[0].push_back(sort_sum_pref[i]); } else { if(sort_sum_pref[i] != unique_sort_sum_pref[1].back()) unique_sort_sum_pref[1].push_back(sort_sum_pref[i]); } } int pow[2] = {1, 1}; while(pow[0] <= unique_sort_sum_pref[0].size()) pow[0] *= 2; while(pow[1] <= unique_sort_sum_pref[1].size()) pow[1] *= 2; vector<int> tree[2] = {vector<int>(2*pow[0], 0), vector<int>(2*pow[1], 0)}; for(int i = 0; i < n; i++) { int current_result = 0; if(sum_pref[i] % 2 == 0) { int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin(); int indodd = upper_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin(); current_result += 1; current_result += tree_query(1, indeven, pow[0], tree[0]); current_result %= MOD; if(indodd < unique_sort_sum_pref[1].size()) current_result += tree_query(indodd, pow[1], pow[1], tree[1]); current_result %= MOD; tree_update(indeven, current_result, pow[0], tree[0]); } else { int indodd = lower_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin(); int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin(); current_result += tree_query(1, indodd, pow[1], tree[1]); current_result %= MOD; if(indeven < unique_sort_sum_pref[0].size()) current_result += tree_query(indeven, pow[0], pow[0], tree[0]); current_result %= MOD; tree_update(indodd, current_result, pow[1], tree[1]); } if(i == n-1) cout << current_result << "\n"; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 1e9 + 7; void rec_update(int const node, vector<int> & tree) { if(node == 0) return; tree[node] = tree[2*node] + tree[2*node + 1]; tree[node] %= MOD; rec_update(node/2, tree); } void tree_update(int const node, int const val, int const pow, vector<int> & tree) { tree[pow + node - 1] += val; tree[pow + node - 1] %= MOD; rec_update((pow + node - 1) / 2, tree); } int rec_query(int const node, int const node_beg, int const node_end, int const beg, int const end, vector<int> const & tree) { if(beg <= node_beg && end >= node_end) { return tree[node]; } int mid = (node_beg + node_end) / 2; int result = 0; if(beg <= mid) result += rec_query(2*node, node_beg, mid, beg, end, tree); result %= MOD; if(end > mid) result += rec_query(2*node+1, mid+1, node_end, beg, end, tree); result %= MOD; return result; } int tree_query(int const beg, int const end, int const pow, vector<int> const & tree) { return rec_query(1, 1, pow, beg, end, tree); } void solve(){ int n; cin >> n; vector<int> numbers(n); for(int i = 0; i < n; i++) { cin >> numbers[i]; } vector<int> sum_pref(n); sum_pref[0] = numbers[0]; for(int i = 1; i < n; i++) { sum_pref[i] = (sum_pref[i-1] + numbers[i]) % MOD; } vector<int> sort_sum_pref = sum_pref; sort(sort_sum_pref.begin(), sort_sum_pref.end()); vector<int> unique_sort_sum_pref[2]; unique_sort_sum_pref[0].push_back(-2); unique_sort_sum_pref[1].push_back(-1); for(int i = 0; i < n; i++) { if(sort_sum_pref[i] % 2 == 0) { if(sort_sum_pref[i] != unique_sort_sum_pref[0].back()) unique_sort_sum_pref[0].push_back(sort_sum_pref[i]); } else { if(sort_sum_pref[i] != unique_sort_sum_pref[1].back()) unique_sort_sum_pref[1].push_back(sort_sum_pref[i]); } } int pow[2] = {1, 1}; while(pow[0] <= unique_sort_sum_pref[0].size()) pow[0] *= 2; while(pow[1] <= unique_sort_sum_pref[1].size()) pow[1] *= 2; vector<int> tree[2] = {vector<int>(2*pow[0], 0), vector<int>(2*pow[1], 0)}; for(int i = 0; i < n; i++) { int current_result = 0; if(sum_pref[i] % 2 == 0) { int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin(); int indodd = upper_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin(); current_result += 1; current_result += tree_query(1, indeven, pow[0], tree[0]); current_result %= MOD; if(indodd < unique_sort_sum_pref[1].size()) current_result += tree_query(indodd, pow[1], pow[1], tree[1]); current_result %= MOD; tree_update(indeven, current_result, pow[0], tree[0]); } else { int indodd = lower_bound(unique_sort_sum_pref[1].begin(), unique_sort_sum_pref[1].end(), sum_pref[i]) - unique_sort_sum_pref[1].begin(); int indeven = lower_bound(unique_sort_sum_pref[0].begin(), unique_sort_sum_pref[0].end(), sum_pref[i]) - unique_sort_sum_pref[0].begin(); current_result += tree_query(1, indodd, pow[1], tree[1]); current_result %= MOD; if(indeven < unique_sort_sum_pref[0].size()) current_result += tree_query(indeven, pow[0], pow[0], tree[0]); current_result %= MOD; tree_update(indodd, current_result, pow[1], tree[1]); } if(i == n-1) cout << current_result << "\n"; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; } |