re求助
查看原帖
re求助
148104
赤坂时寞楼主2021/7/27 10:27

第一个点总是re,后面几个点AC,在自己电脑上跑是正确的???

#include<bits/stdc++.h>
using namespace std;
const int M=1000000;
long long n,a[M],m,ans[M];
struct SegmentTree{
	int l,r;
	int sum;
	int lazy;
}tree[M*4];
void build(int p,int l,int r){
	tree[p].l=l;tree[p].r=r;
	if(l==r){tree[p].sum=a[l];return;} 
	int mid=(l+r)/2;
	build(p*2,l,mid); 
	build(p*2+1,mid+1,r); 
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
} 
void print(int p)
{
	cout<<p<<" "<<tree[p].l<<" "<<tree[p].r<<" "<<tree[p].sum<<endl;
	if(tree[p].l==tree[p].r)return;
	print(p*2);
	print(p*2+1);
} 
void pushdown(int p){
	if(tree[p].lazy){
		tree[p*2].sum+=tree[p].lazy*(tree[p*2].r-tree[p*2].l+1);
		tree[p*2+1].sum+=tree[p].lazy*(tree[p*2+1].r-tree[p*2+1].l+1);
		tree[p*2].lazy+=tree[p].lazy;
		tree[p*2+1].lazy+=tree[p].lazy;
		tree[p].lazy=0; 
	}
}
int query(int p,int l,int r){
	if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
	pushdown(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(r<=mid) return query(p*2,l,r);
	if(l>mid) return query(p*2+1,l,r);
	else return query(p*2,l,r)+query(p*2+1,l,r);
}
void update(int p,int l,int r,int d){
	if(l<=tree[p].l&&tree[p].r<=r){
		tree[p].sum+=d*(tree[p].r-tree[p].l+1);
		tree[p].lazy+=d; 
		return;
	}
	pushdown(p); 
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) update(p*2,l,r,d);
	if(r>mid) update(p*2+1,l,r,d);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>a;
		if(a==1){
		cin>>b>>c>>d;
		update(1,b,c,d);
		}
		if(a==2){
		cin>>b>>c;
		cout<<query(1,b,c)<<endl;
		}
	}
	return 0;
}

2021/7/27 10:27
加载中...