社区讨论

P3368【模板】树状数组2 求调

学术版参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mib4u2cs
此快照首次捕获于
2025/11/23 11:02
3 个月前
此快照最后确认于
2025/11/23 12:42
3 个月前
查看原帖
题目传送门:P3369
我是直接把线段树的区间修改区间查询的板子改了一下去做这道区间修改单点查询的题,结果: 10个WA
贴上代码
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,_,a[N];
long long tree[4*N],add[4*N];
inline int read(){
	int x=0,sign=1;
	char ch=getchar();
	while(!isdigit(ch)){
		sign=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*sign;
}
void build(int k,int l,int r){
	if(l==r){
		tree[k]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	tree[k]=tree[k<<1]+tree[k<<1|1];
}
void apply(int k,int l,int r,int x){
	add[k]+=x;
	tree[k]+=(long long)x*(r-l+1);
}
void pushdown(int k,int l,int r,int mid){
	if(add[k]==0)return;
	apply(k<<1,l,mid,add[k]);
	apply(k<<1|1,mid+1,r,add[k]);
	add[k]=0;
}
void update(int k,int l,int r,int x,int y,int v){
	if(x<=l&&r<=y)return apply(k,l,r,v);
	int mid=l+r>>1;
	pushdown(k,l,r,mid);
	if(x<=mid)update(k<<1,l,mid,x,y,v);
	if(y>mid)update(k<<1|1,mid+1,r,x,y,v);
	tree[k]=tree[k<<1]+tree[k<<1|1];
}
long long query(int k,int l,int r,int x,int y){
	if(l==r)return tree[k];
	int mid=l+r>>1;
	pushdown(k,l,r,mid);
	long long res=0;
	if(x<=mid)res+= query(k<<1,l,mid,x,y);
	if(y>mid) res+= query(k<<1|1,mid+1,r,x,y);
	return res;
}
int main(){
    n=read();_=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(_--){
    	int op=read();
    	if(op==1){
    		int l=read(),r=read(),x=read();
    		update(1,1,n,l,r,x);
		}
		else{
			int i=read();
			printf("%lld\n",query(1,1,n,i,i));
		}
	}
}

有没有大牛帮我找找错~~~

回复

6 条回复,欢迎继续交流。

正在加载回复...