HDU 4046 Panda (트 리 배열)

제목: 길이 가 5W 인 문자열 을 지정 합 니 다. 알파벳 w 나 b 만 포함 되 어 있 습 니 다. 현재 1W 작업 이 있 습 니 다. 0, l, r 는 매번 l, r 구간 에 몇 개의 연속 적 인 'wbw' 가 있 는 지 물 어 볼 때마다 표시 합 니 다. 1, i, c 는 i 번 째 위치 에 있 는 문 자 를 문자 c 로 수정 하 는 것 을 표시 합 니 다.
분석: 트 리 배열 의 단일 업데이트: 구간 내 에 몇 개의 연속 적 인 'wbw' 가 있 는 지, 모든 'wbw' 를 찾 을 수 있 습 니 다. 세 개의 배열 pre, mid, suc 로 각각 표시 합 니 다. i 번 째 위치의 문 자 는 접두사 w, 중간 b 또는 접두사 w, 문자 b 가 있 는 위치 값 업데이트 + 1 을 찾 을 수 있 습 니 다. 매번 l, r 를 조회 할 때마다 가장 가 까 운 접두사 w, 가장 가 까 운 r 의 접두사 w 를 찾 을 수 있 습 니 다.조회 하면 됩 니 다.
업데이트 시 여러 가지 상황 에 주의 하 십시오. 세 개의 배열 pre, mid, suc 이 태그 의 표 시 는 제거 해 야 합 니 다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include<functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//  INT_MAX   
#define MAX 50555
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x<<1
#define R(x) x<<1|1
# define eps 1e-5
using namespace std;

int pre[MAX],mid[MAX],suc[MAX],c[MAX];
char str[MAX];
int n,m;

void init() {
    memset(pre,0,sizeof(pre));
    memset(suc,0,sizeof(suc));
    memset(mid,0,sizeof(mid));
    memset(c,0,sizeof(c));
}

int lowbit(int x) {
    return x & (-x);
}

void update(int x,int va) {
    while(x <= n) {
        c[x] += va;
        x += lowbit(x);
    }
}

int query(int x) {
    int sum = 0;
    while(x > 0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    int T;
    int a,b,c;
    char op;
    cin >> T;
    int ca = 1;
    while(T--) {
        init();
        scanf("%d%d",&n,&m);
        scanf("%s",str);
        for(int i=0; i<n-2; i++) {
            if(str[i] == 'w' && str[i+1] == 'b' && str[i+2] == 'w') {
                pre[i] = 1;
                mid[i+1] = 1;
                suc[i+2] = 1;
                update(i+2,1);
            }
        }
        printf("Case %d:
",ca++);
        for(int i=0; i<m; i++) {
            scanf("%d",&a);
            if(a == 0) {
                scanf("%d%d",&b,&c);
                while(pre[b] == 0) {
                    b ++;
                }
                while(suc[c] == 0) {
                    c --;
                }
                if(c < b) printf("0
");
                else {
                    printf("%d
",query(c+1) - query(b));
                }
            } else {
                scanf("%d %c",&b,&op);
                if(op == 'b') {
                    if(str[b] == 'w') {
                        str[b] = 'b';
                        if(pre[b] == 1) {
                            pre[b] = 0;
                            mid[b+1] = 0;
                            suc[b+2] = 0;
                            update(b+2,-1);
                        }
                        if(suc[b] == 1) {
                            pre[b-2] = 0;
                            mid[b-1] = 0;
                            suc[b] = 0;
                            update(b,-1);
                        }
                        if(str[b-1] == 'w' && str[b+1] == 'w') {
                            pre[b-1] = 1;
                            mid[b] = 1;
                            suc[b+1] = 1;
                            update(b+1,1);
                        }
                    }
                } else {
                    if(str[b] == 'b') {
                        str[b] = 'w';
                        if(mid[b] == 1) {
                            pre[b-1] = 0; mid[b] = 0; suc[b+1] = 0;
                            update(b+1,-1);
                        }
                        if(str[b+1] == 'b' && str[b+2] == 'w') {
                            pre[b] = 1;
                            mid[b+1] = 1;
                            suc[b+2] = 1;
                            update(b+2,1);
                        }
                        if(str[b-1] == 'b' && str[b-2] == 'w') {
                            pre[b-2] = 1;
                            mid[b-1] = 1;
                            suc[b] = 1;
                            update(b,1);
                        }
                    }
                }
            }
        }
    }
    return 0;
}