#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
struct node
{
int val, val1, val3, val31;
int valmic, valmic1, valmic3, valmic31;
bool ok, ok1, ok3, ok31;
node()
{
val = val1 = val3 = val31 = 0;
valmic = valmic1 = valmic3 = valmic31 = 0;
ok = ok1 = ok3 = ok31 = false;
}
};
int n,q,v[100005];
node ai[1000005];
node Merge(node a, node b)
{
node rez;
rez.val = (1LL * a.val * b.val % Mod - 1LL * a.val1 * b.val3 % Mod + Mod) % Mod;
rez.val1 = (1LL * a.val * b.val1 % Mod - 1LL * a.val1 * b.val31 % Mod + Mod) % Mod;
rez.val3 = (1LL * a.val3 * b.val % Mod - 1LL * a.val31 * b.val1 % Mod + Mod) % Mod;
rez.val31 = (1LL * a.val3 * b.val1 % Mod - 1LL * a.val31 * b.val31 % Mod + Mod) % Mod;
rez.valmic = ((1LL * a.valmic * b.val % Mod - 1LL * a.valmic1 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic % Mod - 1LL * a.ok1 * b.valmic3 % Mod + Mod)) % Mod;
rez.valmic1 = ((1LL * a.valmic * b.val1 % Mod - 1LL * a.valmic1 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic1 % Mod - 1LL * a.ok1 * b.valmic31 % Mod + Mod)) % Mod;
rez.valmic3 = ((1LL * a.valmic3 * b.val % Mod - 1LL * a.valmic31 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic % Mod - 1LL * a.ok31 * b.valmic1 % Mod + Mod)) % Mod;
rez.valmic31 = ((1LL * a.valmic3 * b.val1 % Mod - 1LL * a.valmic31 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic1 % Mod - 1LL * a.ok31 * b.valmic31 % Mod + Mod)) % Mod;
rez.ok = (a.ok & b.ok & ((!a.ok1)|(!b.ok3)));
rez.ok1 = (rez.ok & a.ok1);
rez.ok3 = (rez.ok & b.ok3);
rez.ok31 = (rez.ok & a.ok1 & b.ok3);
return rez;
}
node Init(int val)
{
node rez;
rez.val = 10;
rez.val1 = 1;
rez.val3 = 1;
rez.val31 = 0;
rez.valmic = val;
rez.valmic1 = (1<val);
rez.valmic3 = (3<val);
rez.valmic31 = 0;
rez.ok = true;
rez.ok1 = (val==1);
rez.ok3 = (val==3);
rez.ok31 = false;
return rez;
}
void update(int poz, int val, int nod, int a, int b)
{
if(a==b)
{
ai[nod] = Init(val);
return;
}
int mij = (a+b)>>1;
if(poz<=mij)
{
update(poz,val,nod*2,a,mij);
}
else
{
update(poz,val,nod*2+1,mij+1,b);
}
ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
}
node query(int qa, int qb, int nod, int a, int b)
{
if(qa<=a && qb>=b)
{
return ai[nod];
}
int mij = (a+b)>>1;
node rez1, rez2;
if(qa<=mij)
{
rez1 = query(qa,qb,nod*2,a,mij);
}
if(qb>mij)
{
rez2 = query(qa,qb,nod*2+1,mij+1,b);
}
if(qa<=mij && qb<=mij)
{
return rez1;
}
if(qa>mij && qb>mij)
{
return rez2;
}
return Merge(rez1,rez2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("nr.in","r",stdin);
// freopen("nr.out","w",stdout);
cin>>n>>q;
cin.get();
for(int i=1;i<=n;i++)
{
char ch;
cin.get(ch);
v[i] = ch - '0';
update(i,v[i],1,1,n);
}
node rez = query(1,n,1,1,n);
cout<<rez.valmic + rez.ok<<'\n';
for(int i=1;i<=q;i++)
{
int t;
cin>>t;
if(t==1)
{
int l,r;
cin>>l>>r;
node rez = query(l,r,1,1,n);
cout<<rez.valmic + rez.ok<<'\n';
}
else
{
int poz,val;
cin>>poz>>val;
update(poz,val,1,1,n);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
35532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
35532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
35552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
35552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
35532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
35532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
