你有N整数,A1, A2, … , AN..你需要处理两种操作。一种操作是在给定的时间间隔内向每个数字添加一些给定的数字。另一种是要求给定区间内的数字之和。
输入
第一行包含两个数字N和Q..1≤N,Q≤100000。
第二行包含N的初始值A1, A2, … , AN..-1000000000≤Ai≤1000000000。
下一个Q行表示操作。
“Ca b c“意思是增加c每一个Aa, Aa+1, … , Ab..-10000≤c≤10000。
“Qa b“意思是查询…之和。Aa, Aa+1, … , Ab.
输出量
你需要回答所有Q命令有条不紊。一字一句地回答。
样本输入
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
样本输出
4
55
9
15
这道题也是个裸题,主要知识点,懒人标记入门 区间修改,区间查询。
上代码
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int MAX = 50000 + 10;
long long tree[MAX*4], lz[MAX*4],len[MAX];
void init(){
memset(tree,0,sizeof(tree));
memset(lz,0,sizeof(lz));
}
//建树成功!
void build(int node, int l,int r)
{
len[node]=r-l+1;
if(l==r)
{
cin>>tree[node];
return ;
}
int mid=(l+r)/2;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
tree[node]=tree[2*node]+tree[2*node+1];
}
//ok! gaizhi1chenghgong
void push_down(int node){
if(lz[node]){
lz[node*2] += lz[node];
lz[node*2 + 1] += lz[node];
// 注意线段树的数据更新方式要一致
tree[node*2] += len[node*2]*lz[node];
tree[node*2 + 1] += len[node*2+1]*lz[node];
lz[node] = 0;
}
}
void update_range(int node,int l,int r,int L,int R,int add){
if(l <= L && r >= R){
lz[node] += 1LL*add;
tree[node] += 1LL*(R - L + 1)*add; // 更新方式
return;
}
push_down(node);
int mid = (L+R) / 2;
if(mid >= l) update_range(node*2,l,r,L,mid,add);
if(mid < r) update_range(node*2 + 1,l,r,mid+1,R,add);
tree[node] = tree[node*2] + tree[node*2 + 1];
}
long long query(int l,int r,int node,int x, int y)
{
if(x<=l&&y>=r)
return tree[node];
push_down(node);
int mid=(l+r)/2;
int sum=0;
if(mid>=x){
sum=sum+query( l, mid, node*2, x, y);
}
if(mid<y)//chadiancuol
{
sum=sum+query( mid+1, r, node*2+1, x, y);
}
return sum;
}
int main()
{
int m,n;
init();
char s[MAX];
while(scanf("%d%d",&m,&n)!=EOF)
{
build(1,1,m);
int x, y,z;
while(n--)
{
scanf("%s",s);
if(s[0]=='Q')
{
scanf("%d %d",&x,&y);
printf("%lld\n",query(1,m,1,x,y));
}
if(s[0]=='C')
{
scanf("%d %d %d",&x,&y,&z);
update_range(1,1,m,x,y,z);
}
}
}
return 0;
}
回去发现又错误,检查了将近两小时,才发现,更新区域的值函数,形式参数为小写的了l,r,然后与大写的搞混了。
这样的情况已经不是第一次发生了,找这种错误耗费了我太多无用功,
下次如果再有超过半小时还没找出错误的,感觉思路绝对没问题,就自己重新写,然后就是函数的形式参数的名字尽量要区分开,找的要猝死了,感觉啊。。。
void update_range(int l,int r,int node,int L,int R,int add){
if(L <=l && R >= r){
lz[node] += add;
tree[node] += len[node]*add; //
return;
}
push_down(node);
int mid = (l+r) / 2;
if(mid >= L) update_range(l,mid,node*2,L,R,add);
if(mid < R) update_range(mid+1,r,node*2+1,L,R,add);//就错这里,,,,,
tree[node] = tree[node*2] + tree[node*2 + 1];
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114887.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...