#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
struct Matrix{
int data[2][2];
Matrix (int x=0){
for (int i=0; i<2; ++i) for (int j=0; j<2; ++j) data[i][j]=(i==j)&x;
}
auto & operator[](int x){ return data[x]; }
const auto & operator[](int x) const { return data[x]; }
Matrix operator*(const Matrix &b){
Matrix c;
for (int i=0; i<2; ++i) for (int k=0; k<2; ++k) for (int j=0; j<2; ++j){
c[i][j]=(c[i][j]+data[i][k]*b[k][j])%mod;
}
return c;
}
Matrix pow(int y){
Matrix x=*this, t(1);
while (y){
if (y&1) t=t*x;
x=x*x;
y>>=1;
}
return t;
}
};
struct SegmentTree{
int n;
vector<Matrix> t;
void init(int _n){
n=_n;
t.assign(4*n+1, Matrix(1));
}
void update(int k, int l, int r, int pos, const Matrix &val){
if (l==r){
t[k]=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) update(k<<1, l, mid, pos, val);
else update(k<<1|1, mid+1, r, pos, val);
t[k]=t[k<<1]*t[k<<1|1];
}
int get(){
return t[1][0][0];
}
} seg;
const int N=1e5+10;
int n, a[N], f[N][2];
vector<pair<int, int>> v[N];
int32_t main(){
// freopen("fib.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=1; i<=n; ++i) cin >> a[i];
map<int, int> mp;
set<pair<int, int>> st;
for (int i=1; i<=n; ++i){
auto it=st.lower_bound(make_pair(a[i], 2e9));
if (it!=st.begin()){
--it;
int l=it->first, r=it->second;
if (l<=a[i] && a[i]<=r){
if ((l&1)==(a[i]&1)){
st.erase(it), v[i].emplace_back(l, -1);
if (a[i]!=r) st.emplace(a[i]+2, r), v[i].emplace_back(a[i]+2, r);
if (l==1){
st.emplace(2, a[i]+1), v[i].emplace_back(2, a[i]+1);
}else if (l==2){
st.emplace(1, a[i]+1), v[i].emplace_back(1, a[i]+1);
}else{
st.emplace(l+1, a[i]+1), v[i].emplace_back(l+1, a[i]+1);
st.emplace(l-2, l-2), v[i].emplace_back(l-2, l-2);
}
}else{
st.erase(it), v[i].emplace_back(l, -1);
if (l<=a[i]-1) st.emplace(l, a[i]-1), v[i].emplace_back(l, a[i]-1);
if (a[i]+1<=r) st.emplace(a[i]+1, r), v[i].emplace_back(a[i]+1, r);
st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
}
}else st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
}else st.emplace(a[i], a[i]), v[i].emplace_back(a[i], a[i]);
it=st.lower_bound(make_pair(a[i], 2e9));
if (it!=st.begin()) --it;
if (it!=st.begin()) --it;
if (it!=st.begin()) --it;
for (int _=0; _<5; ++_){
if (it==st.end() || next(it)==st.end()) break;
int l1=it->first, r1=it->second, l2=next(it)->first, r2=next(it)->second;
if (r1+1==l2){
if (l2==r2){
if (next(next(it))!=st.end() && next(next(it))->first==r2+1){
++it;
continue;
}
}
v[i].emplace_back(l2, -1);
st.erase(next(it));
v[i].emplace_back(l1, -1);
st.erase(it);
if (l1!=r1) st.emplace(l1, r1-2), v[i].emplace_back(l1, r1-2);
it=st.emplace(r2+1, r2+1).first, v[i].emplace_back(r2+1, r2+1);
}else ++it;
}
it=st.lower_bound(make_pair(a[i], 2e9));
if (it!=st.begin()) --it;
if (it!=st.begin()) --it;
if (it!=st.begin()) --it;
for (int _=0; _<5; ++_){
if (it==st.end() || next(it)==st.end()) break;
int l1=it->first, r1=it->second, l2=next(it)->first, r2=next(it)->second;
if (r1+2==l2){
v[i].emplace_back(l2, -1);
st.erase(next(it));
v[i].emplace_back(l1, -1);
st.erase(it);
it=st.emplace(l1, r2).first, v[i].emplace_back(l1, r2);
}else ++it;
}
}
// for (int i=1; i<=n; ++i){
// for (int j=0; j<(int)v[i].size(); ++j){
// if (v[i][j].second==-1){
// for (int k=0; k<j; ++k) if (v[i][k].first==v[i][j].first){
// v[i].erase(v[i].begin()+k);
// --j;
// break;
// }
// }
// }
// }
vector<int> vals{-1};
for (int i=1; i<=n; ++i) for (auto &j:v[i]) vals.push_back(j.first);
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end())-vals.begin());
seg.init((int)vals.size()-1);
auto get_pos=[&](int x) -> int {
return lower_bound(vals.begin(), vals.end(), x)-vals.begin();
};
st.clear();
for (int i=1; i<=n; ++i){
for (auto &j:v[i]){
if (j.second==-1){
auto it=st.lower_bound({j.first, 0});
{
int pos=get_pos(j.first);
seg.update(1, 1, seg.n, pos, Matrix(1));
}
it=st.erase(it);
if (it!=st.end()){
int pos=get_pos(it->first);
Matrix d;
int l=it==st.begin()?0:prev(it)->second;
int r=it->first;
d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
Matrix d2(1);
d2[1][0]=(it->second-it->first)/2;
seg.update(1, 1, seg.n, pos, d*d2);
}
}else{
auto it=st.insert(j).first;
{
int pos=get_pos(j.first);
Matrix d;
int l=it==st.begin()?0:prev(it)->second;
int r=it->first;
d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
Matrix d2(1);
d2[1][0]=(it->second-it->first)/2;
seg.update(1, 1, seg.n, pos, d*d2);
}
++it;
if (it!=st.end()){
int pos=get_pos(it->first);
Matrix d;
int l=it==st.begin()?0:prev(it)->second;
int r=it->first;
d[0][0]=(r-l+1)/2; d[0][1]=d[0][0]-1; d[1][0]=d[1][1]=(l&1)==(r&1);
Matrix d2(1);
d2[1][0]=(it->second-it->first)/2;
seg.update(1, 1, seg.n, pos, d*d2);
}
}
}
cout << seg.get() << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
2 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
2 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
4700 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
2 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
4700 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
13 |
Correct |
1 ms |
4700 KB |
Output is correct |
14 |
Correct |
1 ms |
4700 KB |
Output is correct |
15 |
Correct |
1 ms |
4700 KB |
Output is correct |
16 |
Correct |
1 ms |
4700 KB |
Output is correct |
17 |
Correct |
1 ms |
4700 KB |
Output is correct |
18 |
Correct |
2 ms |
4700 KB |
Output is correct |
19 |
Correct |
1 ms |
4700 KB |
Output is correct |
20 |
Correct |
1 ms |
4700 KB |
Output is correct |
21 |
Correct |
1 ms |
4700 KB |
Output is correct |
22 |
Correct |
1 ms |
4700 KB |
Output is correct |
23 |
Correct |
2 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
2 |
Correct |
315 ms |
28872 KB |
Output is correct |
3 |
Correct |
425 ms |
29072 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
2 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4700 KB |
Output is correct |
10 |
Correct |
2 ms |
4700 KB |
Output is correct |
11 |
Correct |
2 ms |
4700 KB |
Output is correct |
12 |
Correct |
2 ms |
4696 KB |
Output is correct |
13 |
Correct |
1 ms |
4700 KB |
Output is correct |
14 |
Correct |
1 ms |
4700 KB |
Output is correct |
15 |
Correct |
1 ms |
4700 KB |
Output is correct |
16 |
Correct |
1 ms |
4700 KB |
Output is correct |
17 |
Correct |
1 ms |
4700 KB |
Output is correct |
18 |
Correct |
2 ms |
4700 KB |
Output is correct |
19 |
Correct |
1 ms |
4700 KB |
Output is correct |
20 |
Correct |
1 ms |
4700 KB |
Output is correct |
21 |
Correct |
1 ms |
4700 KB |
Output is correct |
22 |
Correct |
1 ms |
4700 KB |
Output is correct |
23 |
Correct |
2 ms |
4700 KB |
Output is correct |
24 |
Correct |
2 ms |
4700 KB |
Output is correct |
25 |
Correct |
315 ms |
28872 KB |
Output is correct |
26 |
Correct |
425 ms |
29072 KB |
Output is correct |
27 |
Correct |
70 ms |
12068 KB |
Output is correct |
28 |
Correct |
147 ms |
17120 KB |
Output is correct |
29 |
Correct |
102 ms |
12836 KB |
Output is correct |
30 |
Correct |
150 ms |
17620 KB |
Output is correct |
31 |
Correct |
173 ms |
19852 KB |
Output is correct |
32 |
Correct |
190 ms |
16836 KB |
Output is correct |
33 |
Correct |
215 ms |
17868 KB |
Output is correct |
34 |
Correct |
163 ms |
18372 KB |
Output is correct |
35 |
Correct |
247 ms |
16944 KB |
Output is correct |
36 |
Correct |
312 ms |
18456 KB |
Output is correct |
37 |
Correct |
445 ms |
21724 KB |
Output is correct |
38 |
Correct |
307 ms |
29780 KB |
Output is correct |
39 |
Correct |
141 ms |
18992 KB |
Output is correct |
40 |
Correct |
245 ms |
27732 KB |
Output is correct |
41 |
Correct |
646 ms |
29304 KB |
Output is correct |
42 |
Correct |
295 ms |
29892 KB |
Output is correct |
43 |
Correct |
267 ms |
29116 KB |
Output is correct |
44 |
Correct |
187 ms |
32368 KB |
Output is correct |
45 |
Correct |
425 ms |
31156 KB |
Output is correct |
46 |
Correct |
225 ms |
31808 KB |
Output is correct |
47 |
Correct |
384 ms |
31028 KB |
Output is correct |
48 |
Correct |
365 ms |
32444 KB |
Output is correct |
49 |
Correct |
463 ms |
31780 KB |
Output is correct |
50 |
Correct |
363 ms |
29880 KB |
Output is correct |