2018.11.07-1015-幸运字符串查询（lucky）

题目描述：

KC研究完了幸运数列，又开始对幸运字符串感兴趣（KC似乎不是个正常人）。幸运字符串是一个只包括'4'和'7'的字符串。现在KC手中有个长度为N(1<=N<=1,000,000)的幸运字符串。天生调皮爱玩的KC开始玩起了这个字符串，他的玩法是每次从这个字符串中选定一段区间[l,r]，将这段区间上的所有'4'换成'7'，所有'7'换成'4'。

但是KC过了很久终于意识到自己玩的东西太无聊了，于是他找来你陪他玩，他会在变换玩若干区间后突然问你一个问题：当前这个幸运字符串的最长不降子序列的长度是多少？

现在给出N和M，以及KC手中原有的幸运字符串，M为KC自己玩的次数加上询问你的次数，还有M次的信息。

输入：

第一行包括N,M,M<=300，000.
第二行是一个长度为N的幸运字符串。
接下来M行，每行一个操作信息，游戏中会按照给定的顺序执行操作。。
switch l r表示KC对区间[l,r]进行了变换。
count表示KC向你提问了，你必须输出你的答案。

输出：

每行对应一个count。

算法标签：线段树

线段树是万能的小声bb

思路：

考虑每个不下降序列只能有单个4或者单个7或者前一段4和后一段7组成，于是我们维护每个序列里4的个数，7的个数，以及连续一段4连接一段7，以及连续一段7再一段4的个数。

觉得自己的代码非常简单易懂，再小声bb

以下代码：

#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=1e6+5;
char ss[10];
int n,m,a[N],_4[N<<2],_7[N<<2],_47[N<<2],_74[N<<2],rev[N<<2];
il int read(){int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}
il int r(){int x;char ch;_(!);x=ch^48;return x;}
il void update(int x){
    _4[x]=_4[x<<1]+_4[x<<1|1];_7[x]=_7[x<<1]+_7[x<<1|1];
    _47[x]=max(_4[x<<1]+_7[x<<1|1],_4[x<<1]+_47[x<<1|1]);
    _47[x]=max(_47[x],_47[x<<1]+_7[x<<1|1]);
    _74[x]=max(_7[x<<1]+_4[x<<1|1],_74[x<<1]+_4[x<<1|1]);
    _74[x]=max(_74[x],_7[x<<1]+_74[x<<1|1]);
}
il void pushdown(int x){
    if(!rev[x])return;
    swap(_4[x<<1],_7[x<<1]);swap(_47[x<<1],_74[x<<1]);rev[x<<1]^=1;rev[x]=0;
    swap(_4[x<<1|1],_7[x<<1|1]);swap(_47[x<<1|1],_74[x<<1|1]);rev[x<<1|1]^=1;
}
il void build(int x,int l,int r){
    if(l==r){if(a[l]==4)_4[x]=1;else _7[x]=1;return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    update(x);
}
il void change(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        swap(_4[x],_7[x]);swap(_47[x],_74[x]);rev[x]^=1;return;
    }
    int mid=(l+r)>>1;pushdown(x);
    if(ql<=mid)change(x<<1,l,mid,ql,qr);
    if(mid<qr)change(x<<1|1,mid+1,r,ql,qr);
    update(x);
}
int main()
{
    n=read();m=read();for(int i=1;i<=n;i++)a[i]=r();
    build(1,1,n);
    while(m--){
        scanf(" %s",ss);
        if(ss[0]=='c'){
            printf("%d
",max(_4[1],max(_7[1],_47[1])));
        }
        if(ss[0]=='s'){
            int x=read(),y=read();change(1,1,n,x,y);
        }
    }
  return 0;
}

View Code