线段树求调
查看原帖
线段树求调
1291460
under_hole楼主2024/6/30 17:51
#include<bits/stdc++.h>
using namespace std;
/*
question id:p3368
answer:
idea:STree
else:
*/
const int maxn=500105;
struct Node{
	int l,r;
	long long sum,k;
}nodes[4*maxn+5];
long long n,m,c,a,b,k,arr[maxn+5];
void build_tree(int nid,int l,int r){
	nodes[nid].l=l;
	nodes[nid].r=r;
	if(l==r)nodes[nid].sum=arr[l];
	else{
		int mid=l+(r-l)/2;
		build_tree(2*nid,l,mid);
		build_tree(2*nid+1,mid+1,r);
		nodes[nid].sum=nodes[2*nid].sum+nodes[2*nid+1].sum;
	}
	return;
}
void add(int np,int l,int r,int k){
	if(nodes[np].l>=l&&nodes[np].r<=r){
		nodes[np].sum+=(nodes[np].r-nodes[np].l+1)*k;
		nodes[np].k+=k;
	}
	else{
		int mid=nodes[np].l+(nodes[np].r-nodes[np].l)/2;
		if(nodes[np].k){
			nodes[np*2].sum+=(mid-l+1)*nodes[np].k;
			nodes[np*2].k+=nodes[np].k;
			nodes[np*2+1].sum+=(r-mid)*nodes[np].k;
			nodes[np*2+1].k+=nodes[np].k;
			nodes[np].k=0;
		}
		if(l<=mid)add(2*np,l,r,k);
		if(r>mid)add(2*np+1,l,r,k);
		nodes[np].sum=nodes[2*np].sum+nodes[2*np+1].sum;
	}
	return;
}
long long getsum(int cid,int np){
	if(cid==nodes[np].l&&nodes[np].r==cid)return nodes[np].sum;
	int mid=nodes[np].l+(nodes[np].r-nodes[np].l)/2;
	if(nodes[np].k){
		nodes[np*2].sum+=(mid-nodes[np].l+1)*nodes[np].k;
		nodes[np*2].k+=nodes[np].k;
		nodes[np*2+1].sum+=(nodes[np].r-mid)*nodes[np].k;
		nodes[np*2+1].k+=nodes[np].k;
		nodes[np].k=0;
	}
	if(cid<=mid)return getsum(cid,2*np);
	else if(cid>mid)return getsum(cid,2*np+1);
}
int main(){
	//freopen("P3368_2.in","r",stdin);
	//freopen("P3368_2.ans","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
	build_tree(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		switch(k){
			case 1:{
				scanf("%d%d%d",&a,&b,&c);
				add(1,a,b,c);
				break;
			}
			case 2:{
				scanf("%d",&a);
				printf("%lld\n",getsum(a,1));
				break;
			}
		}
	}
	return 0;
}

30tps,只对了测试点#1#3#4.

2024/6/30 17:51
加载中...