#include <bits/stdc++.h> using namespace std; #define st first #define nd second #define iamspeed ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) int n, t[300003], modd = 1e9 + 7, ind = 1, roz, leaves = 1, ile, tree[2][1048580]; map<int, int> mp; pair<int, int> pref[300003]; void quary(int A, int B, int l, int r, int val, int w, int tr) { if(r < A || l > B) return; else if(l >= A && r <= B) { if(val == 0) { ile = (ile + tree[tr][w]) % modd; } tree[tr][w] = (tree[tr][w] + val) % modd; return; } int mid = (l + r) / 2; quary(A, B, l, mid, val, w * 2, tr); quary(A, B, mid + 1, r, val, w * 2 + 1, tr); tree[tr][w] = (tree[tr][w * 2] + tree[tr][w * 2 + 1]) % modd; } int main() { iamspeed; cin >> n; for(int i = 1 ; i <= n ; i++) { cin >> t[i]; pref[i].st = (pref[i - 1].st + t[i]) % modd; pref[i].nd = pref[i].st % 2; if(!mp[pref[i].st]) { mp[pref[i].st] = 1; roz++; } } while(leaves < roz + 1) { leaves *= 2; } for(auto it = mp.begin() ; it != mp.end() ; it++) { it->nd = ++ind; } for(int i = 1 ; i <= n ; i++) { pref[i].st = mp[pref[i].st]; } quary(1, 1, 1, leaves, 1, 1, 0); for(int i = 1 ; i <= n ; i++) { ile = 0; quary(1, pref[i].st, 1, leaves, 0, 1, pref[i].nd); quary(pref[i].st + 1, leaves, 1, leaves, 0, 1, 1 - pref[i].nd); if(i != n) quary(pref[i].st, pref[i].st, 1, leaves, ile, 1, pref[i].nd); else cout << ile % modd << endl; } }
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 | #include <bits/stdc++.h> using namespace std; #define st first #define nd second #define iamspeed ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) int n, t[300003], modd = 1e9 + 7, ind = 1, roz, leaves = 1, ile, tree[2][1048580]; map<int, int> mp; pair<int, int> pref[300003]; void quary(int A, int B, int l, int r, int val, int w, int tr) { if(r < A || l > B) return; else if(l >= A && r <= B) { if(val == 0) { ile = (ile + tree[tr][w]) % modd; } tree[tr][w] = (tree[tr][w] + val) % modd; return; } int mid = (l + r) / 2; quary(A, B, l, mid, val, w * 2, tr); quary(A, B, mid + 1, r, val, w * 2 + 1, tr); tree[tr][w] = (tree[tr][w * 2] + tree[tr][w * 2 + 1]) % modd; } int main() { iamspeed; cin >> n; for(int i = 1 ; i <= n ; i++) { cin >> t[i]; pref[i].st = (pref[i - 1].st + t[i]) % modd; pref[i].nd = pref[i].st % 2; if(!mp[pref[i].st]) { mp[pref[i].st] = 1; roz++; } } while(leaves < roz + 1) { leaves *= 2; } for(auto it = mp.begin() ; it != mp.end() ; it++) { it->nd = ++ind; } for(int i = 1 ; i <= n ; i++) { pref[i].st = mp[pref[i].st]; } quary(1, 1, 1, leaves, 1, 1, 0); for(int i = 1 ; i <= n ; i++) { ile = 0; quary(1, pref[i].st, 1, leaves, 0, 1, pref[i].nd); quary(pref[i].st + 1, leaves, 1, leaves, 0, 1, 1 - pref[i].nd); if(i != n) quary(pref[i].st, pref[i].st, 1, leaves, ile, 1, pref[i].nd); else cout << ile % modd << endl; } } |