Codeforces Round #104 div1 E

分析 ：(这里用0，1代替4，7，写代码时节约内存空间)只有全0或全1或(全0+全1)类型的subsequence满足要求，使用线段树维护区间的四个数据，全0subsequence长度，全1长度，全0+全1长度，全1+全0长度，switch操作时交换一下数据即可 。

code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 4;
struct T {
    int l,r,f[2][2],lazy;
}t[maxn<<2];
char s[maxn];
void Switch(int p)
{
    int tmp=t[p].f[0][0];
    t[p].f[0][0]=t[p].f[1][1],t[p].f[1][1]=tmp;
    tmp=t[p].f[0][1];
    t[p].f[0][1]=t[p].f[1][0],t[p].f[1][0]=tmp;
}
void pushup(int p)
{
    t[p].f[0][0]=t[p*2].f[0][0]+t[p*2+1].f[0][0];
    t[p].f[1][1]=t[p*2].f[1][1]+t[p*2+1].f[1][1];
    t[p].f[0][1]=max(t[p*2].f[0][0]+max(t[p*2+1].f[0][1],t[p*2+1].f[1][1]),t[p*2].f[0][1]+t[p*2+1].f[1][1]);
    t[p].f[1][0]=max(t[p*2].f[1][1]+max(t[p*2+1].f[0][0],t[p*2+1].f[1][0]),t[p*2].f[1][0]+t[p*2+1].f[0][0]);
}
void pushdown(int p)
{
    if(t[p].lazy) {
        Switch(p*2); Switch(p*2+1);
        t[p*2].lazy=(t[p*2].lazy+t[p].lazy)%2;
        t[p*2+1].lazy=(t[p*2+1].lazy+t[p].lazy)%2;
        t[p].lazy=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].lazy=0;
    if(l==r) {
        if(s[l]=='1') t[p].f[1][1]=1;
        else t[p].f[0][0]=1;
        t[p].f[0][1]=t[p].f[1][0]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid); build(p*2+1,mid+1,r);
    pushup(p);
}
void update(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r) {
        Switch(p);
        t[p].lazy=(t[p].lazy+1)%2;//当lazy标记为奇数时才执行Switch和向下修改lazy标记，因为lazy为偶数的时候相当于switch了一次又switch回来了 
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) update(p*2,l,r);
    if(r>mid) update(p*2+1,l,r);
    pushup(p);
}
int main()
{
    int n,m;
    scanf("%d%d%s",&n,&m,s+1);
    for(int i=1;i<=n;i++) 
        if(s[i]=='7') s[i]='1';
        else s[i]='0';
    build(1,1,n);
    while(m--)
    {
        char op[10];
        scanf("%s",op);
        if(op[0]=='s') {
            int l,r;
            scanf("%d%d",&l,&r);
            update(1,l,r);
        }
        else printf("%d\n",max(t[1].f[0][1],max(t[1].f[0][0],t[1].f[1][1])));
    }
    return 0;
}