COGS 264. 数列操作
2024-08-26 13:00:39
时间限制:1 s 内存限制:160 MB
【问题描述】
假设有一列数 {Ai }(1 ≤ i ≤ n) ,支持如下两种操作:
(1)将 A k 的值加 D 。( k, D 是输入的数)
(2) 输出 A s +A s+1 +…+A t 。( s, t 都是输入的数, S ≤ T )
根据操作要求进行正确操作并输出结果。
【输入格式】
输入文件第一行一个整数 n(0<=n<=100000) , 第二行为 n 个整数,表示 {A i } 的初始值。
第三行为一个整数 m(0<=m<=150000) ,表示操作数。 下接 m 行,每行描述一个操作,有如下两种情况:
ADD k d ( 表示将 A k 加 d , 1<=k<=n , d 为整数 )
SUM s t (表示输出 A s +…+A t )
【输出格式】
对于每一个 SUM 提问,输出结果
【输入输出样例】
输入:
4
1 4 2 3
3
SUM 1 3
ADD 2 50
SUM 2 3
输出:
7
56
线段树模版题
区间查询,单点修改
#include <iostream>
#include <cstdio>
#include <string> #define Max 100000 using namespace std;
int n,m,ans;
struct node
{
int l,r,dis;
int mid;
void get_mid(){mid=(l+r)>>;}
}tree[Max*+];
void up(int k)
{
tree[k].dis=tree[k<<].dis+tree[k<<|].dis;
}
void build(int l,int r,int k)
{
tree[k].l=l;
tree[k].r=r;
tree[k].get_mid();
if(l==r)
{
scanf("%d",&tree[k].dis);
return;
}
int mid=(l+r)>>;
build(l,mid,k<<);
build(mid+,r,k<<|);
up(k);
}
char cz[];
void add(int to,int v,int k)
{
if(tree[k].l==tree[k].r)
{
tree[k].dis+=v;
return;
}
int mid=tree[k].mid;
if(mid>=to) add(to,v,k<<);
else add(to,v,k<<|);
up(k);
}
int sum(int u,int v,int k)
{
if(tree[k].l==u&&tree[k].r==v)
{
return tree[k].dis;
}
if(v<=tree[k].mid) return sum(u,v,k<<);
else if(u>tree[k].mid) return sum(u,v,k<<|);
else
{
return sum(u,tree[k].mid,k<<)+sum(tree[k].mid+,v,k<<|);
}
}
int main()
{
freopen("shulie.in","r",stdin);
freopen("shulie.out","w",stdout);
scanf("%d",&n);
build(,n,);
scanf("%d",&m);
int u,v;
while(m--)
{
cin>>cz;
if(cz[]=='A')
{
scanf("%d%d",&u,&v);
add(u,v,);
}
else if(cz[]=='S')
{
scanf("%d%d",&u,&v);
printf("%d\n",sum(u,v,));
}
}
return ;
}
最新文章
- 通过重建Hosting系统理解HTTP请求在ASP.NET Core管道中的处理流程[下]:管道是如何构建起来的?
- DEV全选多选小技巧
- java中从1970-1-1到当前时间之间的毫秒数转换为oracle date
- JavaEE路径陷阱之getRealPath
- 虚拟机 本地 本机 双启动 运行 vhd local Dual Boot
- 51nod1434 区间LCM
- 【Android Api 翻译3】android api 完整翻译之Application Fundamentals (学习android必须知道的)
- Android 多种方式正确的加载图像,有效避免oom
- Scala函数字面量简化写法
- Java多线程内存模型
- eclipse/ggts/myeclipse清除SVN用户名和密码
- OC对象创建过程
- typescript的函数
- elasticSearch 2.3 delete-by-query plugin
- 实时监听input输入内容的N种方法
- 前端 ----jQuery的动画效果
- oss2罗列所有文件
- 队列----java实现
- 有趣的NaN类型
- Kettle日常使用汇总整理
热门文章
- 【216】◀▶ IDL 字符串操作说明 (黑底)
- c++ primer 5th学习时间轴[ 100% ]
- laravel C层 (控制器)
- tpc-ds99 工具使用
- chmod 详解
- swipe轮播插件零基础实用
- linux 和windows 的定时任务
- Unable to load script from assets &#39;index.android.bundle&#39;.Make sure your bundle is packaged correctly or you&#39;re running a packager server
- TYVJ1424占卜DIY
- JAVA 操作远程mysql数据库实现单表增删改查操作