\ # 4021. 행운 문자열 조회 (행운)

제목 설명
KC 는 행운 수열 을 연구 하고 행운 문자열 에 관심 을 가지 기 시작 했다 (KC 는 정상 인 이 아 닌 것 같다).행운 의 문자열 은 '4' 와 '7' 만 포함 하 는 문자열 입 니 다.현재 KC 수중 에 N (1 ≤ N ≤ 106) N (1 \ \ le N \ \ \ le 10 ^ 6) N (1 ≤ N ≤ 106) 길이 의 행운 문자열 이 있 습 니 다.천성적으로 장난 이 심 한 KC 는 이 문자열 을 가지 고 놀 기 시작 했다. 그의 게임 방법 은 매번 이 문자열 에서 구간 [l, r] [l, r] [l, r] 를 선택 하여 이 구간 의 모든 '4' 를 '7' 로 바 꾸 고 모든 '7' 을 '4' 로 바 꾸 는 것 이다.
그러나 KC 는 오 랜 시간 이 지나 서 야 자신 이 노 는 것 이 너무 지루 하 다 는 것 을 깨 달 았 습 니 다. 그래서 그 는 당신 을 찾 아와 놀아 주 었 습 니 다. 그 는 몇 구간 을 바 꾼 후에 갑자기 당신 에 게 질문 을 할 것 입 니 다. 현재 이 행운 문자열 의 최 장 불 강 자 서열 의 길 이 는 얼마 입 니까?
현재 NNN 과 MMM, 그리고 KC 에 있 는 행운 의 문자열 을 보 여 줍 니 다. MMM 은 KC 가 직접 노 는 횟수 에 당신 에 게 묻 는 횟수, 그리고 MMM 번 의 정 보 를 보 여 줍 니 다.입력 형식
첫 번 째 줄 은 N, M (M ≤ 300000) N, M (M \ \ le 300000) N, M (M ≤ 300000) 을 포함한다.
두 번 째 줄 은 NNN 길이 의 행운 문자열 입 니 다.
다음 MMM 줄 은 줄 마다 조작 정보 가 있 고 게임 에 서 는 주어진 순서에 따라 동작 이 실 행 됩 니 다.
switch l r 는 KC 가 구간 [l, r] [l, r] [l, r] 을 변환 했다 는 것 을 나타 낸다.count 는 KC 가 당신 에 게 질문 을 했 습 니 다. 당신 의 답 을 출력 해 야 합 니 다.출력 형식
줄 마다 하나의 count 에 대응 합 니 다.샘플 입력
2 3 47 count switch 1 2 count
샘플 출력 1
2 1
샘플 입력 2
3 5 747 count switch 1 1 count switch 1 3 count
샘플 출력 2
2 3 2
데이터 범위 및 알림
30% 30% 30% 의 데이터 n, m ≤ 1000 n, m \ le 1000 n, m ≤ 1000.문제 풀이: 두 글자 만 있 기 때문에 하위 서열 을 줄 이지 않 고 44444444444 또는 444477777 또는 77777777 일 수 있 습 니 다. 그러나 문 제 는 반전 을 지원 해 야 하기 때문에 44444444 - > 77777777 44477777 - > 77777744444444 7777 - > 44444444 를 기록 해 야 합 니 다. 이 를 통 해 알 수 있 듯 이 답 은 앞의 세 개의 최대 치 입 니 다.그래서 데이터 구조 가 나 오 려 고 합 니 다. 선분 트 리!

#include
#include
#include
#include
#include
#define N 1000005
using namespace std;
int n,m,a[N];
struct segement
{
	int l,r,f1,f2,f3,f4;
	int lazy;
}t[N*4];//f1 4444 f2 444777 f3 777777 f4 7777744444
void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r){
		if(a[l]==4){
			t[p].f1++;
		}else{
			t[p].f3++;
	    }
	    return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
	t[p].f2=max(max(t[p*2].f2,t[p*2].f1+t[p*2+1].f2),max(t[p*2+1].f2,t[p*2].f1+t[p*2+1].f3));
	t[p].f2=max(t[p].f2,t[p*2].f2+t[p*2+1].f3);
	t[p].f1=max(t[p*2].f1,max(t[p*2+1].f1,t[p*2].f1+t[p*2+1].f1));
	t[p].f3=max(t[p*2].f3,max(t[p*2+1].f3,t[p*2].f3+t[p*2+1].f3));
	t[p].f4=max(max(t[p*2].f4,t[p*2].f3+t[p*2+1].f4),max(t[p*2+1].f4,t[p*2].f3+t[p*2+1].f1));
	t[p].f4=max(t[p].f4,t[p*2].f4+t[p*2+1].f1);
}
void spread(int p){
	if(t[p].lazy&1){
		swap(t[p*2].f1,t[p*2].f3);
		swap(t[p*2].f2,t[p*2].f4);
        swap(t[p*2+1].f1,t[p*2+1].f3);
		swap(t[p*2+1].f2,t[p*2+1].f4);
		t[p*2].lazy+=t[p].lazy;
		t[p*2+1].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
}
//f1 4444 f2 444777 f3 777777 f4 7777744444
void change(int p,int l,int r){
	if(t[p].l>=l&&t[p].r<=r){
        swap(t[p].f1,t[p].f3);
		swap(t[p].f2,t[p].f4);
        t[p].lazy+=1;
        return ;
	}
	spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)change(p*2,l,r);
    if(r>mid)change(p*2+1,l,r);
    t[p].f2=max(max(t[p*2].f2,t[p*2].f1+t[p*2+1].f2),max(t[p*2+1].f2,t[p*2].f1+t[p*2+1].f3));
	t[p].f2=max(t[p].f2,t[p*2].f2+t[p*2+1].f3);
	t[p].f1=max(t[p*2].f1,max(t[p*2+1].f1,t[p*2].f1+t[p*2+1].f1));
	t[p].f3=max(t[p*2].f3,max(t[p*2+1].f3,t[p*2].f3+t[p*2+1].f3));
	t[p].f4=max(max(t[p*2].f4,t[p*2].f3+t[p*2+1].f4),max(t[p*2+1].f4,t[p*2].f3+t[p*2+1].f1));
	t[p].f4=max(t[p].f4,t[p*2].f4+t[p*2+1].f1);
}
int main()
{
	cin>>n>>m;
	string aa;
	cin>>aa;
	for(int i=1;i<=n;i++){
		if(aa[i-1]=='4')a[i]=4;
		else a[i]=7;
	}
	build(1,1,n);
	/*for(int i=1;i<=10;i++){
		cout<
	for(int i=1;i<=m;i++){
		cin>>aa;
		if(aa[0]=='s'){
			int x,y;cin>>x>>y;
			change(1,x,y);
		}else{
			cout<<max(t[1].f1,max(t[1].f2,t[1].f3))<<endl;
		}
	}
	return 0;
}