CF 145E
线段树。
统计5个东西。1 统计 这一段4 的个数。2 统计这一段7的个数。3 统计这一段最长的递增序列个数。4统计这一段最长的递减序列的个数。5标记这段是否被翻转。
那么答案就是求3了。每次翻转 1-2 3-4互换即可。
[cpp]
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef long long LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 1000000+100;
char s[maxn],op[100],temp[100];
struct node{
int m4,m7,c4,c7;
int flip;
}T[maxn<<2];
void push_up(int id ){
T[id].c4=T[id<<1].c4+T[id<<1|1].c4;
T[id].c7=T[id<<1].c7+T[id<<1|1].c7;
T[id].m4=max(T[id<<1].m4+T[id<<1|1].c7,T[id<<1].c4+T[id<<1|1].m4);
T[id].m7=max(T[id<<1].m7+T[id<<1|1].c4,T[id<<1].c7+T[id<<1|1].m7);
}
void build(int id,int l,int r){
if(l==r){
T[id].flip=0;
if(s[l-1]=='4')
T[id].c4=1;
else T[id].c7=1;
T[id].m4=T[id].m7=1; return ;
}
int m=(l+r)>>1;
build(id<<1,l,m); build(id<<1|1,m+1,r);
push_up(id);
}
void flip(int id){
T[id].flip^=1;
swap(T[id].m4,T[id].m7);
swap(T[id].c4,T[id].c7);
}
void update(int id,int l,int r,int L,int R){
if(l==L&&r==R){
flip(id);
return ;
}
if(T[id].flip){
flip(id<<1); flip(id<<1|1); T[id].flip=0;
}
int m=(L+R)>>1;
if(m>=r){
update(id<<1,l,r,L,m);
}
else if(l>m){
update(id<<1|1,l,r,m+1,R);
}
else {
update(id<<1,l,m,L,m);
update(id<<1|1,m+1,r,m+1,R);
}
push_up(id);
}
int main(){
int n,m,l,r;
scanf("%d%d",&n,&m); scanf("%s",s);
build(1,1,n);
while(m--){
scanf("%s",op);
if(op[0]=='s'){
scanf("%d %d",&l,&r);
update(1,l,r,1,n);
}
else{
printf("%d\n",T[1].m4);
}
}
return 0;
}
补充：软件开发 , C++ ,
