注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

线段树||树状数组 hdu 1166 敌兵布阵  

2010-04-05 22:31:51|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

敌兵布阵

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2678    Accepted Submission(s): 1059


Problem Description
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.
 

Input
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
 

Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数最多不超过1000000。
 

Sample Input
1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
 

Sample Output
Case 1: 6 33
 
 
 
 
刚刚线段树入了门。。队友推荐做了一下这个题目,一个下午才写完了这个代码。。。暴汗。。。。
还可以用树状数组来做的。下面是线段树的代码。。
 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 50001;
struct Node
{
 int l, r;
 int sum;
}tree[maxn*3];
int s[maxn];
inline void make_tree(int left, int right, int now)//建树
{
 tree[now].l = left;
 tree[now].r = right;
 if(left == right)//左右子树相同结束,返回
 {
  tree[now].sum =  s[right];
  return ;
 }
 else
 {
  int mid = (right + left) >> 1;
  int l1 = now << 1, r1 = (now<<1)+1;
  make_tree(left, mid, l1);
  make_tree(mid+1, right, r1);
  tree[now].sum += tree[l1].sum + tree[r1].sum;
 }
}
inline Node getsum(int left, int right, int now)//读取所有数之和
{
 if(tree[now].l == left && tree[now].r == right)
  return tree[now];
 else if(tree[now].r > tree[now].l)
 {
  int mid = (tree[now].r + tree[now].l) >> 1;
  if(right <= mid)
   return getsum(left, right, now<<1);
  else if(left > mid)
   return getsum(left, right, (now<<1)+1);
  else
  {
   Node p1 = getsum(left, mid, (now<<1));
   Node p2 = getsum(mid+1, right, (now<<1)+1);
   p1.sum += p2.sum;
   return p1;
  }
 }
}
inline void modify(int left, int right, int now, int n)//更新状态
{
 if(tree[now].l == left && tree[now].r == right)
 {
  tree[now].sum += n;
  return ;
 }
 int mid = (tree[now].l + tree[now].r)>>1;
 if(right <= mid)
 {
  modify(left, right, now<<1, n);
  tree[now].sum += n;
 }
 else if(left > mid)
 {
  modify(left, right, (now<<1)+1, n);
  tree[now].sum += n;
 }
 else
 {
  modify(left, mid, now<<1, n);
  modify(mid+1, right, (now<<1)+1, n);
  tree[now].sum += n;
 }
}
int main()
{
 int t, n, i;
 scanf("%d", &t);
 char oder[10];
 int aa = 1;
 while(t--)
 {
  memset(tree, 0, sizeof(tree));
  printf("Case %d:\n", aa++);
  scanf("%d", &n);
  for(i = 1; i <= n; i++)
   scanf("%d", &s[i]);
  make_tree(1, n, 1);
  int j = 0, a, b;  
  while(scanf("%s", oder),strcmp(oder, "End") != 0)
  {
   scanf("%d%d", &a, &b);
   if(strcmp(oder, "Query") == 0)
   {
    Node p = getsum(a, b, 1);
    printf("%d\n", p.sum);
   }
   if(strcmp(oder, "Add") == 0)
    modify(a, a, 1, b);
   if(strcmp(oder, "Sub") == 0)
    modify(a, a, 1, -b);
  }
 }
return 0;
}
 
下面是树状数组的代码:
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int c[50001], n;
inline int lowbit(int x)
{
 return x & (-x);
}
inline int getsum(int x)
{
 int sum = 0;
 while(x > 0)
 {
  sum += c[x];
  x -= lowbit(x);
 }
 return sum;
}
inline void update(int x, int now)
{
 while(x <= n)
 {
  c[x] += now;
  x += lowbit(x);
 }
}
int main()
{
 int test, i, a, b, ii;
 char s[10];
 scanf("%d", &test);
 for(ii = 1; ii <= test; ii++)
 {
  for(i = 1; i <= n; i++) c[i] = 0;  
  scanf("%d", &n);
  for(i = 1; i <= n; i++)
  {
   scanf("%d", &a);
   update(i, a);
  }
  printf("Case %d:\n", ii);
  while(scanf("%s", s) && strcmp(s, "End") != 0)
  {
   if(strcmp(s, "Query") == 0)
   {
    scanf("%d%d", &a, &b);
    printf("%d\n", getsum(b) - getsum(a-1));
   }
   else if(strcmp(s, "Add") == 0)
   {
    scanf("%d%d", &a, &b);
    update(a, b);
   }
   else if(strcmp(s, "Sub") == 0)
   {
    scanf("%d%d", &a, &b);
    update(a, -b);
   }
  }
 }
return 0;
}
  评论这张
 
阅读(487)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017