社区讨论
too many or too few lines求助
P3368【模板】树状数组 2参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6up1lc
- 此快照首次捕获于
- 2025/11/20 11:07 4 个月前
- 此快照最后确认于
- 2025/11/20 11:07 4 个月前
想用线段树水板子,结果WA了2/9/10,求助
CPP#include<bits/stdc++.h>
using namespace std;
int num[100007],s,n,m,k,x,y,c,cc,xx,yy;
struct node_tree{
int lft,rgt;
long long s,lazy;
}seg_tree[400007];
void build_tree(int r,int x,int y){
seg_tree[r].lft=x,seg_tree[r].rgt=y,seg_tree[r].lazy=0;
if(x==y){
seg_tree[r].s=num[x];
return;
}
int mid=(x+y)/2;
build_tree(2*r,x,mid);
build_tree(2*r+1,mid+1,y);
seg_tree[r].s=seg_tree[2*r].s+seg_tree[2*r+1].s;
}
void pushdown(int r)
{
seg_tree[r*2].lazy+=seg_tree[r].lazy;
seg_tree[r*2+1].lazy+=seg_tree[r].lazy;
seg_tree[r*2].s+=(seg_tree[r*2].rgt-seg_tree[r*2].lft+1)*seg_tree[r].lazy;
seg_tree[r*2+1].s+=(seg_tree[r*2+1].rgt-seg_tree[r*2+1].lft+1)*seg_tree[r].lazy;
seg_tree[r].lazy=0;
}
long long query(int r,int x,int y){
if(seg_tree[r].lft>y||seg_tree[r].rgt<x) return 0;
if(seg_tree[r].lft>=x&&seg_tree[r].rgt<=y) return seg_tree[r].s;
if(seg_tree[r].lazy) pushdown(r);
return query(r*2,x,y)+query(r*2+1,x,y);
}
void change(int r,int x,int y){
if(seg_tree[r].lft>y||seg_tree[r].rgt<x) return;
if(seg_tree[r].lft>=x&&seg_tree[r].rgt<=y){
seg_tree[r].s+=(seg_tree[r].rgt-seg_tree[r].lft+1)*k;
seg_tree[r].lazy+=k;
return;
}
if(seg_tree[r].lazy) pushdown(r);
change(r*2,x,y);
change(r*2+1,x,y);
seg_tree[r].s=seg_tree[2*r].s+seg_tree[2*r+1].s;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build_tree(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d",&cc);
{
if(cc==1)
{
scanf("%d%d%d",&xx,&yy,&k);
change(1,xx,yy);
}
else
{
scanf("%d",&xx);
long long fff=query(1,xx,xx);
printf("%lld\n",fff);
}
}
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...