线段树10分求调
查看原帖
线段树10分求调
1034211
TIS_Minecraft_CNAI楼主2024/10/19 10:50

10分代码:(样例是对的)

#include<bits/stdc++.h>
using namespace std;

struct node{
	long long l;
	long long r;
	long long f;
	long long w;
}tree[5000005];

inline void build(long long k,long long ll,long long rr){
	tree[k].l=ll;
	tree[k].r=rr;
	if(tree[k].l==tree[k].r){
		cin>>tree[k].w;
		return ;
	}
	long long mid=(tree[k].l+tree[k].r)/2;
	build(2*k,ll,mid);
	build(2*k+1,mid+1,rr);
	tree[k].w=tree[2*k].w+tree[2*k+1].w;
}

inline void down(long long k) {
	tree[2*k].f+=tree[k].f;
	tree[2*k+1].f+=tree[k].f;
	tree[2*k].w+=tree[k].f*(tree[2*k].r-tree[2*k].l+1);
	tree[2*k+1].w=tree[k].f*(tree[2*k+1].r-tree[2*k+1].l+1);
	tree[k].f=0;
}

inline void change_interval(long long k,long long x,long long y,long long add){
	if(x<=tree[k].l && y>=tree[k].r) {
		tree[k].w+=add*(tree[k].r-tree[k].l+1);
		tree[k].f+=add;
		return ;
	}
	if(tree[k].f) {
		down(k);
	}
	long long mid=(tree[k].l+tree[k].r)/2;
	if(x<=mid) {
		change_interval(2*k,x,y,add);
	}
	if(y>mid) {
		change_interval(2*k+1,x,y,add);
	}
	tree[k].w=tree[2*k].w+tree[2*k+1].w;
}

inline long long ask_point(long long k,long long x){
	if(tree[k].l==tree[k].r){
		return tree[k].w;
	}
	if(tree[k].f) {
		down(k);
	}
	long long mid=(tree[k].l+tree[k].r)/2;
	if(x<=mid){
		return ask_point(2*k,x);
	}
	else{
		return ask_point(2*k+1,x);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long n,m;
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		long long op;
		cin>>op;
		if(op==1){
			long long x,y,k;
			cin>>x>>y>>k;
			change_interval(1,x,y,k);
		}
		else{
			long long x;
			cin>>x;
			cout<<ask_point(1,x)<<"\n";
		}
	}
	return 0;
}

求调

2024/10/19 10:50
加载中...