大致题意:
给出一个n长度的数组,在线的实现改变某个值,查询一个区间和的功能。
大致思路:
基础线段树。。G++死活过不去,郁闷,用c++水过去了
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Max = 50005;
struct data{
int l, r, num;
}node[3*Max]; // 线段树节点的数据结构。
int num[Max];
void BuildTree(int left, int right, int u){ // 建树。
node[u].l = left;
node[u].r = right;
if(left == right)
node[u].num = num[left];
else{
BuildTree(left, (left+right)/2, 2*u);
BuildTree((left+right)/2+1, right, 2*u+1);
node[u].num = node[2*u].num + node[2*u+1].num;
}
}
int updata(int camp, int w, int u){ // 修改。
node[u].num += w;
if(node[u].l == node[u].r) return 0;
else if(camp <= node[2*u].r) updata(camp, w, 2*u);
else updata(camp, w, 2*u+1);
return 0;
}
int query(int left, int right, int u){ // 查询。
if(node[u].l == left && node[u].r == right)
return node[u].num;
if(right <= node[2*u].r)
return query(left, right, 2*u);
if(left >= node[2*u+1].l)
return query(left, right, 2*u+1);
int a = query(left, (node[u].l+node[u].r)/2, 2*u);
int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1);
return a + b;
}
int main()
{
char str[10];
int cas,i,j,a,b,c,n,t=0;
cin>>cas;
while(cas--)
{
cin>>n;
for(i=1;i<=n;i++)
{
//cin>>num[i];
scanf("%d",&num[i]);
}
printf("Case %d:\n",++t);
BuildTree(1,n,1);
while(cin>>str&&str[0]!='E')
{
if(str[0]=='Q')
{
cin>>a>>b;
//cout<<query(a,b,1)<<endl;
a=query(a,b,1);
printf("%d\n",a);
}
if(str[0]=='A')
{
//cin>>a>>b;
scanf("%d%d",&a,&b);
updata(a,b,1);
}
if(str[0]=='S')
{
scanf("%d%d",&a,&b);
updata(a,-b,1);
}
}
}
return 0;
}
分享到:
相关推荐
例如,在HDOJ 1166题中,使用线段树来解决敌兵布阵问题。在这个问题中,需要快速地进行点修改和区间查询操作,而线段树正好满足这个需求。 线段树的优缺点 线段树的优点是:1. 高效的查询速度:线段树能够快速地...
例如,HDOJ 1166题目的解决方案就展示了如何用线段树处理区间求和的问题。 2. **节点结构**: 线段树的每个节点通常包含三个属性:左边界(l),右边界(r)和中间值(mid,表示当前节点覆盖的区间的中间位置)。...
【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
【ACM HDOJ 课件】是一套涵盖了多种计算机科学竞赛中常见算法与理论的教育资源,主要针对ACM(国际大学生程序设计竞赛)和HDOJ(华中地区大学生在线编程题库)的训练。这些课件深入浅出地讲解了在解决复杂问题时所需...
hdoj1004,解题代码,答案代码,欢迎下载
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...