【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 104228
  • 排名 - 233

最新评论

阅读排行榜

评论排行榜

NK中学组织同学们去五云山寨参加社会实践活动,按惯例要乘坐火车去。由于NK中学的学生很多,在火车开之前必须清点好人数

初始时,火车上没有学生;当同学们开始上火车时,年级主任从第一节车厢出发走到最后一节车厢,每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时,他想知道第1到m这m节车厢上一共有多少学生,但是他没有调头往回走的习惯.也就是说每次当他提问时,m总会比前一次大。

input:
初始时,火车上没有学生;当同学们开始上火车时,年级主任从第一节车厢出发走到最后一节车厢,每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时,他想知道第1到m这m节车厢上一共有多少学生,但是他没有调头往回走的习惯.也就是说每次当他提问时,m总会比前一次大

output:
有多少个A就输出多少个数,回答年级主任提出的问题。输出不要换行!

input:
10 7
A 1
B 1 1
B 3 1
B 4 1
A 2
A 3
A 10

output:
0
1
2
3

分析:
      来一个人就把所有的上司(我影响的火车)都加上这个数,下车的就是单纯的减去即可,有A 的就统计

【参考程序】://树状数组

#include<string.h>
#include
<stdio.h>
#include
<stdlib.h>
long c[500001];
long n,k;
long lowbit(long x)
{
    
return x^(x&(x-1));
}
void modify(long x,long d)
{
    
while (x<=n)
    {
        c[x]
+=d;
        x
+=lowbit(x);
    }
}
long getsum(long x)
{
    
long s=0;
    
while (x)
    {
        s
+=c[x];
        x
-=lowbit(x);
    }
    
return s;
}
int main()
{
    scanf(
"%d%d",&n,&k);
    getchar();
    memset(c,
0,sizeof(c));
    
long x,y;
    
char c;
    
for (int i=1;i<=k;i++)
    {
        scanf(
"%c",&c);

        
if (c=='A')
        {
            scanf(
"%d",&x);
            getchar();
            printf(
"%d",getsum(x));
        }
        
else if (c=='B')
        {
            scanf(
"%d%d",&x,&y);
            getchar();
            modify(x,y);
        }
        
else
        {
            scanf(
"%d%d",&x,&y);
            getchar();
            modify(x,
-y);
        }
    }
    system(
"pause");
    
return 0;
}
posted on 2009-04-07 14:03 开拓者 阅读(587) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理