题意:
给出一串n个数,每次操作分为两种,分别是对[i,j]区间上的数字加上一个值,查询[i,j]区间上所有数字的和
思路:
对于这种一次要对一个区间进行更新的问题,用单点更新肯定会超时,这里设定一个add值,意思是如果更新的区间和当前区间左右完全相等的时候,用add值记录本应向下加上去的节点,并返回
#include<iostream> #include<cstring> #include<cstdio> const int nMax = 100010; typedef long long ll; using namespace std; struct{ int l,r; ll sum,add; }node[3 * nMax]; int num[nMax]; ll ans; void build(int l , int r , int u){ node[u].l = l; node[u].r = r; node[u].add = 0; if(l == r){ node [u].sum = num[r]; return; } int m = (l + r) >> 1; build(l , m , u * 2); build(m + 1 ,r , u * 2 + 1); node[u].sum = node[u*2].sum + node[u * 2 + 1].sum; } void update(int left , int right ,int p , int u){ if(node[u].l == left && node[u].r == right){ node[u].add += p; return; } node[u].sum += (right - left + 1 )* p; int m = (node[u].r + node[u].l)>>1; if(left <= m){ update(left , min(right ,node[u*2].r), p, u*2); } if(right >= m+1){ update(max(left ,m+1) , right , p ,u*2 + 1); } } void query(int left ,int right ,int u){ int l = node[u].l; int r = node[u].r; ans += (right-left+1)* node[u].add; if(l == left && r == right){ ans += node[u].sum; return ; } int m = (node[u].r + node[u].l)>>1; if(right <= m){ query(left , right , u*2); return; } if(left >= m+1){ query(left , right , u*2+1); return; } query(left , m , u*2); query(m+1 , right , u*2 + 1); } int main(){ int n, m ,i ,a , b ,c;char str[5]; while(scanf("%d%d",&n,&m)!=EOF){ for(i=1; i<= n; i++){ scanf("%d",&num[i]); } build(1, n, 1); while(m--){ scanf("%s",str); if(str[0] == 'C'){ scanf("%d%d%d",&a,&b,&c); update(a ,b ,c , 1); }else{ ans = 0; scanf("%d%d",&a,&b); query(a , b , 1); printf("%I64d\n",ans); } } } return 0; }
相关推荐
作者:Persegrand.Spiniper(树成) 编写时间:2008年8月10日 版本:1.1 该控件以发现且未解决缺陷: 1、点击下拉单的滚动条然后失去焦点不会使下拉单消失。 2、显示长度过长会出现换行现象,没有进行字符串截取...
总结了一套科学的方法。如果自己一个人,或者团队人数也有限,只能主做商业领域,剩下财经、体育、母婴、旅游、情感、健康、职场......等等一系列行业,都没法做,我既没时间,也不可能懂这么多行业的专业知识。...
选煤厂浮选尾煤资源化利用技术浅析,柳树成,盛啸,煤炭工业的快速发展以及煤炭入选量的急剧增大,使得尾煤产生量越来越大。合理开发尾煤资源对缓解我国能源危机以及控制因尾煤带来
方形软包锂离子电池热物性参数的辨识方法,陈树成,吕超,锂离子电池具有高能量密度和长循环寿命等优点,使其在不同应用场合都得到了广泛的关注,其热相关问题关系到电池性能、寿命、安全
特别说明:此shell代码为原创,放在csdn上供大家下载,如果大家喜欢此代码,或者觉得值得推荐给他人,在其他网站或者地址提供下载,本人表示欢迎,只是希望各位注明出处,提供者为——树成,源地址为...
... 本脚本通过rhel5.x安装oracle10g与oracle11g的测试无误,其它linux版本不保证能正常工作。 此脚本使用方法: ... 运行简介: ...service oraclectrl start --启动数据库与侦听 service oraclectrl start db --仅仅启动...