线段树求调
查看原帖
线段树求调
752094
MornHus楼主2023/2/21 21:52
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,m,opt;
int a[500001];
ll lazy[500001<<2];
ll t[500001<<2];
void pushup(int x){
	t[x]=t[x<<1]+t[x<<1|1];
}
void pushdown(int k,int l,int r){
	if(lazy[k]){
		int mid=(l+r)>>1;
		lazy[k<<1]=lazy[k];
		lazy[k<<1|1]=lazy[k];
		t[k<<1]+=lazy[k]*(mid-l+1);
		t[k<<1|1]+=lazy[k]*(r-mid);
		lazy[k]=0;
	}
}
void build(int x,int l,int r){
	if(l==r){
		t[x]=a[l];
	}else{
		int mid=(l+r)>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		pushup(x);
	}
}
void update(int L,int R,ll v,int l,int r,int x){
	if(L<=l&&r<=R){
		lazy[x]=v;
		t[x]+=v*(r-l+1);
	}else{
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		if(L<=mid){
			update(L,R,v,l,mid,x<<1);
		}
		if(mid<R){
			update(L,R,v,mid+1,r,x<<1|1);
		}
		pushup(x);
	}
}
int query(int T,int l,int r,int x){
	if(l==r){
		return t[x];
	} else{
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		if(T<=mid){
			return query(T,l,mid,x<<1);
		}else{
			return query(T,mid+1,r,x<<1|1);
		}
	}
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	build(1,1,n);
	int x,y;ll z;
	for(int i=1;i<=m;i++){
		opt=read();
		if(opt==1){
			x=read();
			y=read();
			z=read();
			update(x,y,z,1,n,1);
		}else{
			x=read();
			printf("%d\n",query(x,1,n,1));
		}
	}
	return 0;
}
2023/2/21 21:52
加载中...