[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
思路是维护每个字母开头,长度为3的串是不是wbw……
这样相当于将长度为N的字符串变成长度为N-2的序列,然后一系列修改就是将序列中1变0,0变1,查询就是求一段的和
BIT,大家都懂的……
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int n,m;
 5 char str[50010];
 6 int arr[50010];
 7 
 8 inline int lowbit(int x) {return x & -x;}
 9 
10 void update(int x,int delta) {
11     for (int i = x; i <= n; i += lowbit(i)) {
12         arr[i] += delta;
13     }
14 }
15 
16 int sum(int x) {
17     int ret = 0;
18     while (x) {ret += arr[x]; x -= lowbit(x);}
19     return ret;
20 }
21 
22 int sum(int l,int r) {
23     if (l > r) return 0;
24     if (l == 0return sum(r);
25     return sum(r) - sum(l - 1);
26 }
27 
28 int main() {
29     int nn; scanf("%d",&nn);
30     for (int ii = 1; ii <= nn; ii++) {
31         scanf("%d%d",&n,&m);                
32         memset(str,0,sizeof(str));
33         memset(arr,0,sizeof(arr));
34         scanf("%s",str + 1);
35         for (int i = 1; i + 2 <= n; i++) {
36             if (str[i] == 'w' && str[i + 1== 'b' && str[i + 2== 'w') {
37                 update(i,1);
38             }
39         }
40         printf("Case %d:\n",ii);
41         while (m--) {
42             int ctrl; scanf("%d",&ctrl);
43             if (ctrl == 0) {
44                 int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum(l + 1,r - 1));
45             } else {
46                 int pos; char buf[10]; scanf("%d",&pos); scanf("%s",buf); pos ++;
47                 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
48                     if (str[i] == 'w' && str[i + 1== 'b' && str[i + 2== 'w') {
49                         update(i,-1);
50                     }
51                 }
52                 str[pos] = buf[0];
53                 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
54                     if (str[i] == 'w' && str[i + 1== 'b' && str[i + 2== 'w') {
55                         update(i,1);
56                     }
57                 }
58             }
59         }
60     }
61     return 0;
62 }
posted on 2011-09-18 20:44 sweetsc 阅读(588) 评论(3)  编辑  收藏

Feedback

# re: 2011ACM北京网络预选赛G Panda (BUPT 217) 2011-09-19 10:44 forget~
这个是属于线段树里的吗?  回复  更多评论
  

# re: 2011ACM北京网络预选赛G Panda (BUPT 217) 2011-09-19 12:51 [NKU]sweet
@forget~
树状数组……  回复  更多评论
  

# re: 2011ACM北京网络预选赛G Panda (BUPT 217) 2011-09-21 15:17 游客
query的时候。
为什么要 if( r - l < 2 ) cout << "0" << endl;
else cout << sum(r-1) - sum(l) << endl;
我知道r-l 如果小于2的话肯定是0 ,但是else里面sum()可以正确求出这样的答案啊。。。。
我不加if 就WA,加了才对。
能不能举出例子为什么必须加if啊  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: