hdu_4046 Panda线段树_点修改_区间求和

Panda

Time Limit: 10000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2396    Accepted Submission(s): 810

Problem Description

When I wrote down this letter, you may have been on the airplane to U.S.
We have known for 15 years, which has exceeded one-fifth of my whole life. I still remember the first time we went to the movies, the first time we went for a walk together. I still remember the smiling face you wore when you were dressing in front of the mirror. I love your smile and your shining eyes. When you are with me, every second is wonderful.
The more expectation I had, the more disappointment I got. You said you would like to go to U.S.I know what you really meant. I respect your decision. Gravitation is not responsible for people falling in love. I will always be your best friend. I know the way is difficult. Every minute thinking of giving up, thinking of the reason why you have held on for so long, just keep going on. Whenever you’re having a bad day, remember this: I LOVE YOU.
I will keep waiting, until you come back. Look into my eyes and you will see what you mean to me.
There are two most fortunate stories in my life: one is finally the time I love you exhausted. the other is that long time ago on a particular day I met you.
Saerdna.

It comes back to several years ago. I still remember your immature face.
The yellowed picture under the table might evoke the countless memory. The boy will keep the last appointment with the girl, miss the heavy rain in those years, miss the love in those years. Having tried to conquer the world, only to find that in the end, you are the world. I want to tell you I didn’t forget. Starry night, I will hold you tightly.

Saerdna loves Panda so much, and also you know that Panda has two colors, black and white.
Saerdna wants to share his love with Panda, so he writes a love letter by just black and white.
The love letter is too long and Panda has not that much time to see the whole letter.
But it's easy to read the letter, because Saerdna hides his love in the letter by using the three continuous key words that are white, black and white.
But Panda doesn't know how many Saerdna's love there are in the letter.
Can you help Panda?

 

 

Input

An integer T means the number of test cases T<=100
For each test case:
First line is two integers n, m
n means the length of the letter, m means the query of the Panda. n<=50000,m<=10000
The next line has n characters 'b' or 'w', 'b' means black, 'w' means white.
The next m lines
Each line has two type
Type 0: answer how many love between L and R. (0<=L<=R<n)
Type 1: change the kth character to ch(0<=k<n and ch is ‘b’ or ‘w’)

 

 

Output

For each test case, output the case number first.
The answer of the question.

 

 

Sample Input

   
   2

5 2
bwbwb
0 0 4
0 1 3
5 5
wbwbw
0 0 4
0 0 2
0 2 4
1 2 b
0 0 4
  
  

 

 

Sample Output

   
   Case 1: 
1 
1 
Case 2: 
2 
1 
1 
0
  
  

 

题意不在叙述，本题中可以将w和符合要求的转为1，否则为0 ，最后利用线段树求和，具体转化方式如下：

例：wbwbwbwwb 存入字符数组s[i] i = 9

同时建立整形数组a[j]   j= 9；每个i和j相对应

每三个字符若满足条件，则将a[j]标记为1，否则为0，初始a全为0

则 wbwbwbwwb ---->>0 0 1 0 1 0 1 0 0

最后利用线段树求和即可

在改变某个结点的值时，要进行三次修改，代表三种情况，修改完后要更新线段树，具体代码如下：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define mem0(a) memset(a,0,sizeof(a))
const int num = 50000+10;
char s[num];
int a[num],sum[num<<2];
void Getsum(int cur){
    sum[cur] = sum[cur<<1]+sum[cur<<1|1];
}
void build(int l,int r, int cur){
    if( l == r ){
        sum[cur] = a[l];
        return ;
    }
    int mid = (l + r )>>1;
    build(l,mid,cur<<1);
    build(mid+1,r,cur<<1|1);
    Getsum(cur);

}
void update(int k,int  v,int l,int r,int cur){
    if(l == r ){
        sum[cur] = v;
        return ;
    }
    int mid = ( l + r )>>1;
    if(k <=mid ){
        update(k,v,l,mid,cur<<1);
    }
    else {
        update(k,v,mid+1,r,cur<<1|1);
    }
    Getsum(cur);
}
int query(int ql,int qr,int l,int r ,int cur){
    if(ql <= l && qr >= r){
        return sum[cur];
    }
    int mid = ( l + r )>>1;
    int ans = 0 ;
    if(ql <= mid) ans += query(ql,qr,l,mid,cur<<1);
    if(qr > mid ) ans += query(ql,qr,mid+1,r,cur<<1|1);
    return ans ;
}
int main()
{
    int T,t =1 ;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        scanf("%s",s);
        mem0(a);
        for(int i = 2 ; i < n ; i++){
            if(s[i]!='w') a[i]=0;
            else if(s[i]=='w'&&s[i-1]=='b'&&s[i-2]=='w')
                a[i]=1;
        }
        build(0,n,1);
        printf("Case %d:\n",t++);
        while(m--){
            int aa,b,c;
            char d;
            scanf("%d",&aa);
            if(aa == 0){
                scanf("%d%d",&b,&c);
                b+=2; //从b开始后第三个字母开始检测
                if(b > c)  //如果b,c长度小于3，直接输出0
                    printf("0\n");
                else
                    printf("%d\n",query(b,c,0,n,1));
            }
            else if(aa == 1){
                scanf("%d %c",&b,&d);
                if(s[b]==d)
                    continue;//当改变值与原来一样，则continue，进行下次询问
                s[b]=d;    //否则值一定改变，下列假设都是在改变值的情况下建立的
               //以b处为末尾的三个字符
                if(b>=2&&s[b-2]=='w'&&s[b-1]=='b'&&s[b]=='w'){
                   // 改变之后符合要求
                    if(a[b]==0)//若改之前不符合要求，则更新
                        update(b,1,0,n,1);//更新线段树sum
                    a[b]=1;//原保存数组a也要更新
                }
                else if(b>=2&&a[b]==1){//如果原来符合要求，改过必不符合要求
                    update(b,0,0,n,1);//更新
                    a[b]=0;
                }

                //以b处为中间的三个字符
                if(b>=1&&b<n-1&&s[b-1]=='w'&&s[b]=='b'&&s[b+1]=='w'){//同上
                    if(a[b+1]==0)
                        update(b+1,1,0,n,1);
                    a[b+1]=1;
                }
                else if(b < n-1 && b >= 1&&a[b+1]==1){
                    a[b+1]=0;
                    update(b+1,0,0,n,1);
                }
                //以b处为起始的三个字符
                if(b+2<n&&s[b]=='w'&&s[b+1]=='b'&&s[b+2]=='w'){
                    if(a[b+2]==0)
                        update(b+2,1,0,n,1);
                    a[b+2]=1;
                }
                else if(b < n - 2 && a[b+2]==1){
                    a[b+2]=0;
                    update(b+2,0,0,n,1);
                }
            }
        }
    }
    return 0;
}