题目名称 264. 数列操作
输入输出 shulie.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 160 MB
测试数据 15 简单对比
题目来源 2009-02-13
开放分组 全部用户
提交状态
分类标签
树状数组 线段树 分块
通过:498, 提交:1732, 通过率:28.75%
GravatarHeHe 100 0.086 s C++
Gravataraccepted 100 0.135 s C++
GravatarKulliu 100 0.141 s C++
GravatarDissolute丶Tokgo 100 0.142 s C++
GravatarOI永别 100 0.143 s C++
Gravataraccepted 100 0.150 s C++
GravatarRiolu 100 0.150 s C++
Gravataraccepted 100 0.152 s C++
GravatarRiolu 100 0.154 s C++
Gravatar啊吧啦吧啦吧 100 0.154 s C++
关于 数列操作 的讨论
这个题就是裸的树状数组吧……
Gravatar吴  豪
2009-05-02 08:37 1楼
zkw式线段树可以更快= =不过变量什么的打起来容易错。…
GravatarFrCsKOH
2012-11-05 21:40 2楼
大神这么快……
Gravatarcstdio
2013-03-21 20:53 3楼
非常困惑我的程序速度为什么老是前几名,难道评测机刚升级?我的代码也没什么特殊的啊?_?
GravatarSpaceQ
2013-05-09 19:41 4楼
是的,评测机一年前换了,配置好了很多
GravatarQhelDIV
2013-05-10 08:09 5楼
线段树练习1
Gravatarraywzy
2013-10-29 12:55 6楼
纯模拟居然A了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
GravatarFrost
2013-12-02 20:35 7楼
模拟过了。。。
Gravatarch3coooh
2014-03-18 18:54 8楼
表示看不懂楼上大神们的代码
GravatarLetter zZZz
2014-04-18 20:18 9楼
树状数组基本操作!!!
GravatarOI永别
2014-05-10 20:13 10楼
树状数组,首先初始化sum初始值,然后再memset(sum,0,sizeof(sum))。。。我是有多脑残
居然还对了一个点= =
GravatarHouJikan
2014-09-03 21:01 11楼
电脑上运行ok,为什么提交就运行错误的= =
Gravatar稠翼
2014-10-14 10:27 12楼
蒟蒻第一次练习写树状数组……
Gravatardevil
2014-10-24 20:53 13楼
先是错交成其他题,后是文件名写错,最后又发现还有0 0这种数据...
Gravatarchs
2014-12-06 22:08 14楼
裸的树状数组
GravatarBH2
2015-01-27 14:48 15楼
同样是树状数组,我的咋就这么慢。。。
Gravatar一個人的雨
2015-04-11 09:26 16楼
最后一个输入数据是“0
0”
注意
Gravatar第三十八年夏至
2015-04-17 17:17 17楼
GravatarOI88
2015-06-07 12:02 18楼
Gravatarforever
2015-06-12 08:16 19楼
Gravatar啊吧啦吧啦吧
2015-06-14 16:10 20楼
为啥我的线段树如此之慢
Gravatarforever
2015-06-14 20:42 21楼
模拟就成了啊。何必要线段树。。。
Gravatar1azyReaper
2015-07-18 14:57 22楼
没注意下标WA一次。。
Gravatarliu_runda
2016-02-17 06:03 23楼
Go X
GravatarSOBER GOOD BOY
2016-02-17 12:06 24楼
评测姬已超神……
GravatarSPA
2016-03-06 16:13 25楼
刘明
GravatarHzoi_
2016-02-17 17:38 26楼
GravatarAntiLeaf
2017-05-25 15:43 27楼
回复 @叶子の宿敌 :
你这样大小号配合留名真的好吗-_-?
Gravatarrvalue
2016-02-19 09:12 28楼
回复 @(无定义) :
怪我咯
GravatarHzoi_
2016-02-19 19:12 29楼
GravatarAntiLeaf
2017-05-25 15:40 30楼
这题有一个数据比数列操作b和数列操作c还强!笨算法超时了。。。
GravatarGaoErFu
2016-02-27 22:06 31楼
线段树
Gravatar粘粘自喜
2016-04-30 12:04 32楼
GravatarSky_miner
2017-02-15 17:43 33楼
学改段求点和改点求段学晕了,差点不会写。。。
GravatarJanis
2016-07-07 22:33 34楼
回复 @Janis :
打开链接身份后海空军飞机库萨芬黄金时段灰灰姐 环境萨哈夫经典怀旧啊哈樊江路口减少客户健康 驹留空谷,吗年历卡看病贵几乎是看见高科技 艰苦的尽快建立,播放机开或关带加号的快更快交点罚款 科技的韩国进口付好款铄金毁骨房价格书法家改了规划建;精度高黄酒克黄酒克 开机后归属感款到发货国际快递华工科技发挥更加科 就会觉得还能帮忙宣传吗 会计师鼓风机可回收空间规划思考空间狗 海空军韩国进口工会经费大客户结果可能不信呢; 进口货国际卡很发达金属构件大虎沟街道法国红酒华电国际 付款交单规划阶段,别那么操心, 发动机号感觉韩国空军
Gravatar风间净无尘
2016-07-08 10:31 35楼
GravatarAntiLeaf
2017-05-25 16:02 36楼
zkw线段树跑了0.4s 果然还是树状数组最快啊
GravatarRapiz
2016-08-11 18:53 37楼
用这个练习splay真是智障
GravatarFoolMike
2016-08-22 19:23 38楼
表示你们的模拟怎么都跑的这么快
Gravataropen the window
2016-08-26 09:02 39楼
...
Gravatar154
2016-10-13 20:44 40楼
回复 @Letter zZZz :
看不懂+1
Gravatar废纸酱/Wastaper
2016-10-18 19:23 41楼
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
class hhh{
public:
int rc,lc;
long long int sum;
}a[1000010]={0};
void init(int lc,int rc,int root)
{
a[root].rc=rc;
a[root].lc=lc;
if(rc==lc)
return;
int mid=(lc+rc)/2;
init(lc,mid,root*2);
init(mid+1,rc,root*2+1);
}
void add(int root,int d,int k)
{
a[root].sum+=d;
if(a[root].rc==a[root].lc)
return;
int mid=(a[root].rc+a[root].lc)/2;
if(k<=mid)
add(root*2,d,k);
if(k>=mid+1)
add(root*2+1,d,k);
}
long long summ(int root,int lc,int rc)
{
if(a[root].lc==lc&&a[root].rc==rc)
return a[root].sum;
int mid=(a[root].lc+a[root].rc)/2;
if(rc<=mid)
return summ(root*2,lc,rc);
if(lc>=mid+1)
return summ(root*2+1,lc,rc);
return summ(root*2,lc,mid)+summ(root*2+1,mid+1,rc);
}
int main()
{
string c;
freopen("shulie.in","r",stdin);
freopen("shulie.out","w",stdout);
int b,n,m;
cin>>n;
init(1,n,1);
for(int i=1;i<=n;i++)
{
cin>>b;
add(1,b,i);
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>c;
if(c=="ADD")
{
int x,y;
cin>>x>>y;
add(1,y,x);
}
if(c=="SUM")
{
int x,y;
cin>>x>>y;
cout<<summ(1,x,y)<<' ';
}
}
return 0;
}
Gravatar (=@__@=)
2016-10-18 19:25 42楼
暴力/////////////////
Gravatar蓝T-shirt
2016-10-18 20:52 43楼
麻辣鸡,=+ 和 if();找了20分钟
GravatarEntre Toi Et Moi
2016-12-01 18:03 44楼
强行CDQ分治了一波。
Gravatarsxysxy
2016-12-09 23:51 45楼
一颗普通的线段树
评测的时候差点以为T掉了
GravatarHeHe
2017-02-18 21:26 46楼
能达到segtree一A,开心开心
GravatarkZime
2017-04-10 11:01 47楼
裸树状数组
Gravatarzeppoe
2017-04-19 22:04 48楼
呃呃呃
GravatarFisher.
2017-06-01 13:58 49楼
@zeppoe : 75行的还没楼上49行跑得快.......
Gravatarguss
2017-07-09 21:47 50楼
学习一哈树状数组
GravatarJustWB
2017-08-30 17:31 51楼
树状数组第一题mark
Gravatar小字、小瓶子
2017-10-26 20:10 52楼
之前写的splay本机没啥问题交上去就t,开10s都t,,见鬼了
GravatarHyoi_Turkey
2017-12-17 21:04 53楼
get cdq
Gravatarhyghb
2018-01-05 08:38 54楼

264. 数列操作

★☆   输入文件:shulie.in   输出文件:shulie.out   简单对比
时间限制:1 s   内存限制:160 MB

【问题描述】

给定一个数列 $A$,请实现如下两种操作:

1. 将 $A_k$ 的值加 $d$。

2. 查询 $A_s+A_{s+1}+\dots+A_t(s≤t)$ 的值。

【输入格式】

第一行为一个整数 $n(0≤n≤100000)$,表示数列 $A$ 的大小。

第二行有 $n$ 个整数,表示序列 $A$ 各项的初始值。

第三行为一个整数 $m(0≤m≤150000)$,表示操作数。

下面 $m$ 行,每行描述一个操作:

ADD k d(表示将 $A_k$ 的值增加 $d$,$1≤k≤n$,$d$ 为整数)

SUM s t(表示查询 $A_s+\dots+A_t$ 的值)

【输出格式】

对于每一个询问,输出查询的结果。

【样例输入】

4
1 4 2 3
3
SUM 1 3
ADD 2 50
SUM 2 3

【样例输出】

7
56