HDU 4046 Panda
HDU
2023-09-11 14:15:28 时间
Panda
Time Limit: 4000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 404664-bit integer IO format: %I64d Java class name: Main
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?
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’)
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.
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
Source
解题:。。。线段树或者树状数组。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 50010; 4 struct node{ 5 int lt,rt,sum; 6 }tree[maxn<<2]; 7 int num[maxn]; 8 void build(int L,int R,int v){ 9 tree[v].lt = L; 10 tree[v].rt = R; 11 if(L == R){ 12 tree[v].sum = num[L]; 13 return; 14 } 15 int mid = (L + R)>>1; 16 build(L,mid,v<<1); 17 build(mid+1,R,v<<1|1); 18 tree[v].sum = tree[v<<1].sum + tree[v<<1|1].sum; 19 } 20 void update(int id,int val,int v){ 21 if(tree[v].lt == tree[v].rt){ 22 tree[v].sum = val; 23 return; 24 } 25 int mid = (tree[v].lt + tree[v].rt)>>1; 26 if(id <= mid) update(id,val,v<<1); 27 if(id > mid) update(id,val,v<<1|1); 28 tree[v].sum = tree[v<<1].sum + tree[v<<1|1].sum; 29 } 30 int query(int lt,int rt,int v){ 31 if(lt <= tree[v].lt && rt >= tree[v].rt) return tree[v].sum; 32 int mid = (tree[v].lt + tree[v].rt)>>1,ans = 0; 33 if(lt <= mid) ans += query(lt,rt,v<<1); 34 if(rt > mid) ans += query(lt,rt,v<<1|1); 35 return ans; 36 } 37 char str[maxn],tmp[20]; 38 int main(){ 39 int T,n,m,op,a,b,cs = 1; 40 scanf("%d",&T); 41 while(T--){ 42 scanf("%d %d",&n,&m); 43 scanf("%s",str); 44 printf("Case %d:\n",cs++); 45 memset(num,0,sizeof num); 46 for(int i = 2; i < n; ++i) 47 if(str[i-2] == 'w' && str[i-1] == 'b' && str[i] == 'w') num[i] = 1; 48 build(0,n-1,1); 49 while(m--){ 50 scanf("%d %d",&op,&a); 51 if(op){ 52 scanf("%s",tmp); 53 if(str[a] == tmp[0]) continue; 54 if(a >= 2 && str[a-2] == 'w' && str[a-1] =='b') 55 update(a,str[a] == 'w'?0:1,1); 56 if(a >= 1 && a + 1 < n && str[a-1] == 'w' && str[a+1] == 'w') 57 update(a+1,str[a] == 'b'?0:1,1); 58 if(a + 2 < n && str[a+1] == 'b' && str[a+2] == 'w') 59 update(a+2,str[a] == 'w'?0:1,1); 60 str[a] = tmp[0]; 61 }else{ 62 scanf("%d",&b); 63 printf("%d\n",b-a<2?0:query(a+2,b,1)); 64 } 65 } 66 } 67 return 0; 68 }
相关文章
- 致初学者(三): HDU 2033~ 2043题解
- HDU 2296 Ring
- 2015 Multi-University Training Contest 10 hdu 5407 CRB and Candies
- HDU 1180 诡异的楼梯
- HDU 5468 Puzzled Elena (dfs + 莫比乌斯反演)
- HDU 6097 Mindis (计算几何)
- HDU 3001 Travelling (状压DP + BFS)
- HDU 5778 abs (素数,暴力)
- HDU 3367 Pseudoforest (最大生成树)
- HDU 2680 最短路 Dijkstra + 链式向前星 + 优先队列(模板)
- 【HDU 5363】Key Set(和为偶数的子集个数)
- HDU 4287 Intelligent IME(map运用)
- HDU 1010 Tempter of the Bone heuristic 修剪
- HDU - 2294 Pendant (DP滚动数组降维+矩阵高速功率)
- hdu 1233 (prim,最小生成树) 还是畅通工程