题目链接：
题目
Problem 1007 幸运数
Time Limit: 2000 mSec
Memory Limit : 131072 KB
问题描述
皮特的幸运数是2和5。只由幸运数字2和5组成的数列，称为幸运数列。对于幸运数列，有两种操作。
1、switch i j
表示数列从第i个数到第j个数中，所有的2改成5，所有的5改成2.例如幸运数列25525，执行switch 2 4操作，则数列变成22255
2、count
表示要求输出当前幸运数列的最长不下降子序列（即子序列中后面的数都不小于前面的数）的长度。例如幸运数列252255，其中222，555，2555是它的不下降子序列，而2525不是，可以看出，最长不下降子序列是22255，长度为5。
现在给出一个长度为n的幸运数列，再依次给出m个操作，对于每个count操作，输出当前幸运数列的最长不下降子序列的长度。
输入
输入包含多组数据。(数据不超过10组)
每组数据的第一行有两个整数n,m（n,m<=100000),分别表示数列的长度和操作个数。
接下来一行，有一个长度为n的只由2和5构成的数列。
接下来m行，每行一个操作，是count或者switch i j，含义如题所述
输出
对于每组数据的每个count操作，都输出一行，包含一个整数，表示当前幸运数列的最长不下降子序列的长度。
样例
input
2 3
25
count
switch 1 2
count
3 5
525
count
switch 1 1
count
switch 1 3
count
output
2
1
2
3
2
题解
可以用线段树跑成段更新。
每个节点维护四个变量，分别表示子序列"22","25","52","55"的长度
在2,5对换的时候，只要交换"22"和"55"；"25"和"52"。
需要懒惰标记。（感觉懒惰标记写搓了。orz，后面学一下）
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson (o<<1)
#define rson ((o<<1)|1)
#define M L+(R-L)/2
using namespace std;
const int maxn=101010;
int sumv[maxn<<2][4],setv[maxn<<2];
int n,m;
char str[maxn];
void pushdown(int o,int L,int R){
if(setv[o]>0){
swap(sumv[o][1],sumv[o][2]);
swap(sumv[o][0],sumv[o][3]);
if(L<R){
setv[lson]^=1; setv[rson]^=1;
}
setv[o]=0;
}
}
void maintain(int o,int L,int R){
if(L==R){
pushdown(o,L,R);
}else{
pushdown(lson,L,M);
pushdown(rson,M+1,R);
sumv[o][0]=sumv[lson][0]+sumv[rson][0];
sumv[o][3]=sumv[lson][3]+sumv[rson][3];
sumv[o][1]=max(sumv[lson][0]+sumv[rson][3],sumv[lson][1]+sumv[rson][3]);
sumv[o][1]=max(sumv[o][1],sumv[lson][0]+sumv[rson][1]);
sumv[o][2]=max(sumv[lson][3]+sumv[rson][0],sumv[lson][2]+sumv[rson][0]);
sumv[o][2]=max(sumv[o][2],sumv[lson][3]+sumv[rson][2]);
}
}
int ql,qr;
void update(int o,int L,int R){
if(ql<=L&&R<=qr){
setv[o]^=1;
pushdown(o,L,R);
}else{
pushdown(o,L,R);
if(ql<=M) update(lson,L,M);
if(qr>M) update(rson,M+1,R);
}
maintain(o,L,R);
}
void build(int o,int L,int R){
if(L==R){
memset(sumv[o],0,sizeof(sumv[o]));
if(str[L]=='2') sumv[o][0]=1;
else sumv[o][3]=1;
}else{
build(lson,L,M);
build(rson,M+1,R);
}
maintain(o,L,R);
}
void init(){
memset(setv,0,sizeof(setv));
}
int main(){
while(scanf("%d%d",&n,&m)==2){
init();
scanf("%s",str+1);
build(1,1,n);
char cmd[22];
while(m--){
scanf("%s",cmd);
if(cmd[0]=='c'){
printf("%d
",max(sumv[1][0],max(sumv[1][1],sumv[1][3])));
}else{
scanf("%d%d",&ql,&qr);
update(1,1,n);
}
}
}
return 0;
}
改进版本：（看起来爽多了）
打标记的位置其实已经更新完毕了，打标记知识告诉后代要更新啦。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson (o<<1)
#define rson ((o<<1)|1)
#define M L+(R-L)/2
using namespace std;
const int maxn = 101010;
int sumv[maxn << 2][4], setv[maxn << 2];
int n, m;
char str[maxn];
void pushdown(int o, int L, int R) {
if (setv[o]>0&&L<R) {
swap(sumv[lson][1], sumv[lson][2]); swap(sumv[lson][0], sumv[lson][3]);
swap(sumv[rson][1], sumv[rson][2]); swap(sumv[rson][0], sumv[rson][3]);
setv[lson] ^= 1; setv[rson] ^= 1;
setv[o] = 0;
}
}
void maintain(int o, int L, int R) {
sumv[o][0] = sumv[lson][0] + sumv[rson][0];
sumv[o][3] = sumv[lson][3] + sumv[rson][3];
sumv[o][1] = max(sumv[lson][0] + sumv[rson][3], sumv[lson][1] + sumv[rson][3]);
sumv[o][1] = max(sumv[o][1], sumv[lson][0] + sumv[rson][1]);
sumv[o][2] = max(sumv[lson][3] + sumv[rson][0], sumv[lson][2] + sumv[rson][0]);
sumv[o][2] = max(sumv[o][2], sumv[lson][3] + sumv[rson][2]);
}
int ql, qr;
void update(int o, int L, int R) {
if (ql <= L&&R <= qr) {
setv[o] ^= 1;
swap(sumv[o][1], sumv[o][2]);
swap(sumv[o][0], sumv[o][3]);
}
else {
pushdown(o, L, R);
if (ql <= M) update(lson, L, M);
if (qr>M) update(rson, M + 1, R);
maintain(o, L, R);
}
}
void build(int o, int L, int R) {
if (L == R) {
memset(sumv[o], 0, sizeof(sumv[o]));
if (str[L] == '2') sumv[o][0] = 1;
else sumv[o][3] = 1;
}
else {
build(lson, L, M);
build(rson, M + 1, R);
maintain(o, L, R);
}
}
void init() {
memset(setv, 0, sizeof(setv));
}
int main() {
while (scanf("%d%d", &n, &m) == 2) {
init();
scanf("%s", str + 1);
build(1, 1, n);
char cmd[22];
while (m--) {
scanf("%s", cmd);
if (cmd[0] == 'c') {
printf("%d
", max(sumv[1][0], max(sumv[1][1], sumv[1][3])));
}
else {
scanf("%d%d", &ql, &qr);
update(1, 1, n);
}
}
}
return 0;
}