3 seconds
256 megabytes
standard input
standard output
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.
Petya brought home string s with the length of n. The string only consists of lucky digits. The digits are numbered from the left to the right starting with 1. Now Petya should execute m queries of the following form:
- switch l r — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from l to r, inclusive: each digit 4 is replaced with 7 and each digit 7 is replaced with 4 (1 ≤ l ≤ r ≤ n);
- count — find and print on the screen the length of the longest non-decreasing subsequence of string s.
Subsequence of a string s is a string that can be obtained from s by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.
Help Petya process the requests.
The first line contains two integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 3·105) — the length of the string s and the number of queries correspondingly. The second line contains n lucky digits without spaces — Petya's initial string. Next m lines contain queries in the form described in the statement.
For each query count print an answer on a single line.
2 3
47
count
switch 1 2
count
2
1
3 5
747
count
switch 1 1
count
switch 1 3
count
2
3
2
In the first sample the chronology of string s after some operations are fulfilled is as follows (the sought maximum subsequence is marked with bold):
- 47
- 74
- 74
In the second sample:
- 747
- 447
- 447
- 774
- 774
比较好写……
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
char s[maxn];
int num[maxn],Mark[maxn<<];
int M1[maxn<<],M2[maxn<<];
int M3[maxn<<],M4[maxn<<];
int tot[maxn<<],n,Q;
//M1:00 M2:11 M3:01 M4:10 void Swich(int x){
swap(M1[x],M2[x]);
swap(M3[x],M4[x]);
Mark[x]^=;
} void Push_down(int x,int l,int r){
if(!Mark[x]||l==r)return;
Swich(x<<);Swich(x<<|);
Mark[x]=;
} void Push_up(int x){
M1[x]=M1[x<<]+M1[x<<|];
M2[x]=M2[x<<]+M2[x<<|];
M3[x]=max(M1[x<<]+M2[x<<|],max(M1[x<<]+M3[x<<|],M3[x<<]+M2[x<<|]));
M4[x]=max(M2[x<<]+M1[x<<|],max(M4[x<<]+M1[x<<|],M2[x<<]+M4[x<<|]));
} void Build(int x,int l,int r){
if(l==r){
M1[x]=num[l]^;
M2[x]=num[l];
return;
}
int mid=(l+r)>>;
Build(x<<,l,mid);
Build(x<<|,mid+,r);
Push_up(x);
} void Update(int x,int l,int r,int a,int b){
Push_down(x,l,r);
if(l>=a&&r<=b){
Swich(x);
return;
}
int mid=(l+r)>>;
if(mid>=a)Update(x<<,l,mid,a,b);
if(mid<b)Update(x<<|,mid+,r,a,b);
Push_up(x);
} char op[];
int main(){
scanf("%d%d",&n,&Q);
scanf("%s",s+);
for(int i=;i<=n;i++){
num[i]=s[i]==''?:;
}
Build(,,n);
int a,b;
while(Q--){
scanf("%s",op);
if(op[]=='s'){
scanf("%d%d",&a,&b);
Update(,,n,a,b);
}
else
printf("%d\n",max(max(M1[],M2[]),M3[]));
}
return ;
}