10:Challenge 3(树状数组直接修改)
2018-06-17 22:11:44来源:未知 阅读 ()
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
给一个长为N的数列,有M次操作,每次操作是以下两种之一:
(1)修改数列中的一个数
(2)求数列中某连续一段的和
- 输入
- 第一行两个正整数N和M。
第二行N个整数表示这个数列。
接下来M行,每行开头是一个字符,若该字符为'M',则表示一个修改操作,接下来两个整数x和y,表示把x位置的值修改为y;若该字符为'Q',则表示一个询问操作,接下来两个整数x和y,表示求[x,y]这段区间的和。 - 输出
- 对每一个询问操作单独输出一行,表示答案。
- 样例输入
-
5 3 1 2 3 4 5 Q 1 5 M 2 7 Q 1 5
- 样例输出
-
15 20
- 提示
- 1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数及答案可用带符号32位整型存储。
- 考虑树状数组肯定是没有什么疑问的,
- 但是这里不是加减,而是直接修改,
- 然而直接修改会爆零,原因自己yy一下就知道。
- 所以说,我们每次改的时候,去加上要加的数和当前的数的差,然后再把当前的数改成将要改的数
-
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=100001; 6 int a[MAXN]; 7 int tree[MAXN]; 8 int n,m; 9 void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 } 17 int lb(int p) 18 { 19 return (p)&(-p); 20 } 21 void add(int pos,int v) 22 { 23 int p=pos; 24 while(p<=n) 25 { 26 tree[p]+=v; 27 p+=lb(p); 28 } 29 } 30 int sum(int pos) 31 { 32 int ans=0; 33 int p=pos; 34 while(p) 35 { 36 ans+=tree[p]; 37 p-=lb(p); 38 } 39 return ans; 40 } 41 int main() 42 { 43 read(n);read(m); 44 for(int i=1;i<=n;i++) 45 { 46 int p; 47 read(p); 48 a[i]=p; 49 add(i,p); 50 } 51 for(int i=1;i<=m;i++) 52 { 53 char c;int x,y; 54 cin>>c;read(x);read(y); 55 if(c=='Q') 56 printf("%d\n",sum(y)-sum(x-1)); 57 else 58 { 59 add(x,y-a[x]); 60 a[x]=y; 61 } 62 63 } 64 return 0; 65 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- 寻找两个有序数组的中位数 2020-04-09
- STL之vector 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash