#include <stdio.h> using ll=long long; const int C=350001, M=1000000007, Cv=1<<20; ll val[2*Cv][2]; ll query(int start, int end, int parity){ int l=start+Cv, r=end+Cv; if (l>r) return 0; ll res=val[l][parity]; if (l!=r) res=(res+val[r][parity])%M; for (; l>0; l/=2,r/=2){ if (l%2==0 && r-l>1) res = (res+val[l+1][parity])%M; if (r%2==1 && r-l>1) res = (res+val[r-1][parity])%M; } return res; } void insert(int pos, ll res, int parity){ for (pos+=Cv; pos>0; pos/=2) val[pos][parity] = (val[pos][parity]+res)%M; } ll pom[C]; void Sebasort (ll tab[], int l, int r){ int lim=2, limi=l+1, limj=l+2, j=limi, i=l, k=l; while (lim/2<=r-l+1){ while (i<=r){ if (limj>r) limj=r+1; if ((j<limj&&tab[j]<tab[i])||i>=limi) pom[k]=tab[j], j++; else pom[k]=tab[i], i++; k++; if (i==limi&&j==limj) limi+=lim, limj+=lim, i=j, j=limi; } for (i=l;i<=r;i++) tab[i]=pom[i]; lim*=2, limi=l+lim/2, limj=l+lim, j=limi, i=k=l; } } inline int bin (ll v, ll tab[], int l, int r){ int m; while (l<=r){ m=(l+r)/2; if (tab[m]==v) return m; if (tab[m]>v) r=m-1; else l=m+1; } return -1; } ll summa[C], a[C], post_summa[C], finale[C], value[C]; int main(){ int n, i, m; scanf ("%d", &n); for (i=0; i<n; i++) scanf ("%lld", &a[i]); summa[0] = a[0]; for (i=1; i<n; i++) summa[i] = (summa[i-1] + a[i])%M; for (i=0; i<n; i++) post_summa[i] = summa[i]; post_summa[n]=0; Sebasort(post_summa, 0, n); int i_values = 0; for (i=1; i<=n; i++){ if (post_summa[i] != post_summa[i-1]) { value[i_values] = post_summa[i-1]; i_values++; } } value[i_values] = post_summa[n]; i_values++; ll res; insert(0, 1, 0); //starter for (i=0; i<n; i++){ res = 0; m = bin(summa[i], value, 0, i_values); if (summa[i]%2 == 0){ res = (res + query(0, m, 0))%M; res = (res + query(m+1, n, 1))%M; } if (summa[i]%2 == 1){ res = (res + query(0, m, 1))%M; res = (res + query(m+1, n, 0))%M; } insert(m, res, summa[i]%2); finale[i] = res; } printf("%lld\n", finale[n-1]); 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 | #include <stdio.h> using ll=long long; const int C=350001, M=1000000007, Cv=1<<20; ll val[2*Cv][2]; ll query(int start, int end, int parity){ int l=start+Cv, r=end+Cv; if (l>r) return 0; ll res=val[l][parity]; if (l!=r) res=(res+val[r][parity])%M; for (; l>0; l/=2,r/=2){ if (l%2==0 && r-l>1) res = (res+val[l+1][parity])%M; if (r%2==1 && r-l>1) res = (res+val[r-1][parity])%M; } return res; } void insert(int pos, ll res, int parity){ for (pos+=Cv; pos>0; pos/=2) val[pos][parity] = (val[pos][parity]+res)%M; } ll pom[C]; void Sebasort (ll tab[], int l, int r){ int lim=2, limi=l+1, limj=l+2, j=limi, i=l, k=l; while (lim/2<=r-l+1){ while (i<=r){ if (limj>r) limj=r+1; if ((j<limj&&tab[j]<tab[i])||i>=limi) pom[k]=tab[j], j++; else pom[k]=tab[i], i++; k++; if (i==limi&&j==limj) limi+=lim, limj+=lim, i=j, j=limi; } for (i=l;i<=r;i++) tab[i]=pom[i]; lim*=2, limi=l+lim/2, limj=l+lim, j=limi, i=k=l; } } inline int bin (ll v, ll tab[], int l, int r){ int m; while (l<=r){ m=(l+r)/2; if (tab[m]==v) return m; if (tab[m]>v) r=m-1; else l=m+1; } return -1; } ll summa[C], a[C], post_summa[C], finale[C], value[C]; int main(){ int n, i, m; scanf ("%d", &n); for (i=0; i<n; i++) scanf ("%lld", &a[i]); summa[0] = a[0]; for (i=1; i<n; i++) summa[i] = (summa[i-1] + a[i])%M; for (i=0; i<n; i++) post_summa[i] = summa[i]; post_summa[n]=0; Sebasort(post_summa, 0, n); int i_values = 0; for (i=1; i<=n; i++){ if (post_summa[i] != post_summa[i-1]) { value[i_values] = post_summa[i-1]; i_values++; } } value[i_values] = post_summa[n]; i_values++; ll res; insert(0, 1, 0); //starter for (i=0; i<n; i++){ res = 0; m = bin(summa[i], value, 0, i_values); if (summa[i]%2 == 0){ res = (res + query(0, m, 0))%M; res = (res + query(m+1, n, 1))%M; } if (summa[i]%2 == 1){ res = (res + query(0, m, 1))%M; res = (res + query(m+1, n, 0))%M; } insert(m, res, summa[i]%2); finale[i] = res; } printf("%lld\n", finale[n-1]); return 0;} |