这个线段树到底哪里爆了?qaq
查看原帖
这个线段树到底哪里爆了?qaq
359422
无咕_楼主2021/2/6 23:25

RT,样例都没过,(我这是抄的学长的代码,但没查出错误诶),怎么救治?

https://www.luogu.com.cn/problem/P3372

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX=4e5+9;
typedef long long int ll;
struct Tree{
	ll l,r,tag,a;
}tree[MAX];
ll n,m,num_tree=1,ans;
ll te,tx,ty,tk,a[MAX];
void pushdown(ll id,ll l,ll r){
	ll mid=(l+r)/2;
	tree[tree[id].l].a+=tree[id].tag*(mid-l+1);
	tree[tree[id].l].tag+=tree[id].tag;
	tree[tree[id].r].a+=tree[id].tag*(r-(mid+1)+1);
	tree[tree[id].r].tag+=tree[id].tag;
	tree[id].tag=0;
}void build(ll l,ll r,ll id){
	if(l==r){
		tree[id].a=a[l];
		return ;
	}ll mid=(l+r)/2;
	num_tree++;
	tree[id].l=num_tree;
	build(l,mid,tree[id].l);
	num_tree++;
	tree[id].r=num_tree;
	build(mid+1,r,tree[id].r);
	tree[id].a=tree[tree[id].l].a+tree[tree[id].r].a;
}void update(ll id,ll l,ll r,ll ls,ll rs,ll k){
	if(l==ls&&r==rs){
		tree[id].a+=k*(r-l+1);
		tree[id].tag+=k;
		pushdown(id,l,r);
		return;
	}ll mid=(l+r)/2;
	pushdown(id,l,r);
	if(ls>mid)update(tree[id].r,mid+1,r,ls,rs,k);
	else if(rs<=mid)update(tree[id].l,l,mid,ls,rs,k);
	else update(tree[id].r,mid+1,r,mid+1,rs,k),update(tree[id].l,l,mid,ls,mid,k);
	tree[id].a=tree[tree[id].l].a+tree[tree[id].r].a;
}void quary(ll id,ll l,ll r,ll ls,ll rs){
	if(l==ls&&r==rs){
		ans+=tree[id].a;
		return;
	}ll mid=(l+r)/2;
	pushdown(id,l,r);
	if(mid<ls)quary(tree[id].r,mid+1,r,ls,rs);
	else if(rs<=mid)quary(tree[id].l,l,mid,ls,rs);
	else quary(tree[id].r,mid+1,r,mid+1,rs),quary(tree[id].l,l,mid,ls,mid);
}int main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}build(1,n,1);
	for(int i=1;i<=m;i++){
		scanf("%lld %lld %lld",&te,&tx,&ty); 
		if(te==1){
			scanf("%lld",&tk);
			update(1,1,n,tx,ty,tk);
		}else{
			quary(1,1,n,tx,ty);
			printf("%lld\n",&ans);
			ans=0;
		}
	}
	return 0;
}/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
*/
2021/2/6 23:25
加载中...