HdU 4046 Panda 段树

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4046

意甲冠军：到了bw组成的长度为n的字符串（n<=50000）。有m次操作（m<=10000），每次操作是询问一段范围内wbw的个数。或者改变一个字符成为w或b。

思路：建一棵线段树，每一个结点记录的是从L到R以每一个i为最左边的字母的总共的wbw的个数，单点更新的时候要更新三个点。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <map>

#include <cstdlib>

#include <queue>

#include <stack>

#include <vector>

#include <ctype.h>

#include <algorithm>

#include <string>

#include <set>

#include <ctime>

#define PI acos(-1.0)

#define INF 0x7fffffff

#define eps 1e-8

#define maxn 50005

typedef long long LL;

typedef unsigned long long ULL;

using namespace std;

int n,m,l,r;

int num[maxn*4];

char ss[maxn*4];

struct line

{

    int left,right;

    int n;

    char value;

} a [maxn*4];

void build_tree(int l,int r,int step)

{

    a[step].left=l;

    a[step].right=r;

    a[step].n=0;

    if(l==r)

    {

        a[step].n=((l+2<=n)&&(ss[l]=='w'&&ss[l+1]=='b'&&ss[l+2]=='w'));

        num[l]=step;

        return;

    }

    int mid=(l+r)>>1;

    build_tree(l,mid,step<<1);

    build_tree(mid+1,r,step<<1|1);

    a[step].n=a[step<<1].n+a[step<<1|1].n;

}

int ans;

void change(int s,int step,char k)

{

    if(s==a[step].left&&s==a[step].right)

    {

        a[step].value=k;

        ss[s]=k;

        a[step].n=((l+2<=n)&&ss[s]=='w'&&ss[s+1]=='b'&&ss[s+2]=='w');

        return;

    }

    if(a[step].left==a[step].right) return;

    int mid=(a[step].left+a[step].right)>>1;

    if(mid>=s) change(s,step<<1,k);

    else change(s,step<<1|1,k);

    a[step].n=a[step<<1].n+a[step<<1|1].n;

}

void change2(int s,int step)

{

    if(s==a[step].left&&s==a[step].right)

    {

        a[step].n=(ss[s]=='w'&&ss[s+1]=='b'&&ss[s+2]=='w');

        return;

    }

    if(a[step].left==a[step].right) return;

    int mid=(a[step].left+a[step].right)>>1;

    if(mid>=s) change2(s,step<<1);

    else change2(s,step<<1|1);

    a[step].n=a[step<<1].n+a[step<<1|1].n;

}

int query(int s,int t,int step)

{

    if(a[step].left>=s&&a[step].right<=t)

    {

        ans+=a[step].n;

        return 0;

    }

    else

    {

        int mid=(a[step].left+a[step].right)/2;

        if(mid>=t) query(s,t,step<<1);

        else if(mid<s) query(s,t,step<<1|1);

        else

        {

            query(s,t,step<<1);

            query(s,t,step<<1|1);

        }

    }

}

int main()

{

    int T,q,L,R,p;

    char k[2];

    scanf("%d",&T);

    for(int ii=1;ii<=T;ii++)

    {

        scanf("%d%d",&n,&m);

        scanf("%s",ss+1);

        printf("Case %d:\n",ii);

        build_tree(1,n,1);

        for(int i=0;i<m;i++)

        {

            scanf("%d",&q);

            if(q==0)

            {

                ans=0;

                scanf("%d%d",&L,&R);

                if(R-1<L+1)

                {

                    printf("0\n");

                    continue;

                }

                query(L+1,R-1,1);

                printf("%d\n",ans);

            }

            else

            {

                scanf("%d%s",&p,&k);

                change(p+1,1,k[0]);

                if(p>=1)

                change2(p,1);

                if(p>=2)

                change2(p-1,1);

            }

        }

    }

    return 0;

}