Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MX=1e6+4;
- #define left ghfghgf
- #define right ghfghfgh
- int n,ar[MX];
- struct Node
- {
- int fours,sevens,opt47,opt74,lasy;
- Node()
- {
- lasy=fours=sevens=opt47=opt74=0;
- }
- }tree[4*MX];
- Node merge(Node left,Node right)
- {
- Node B;
- int z=left.fours+right.fours,y=left.sevens+right.sevens;
- z=max(z,y);
- B.opt47=max(left.opt47+right.sevens,left.fours+right.opt47);
- B.opt47=max(left.fours+right.sevens,B.opt47);
- B.opt74=max(left.opt74+right.fours,left.sevens+right.opt74);
- B.opt74=max(B.opt74,left.sevens+right.fours);
- B.sevens=right.sevens+left.sevens;
- B.fours=right.fours+left.fours;
- B.opt47=max(B.opt47,z);
- B.opt74=max(B.opt74,z);
- return B;
- }
- int st,en,IN;
- void build(int x=1,int l=1,int r=n)
- {
- if(l==r)
- {
- tree[x].fours=(ar[l]==4);
- tree[x].sevens=(ar[l]==7);
- tree[x].opt47=1;
- tree[x].opt74=1;
- return;
- }
- build(2*x,l,(l+r)/2);
- build(2*x+1,(l+r)/2+1,r);
- tree[x]=merge(tree[x*2],tree[2*x+1]);
- }
- void Switch(Node& S,int lz)
- {
- S.lasy++;
- if((lz)%2)return;
- swap(S.fours,S.sevens);
- swap(S.opt47,S.opt74);
- }
- void update(int x=1,int l=1,int r=n,int lz=0)
- {
- if(r<st||en<l)
- return Switch(tree[x],lz+1);
- if(st<=l&&r<=en)
- return Switch(tree[x],lz);
- update(2*x,l,(l+r)/2,lz+tree[x].lasy);
- update(2*x+1,(l+r)/2+1,r,lz+tree[x].lasy);
- // cout<<l<<' '<<r<<' '<<tree[x].opt74<<endl;
- tree[x]=merge(tree[x*2],tree[2*x+1]);
- }
- int m;
- char bb[MX];
- int main()
- {
- cin>>n>>m;
- scanf("%s",bb);
- for(int i=0;i<n;i++)
- ar[i+1]=bb[i]-'0';
- build();
- for(int i=1;i<=m;i++)
- {
- char cc[22];
- scanf(" %s",cc);
- string h=cc;
- if(h=="switch")
- {
- scanf("%d%d",&st,&en);
- update();
- }
- else
- printf("%d %d\n",tree[1].opt47,tree[1].opt74);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement