树状数组

简介:   敌兵布阵Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 85071    Accepted Submission(s): 35909Problem DescriptionC国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。

  

敌兵布阵

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


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询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
 

 

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 59
 

 

Author
Windbreaker
 

 

Recommend
Eddy   |   We have carefully selected several similar problems for you:   1394  1698  1754  1542  1540 
 
 
 1 /* 使用树状数组,借用树状数组的快速求和的方式可以将求和的复杂度降低到
 2  * log(N)。
 3  */
 4 
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <string.h>
 8 
 9 using namespace std;
10 
11 #define MAXN 50005
12 
13 int seq[MAXN];
14 int MaxVal;
15 int ornum[MAXN];
16 
17 int lowbit(int num)
18 {
19     return num & (num^(num-1));
20 }
21 
22 int calsum(int m)
23 {
24     int csum = 0;
25     while (m > 0)
26     {
27         csum += seq[m];
28         m -= lowbit(m);
29     }
30     return csum;
31 }
32 
33 int update(int idx, int num)
34 {
35     while (idx <= MaxVal)
36     {
37         seq[idx] += num;
38         idx += lowbit(idx);
39     }
40 }
41 
42 int main(void)
43 {
44     int T;
45     char str[10];
46     int a, b;
47     scanf("%d", &T);
48     for (int i = 1; i <= T; i++)
49     {
50         // 尤其要注意这里对数组的清空操作。
51         memset(seq, 0, sizeof(seq));
52         memset(ornum, 0, sizeof(ornum));
53         scanf("%d", &MaxVal);
54         for (int j = 1; j <= MaxVal; j++)
55         {
56             scanf("%d", &ornum[j]);
57             update(j, ornum[j]);
58         }
59         printf("Case %d:\n", i);
60         while(~scanf("%s", str))
61         {
62             if (str[0] == 'E')
63                 break;
64             scanf("%d %d",&a, &b);
65             // printf("%s\n%d\t%d\n", str, a, b);
66             if (str[0] == 'Q')
67             {
68                 // 其实这里为什么还有一个a-1,其实还有待思考
69                 printf("%d\n", calsum(b)-calsum(a-1));
70             }
71             else if (str[0] == 'A')
72             {
73                 update(a, b);
74             }
75             else if (str[0] == 'S')
76             {
77                 update(a, -b);
78             }
79         }
80     }
81     return 0;
82 }

 

相关文章
|
3天前
|
人工智能 自然语言处理 Shell
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
157353 24
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
|
5天前
|
人工智能 API 网络安全
用DeepSeek,就在阿里云!四种方式助您快速使用 DeepSeek-R1 满血版!更有内部实战指导!
DeepSeek自发布以来,凭借卓越的技术性能和开源策略迅速吸引了全球关注。DeepSeek-R1作为系列中的佼佼者,在多个基准测试中超越现有顶尖模型,展现了强大的推理能力。然而,由于其爆火及受到黑客攻击,官网使用受限,影响用户体验。为解决这一问题,阿里云提供了多种解决方案。
17021 37
|
13天前
|
机器学习/深度学习 人工智能 自然语言处理
PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型
DeepSeek 系列模型以其卓越性能在全球范围内备受瞩目,多次评测中表现优异,性能接近甚至超越国际顶尖闭源模型(如OpenAI的GPT-4、Claude-3.5-Sonnet等)。企业用户和开发者可使用 PAI 平台一键部署 DeepSeek 系列模型,实现 DeepSeek 系列模型与现有业务的高效融合。
|
5天前
|
并行计算 PyTorch 算法框架/工具
本地部署DeepSeek模型
要在本地部署DeepSeek模型,需准备Linux(推荐Ubuntu 20.04+)或兼容的Windows/macOS环境,配备NVIDIA GPU(建议RTX 3060+)。安装Python 3.8+、PyTorch/TensorFlow等依赖,并通过官方渠道下载模型文件。配置模型后,编写推理脚本进行测试,可选使用FastAPI服务化部署或Docker容器化。注意资源监控和许可协议。
1311 8
|
13天前
|
人工智能 搜索推荐 Docker
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
DeepSeek R1 + LobeChat + Ollama:快速本地部署模型,创建个性化 AI 助手
3416 117
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
|
8天前
|
人工智能 自然语言处理 API
DeepSeek全尺寸模型上线阿里云百炼!
阿里云百炼平台近日上线了DeepSeek-V3、DeepSeek-R1及其蒸馏版本等六款全尺寸AI模型,参数量达671B,提供高达100万免费tokens。这些模型在数学、代码、自然语言推理等任务上表现出色,支持灵活调用和经济高效的解决方案,助力开发者和企业加速创新与数字化转型。示例代码展示了如何通过API使用DeepSeek-R1模型进行推理,用户可轻松获取思考过程和最终答案。
|
5天前
|
人工智能 自然语言处理 程序员
如何在通义灵码里用上DeepSeek-V3 和 DeepSeek-R1 满血版671B模型?
除了 AI 程序员的重磅上线外,近期通义灵码能力再升级全新上线模型选择功能,目前已经支持 Qwen2.5、DeepSeek-V3 和 R1系列模型,用户可以在 VSCode 和 JetBrains 里搜索并下载最新通义灵码插件,在输入框里选择模型,即可轻松切换模型。
934 14
|
12天前
|
API 开发工具 Python
阿里云PAI部署DeepSeek及调用
本文介绍如何在阿里云PAI EAS上部署DeepSeek模型,涵盖7B模型的部署、SDK和API调用。7B模型只需一张A10显卡,部署时间约10分钟。文章详细展示了模型信息查看、在线调试及通过OpenAI SDK和Python Requests进行调用的步骤,并附有测试结果和参考文档链接。
1938 9
阿里云PAI部署DeepSeek及调用
|
9天前
|
人工智能 数据可视化 Linux
【保姆级教程】3步搞定DeepSeek本地部署
DeepSeek在2025年春节期间突然爆火出圈。在目前DeepSeek的网站中,极不稳定,总是服务器繁忙,这时候本地部署就可以有效规避问题。本文以最浅显易懂的方式带读者一起完成DeepSeek-r1大模型的本地部署。
|
12天前
|
缓存 自然语言处理 安全
快速调用 Deepseek API!【超详细教程】
Deepseek 强大的功能,在本教程中,将指导您如何获取 DeepSeek API 密钥,并演示如何使用该密钥调用 DeepSeek API 以进行调试。

热门文章

最新文章