蒟蒻求助,线段树样例过不了
查看原帖
蒟蒻求助,线段树样例过不了
162909
鬼才权家浩666楼主2021/12/29 22:43
//2021 12 29
#include<bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)
using namespace std;
const int maxN=5e5+10;
typedef long long ll;
struct Tree{
	ll v,lazy;
}tree[maxN<<2];
ll n,m;
ll read(),query(ll,ll,ll,ll);
void work(),write(ll x),push_up(ll),push_down(ll,ll,ll),up_date(ll,ll,ll,ll,ll,ll),build(ll,ll,ll);
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	work();
	return 0;
}
void work(){
	n=read(),m=read();
	build(1,1,n);
	while(m--){
		ll op=read(),x=read();
		if(op<2){
			ll y=read();
			up_date(1,1,n,x,y,read());
		}
		else write(query(1,1,n,x)),puts("");
	}
}
ll read(){
	ll s=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void build(ll k,ll l,ll r){
	if(l==r){
		tree[k].v=read();
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(k);
}
void up_date(ll k,ll l,ll r,ll x,ll y,ll v){
	if(y<l||r>x) return;
	if(x<=l&&y>=r){
		tree[k].v+=(r-l+1)*v;
		tree[k].lazy+=v;
		return;
	}
	push_down(k,l,r);
	up_date(ls,l,mid,x,y,v);
	up_date(rs,mid+1,r,x,y,v);
	push_up(k);
}
void push_down(ll k,ll l,ll r){
	if(!tree[k].lazy) return;
	tree[ls].lazy+=tree[k].lazy,tree[ls].v+=(mid-l+1)*tree[k].lazy;
	tree[rs].lazy+=tree[k].lazy,tree[rs].v+=(r-mid)*tree[k].lazy;
	tree[k].lazy=0;
}
void push_up(ll k){
	tree[k].v=tree[ls].v+tree[rs].v;
}
ll query(ll k,ll l,ll r,ll x){
	if(x<l||x>r) return 0;
	if(l==r) return tree[k].v;
	push_down(k,l,r);
	return query(ls,l,mid,x)+query(rs,mid+1,r,x);
}
2021/12/29 22:43
加载中...