线段树70pts TLE
查看原帖
线段树70pts TLE
768238
_WhiteDeer_楼主2024/10/2 10:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,a[N],op,x,y,k;
struct Tree{
	int l,r,num;
}tree[4*N];
inline void build(int u,int l,int r){
	tree[u].l=l; tree[u].r=r;
	if(l==r){
		tree[u].num=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	return;
}
inline void change(int u,int l,int r,int k){
	if(tree[u].l==tree[u].r&&l<=tree[u].l&&tree[u].r<=r){
		tree[u].num+=k;
	}
	if(tree[u].l>r||tree[u].r<l) return;
	if(l<=tree[u<<1].r) change(u<<1,l,r,k);
	if(tree[u<<1|1].l<=r) change(u<<1|1,l,r,k);
	return;
}
inline int query(int u,int x){
	if(tree[u].l==tree[u].r){
		return tree[u].num;
	}
	if(tree[u].l>x||tree[u].r<x) return 0;
	int sum=0;
	if(x<=tree[u<<1].r) sum+=query(u<<1,x);
	if(tree[u<<1|1].l<=x) sum+=query(u<<1|1,x);
	return sum;
}
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar(); 
	}
	return x*f;
}
signed main(){
	//freopen("P3368_2in.txt","r",stdin);
	//freopen("adminout.txt","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) cin >> a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		op=read();
		if(op==1){
			x=read(),y=read(),k=read();
			change(1,x,y,k);
		}else{
			x=read();
			printf("%lld\n",query(1,x));
		}
	}
	return 0;
}

本蒟蒻线段树写T了求调orz

2024/10/2 10:58
加载中...