【玄关】9分代码(线段树+差分)求调
查看原帖
【玄关】9分代码(线段树+差分)求调
907667
thousands_of_years楼主2024/7/11 20:58

只A了第一个点

#include<bits/stdc++.h>
using namespace std;
long long lazy[800000],a[800000],b[800000],c[800000],opt,k,d,p,n,m;
void push_up(int num)
{
	c[num]=c[num*2]+c[num*2+1];
}
void build(int num,int l,int r)
{
	if(l==r)
	{
		c[num]=b[l];
	}
	else
	{
		int mid=(l+r)>>1;
		build(num*2,l,mid);
		build(num*2+1,mid+1,r);
		push_up(num);
	}
}
void push_down(int num,int l,int r)
{
	if(lazy[num])
	{
		lazy[num*2]+=lazy[num];
		lazy[num*2+1]+=lazy[num];
		int mid=l+r>>1;
		c[num*2]+=(mid-l+1)*lazy[num];
		c[num*2]+=(r-mid)*lazy[num];
		lazy[num]=0;
	}
}
void add(int x,int y,int l,int r,int num,int val)
{
	if(x<=l && r<=y)
	{
		lazy[num]+=val;
		c[num]+=(r-l+1)*val;
	}
	else
	{
		push_down(num,l,r);
		int mid=l+r>>1;
		if(x<=mid) add(x,y,l,mid,num*2,val);
		if(y>mid) add(x,y,mid+1,r,num*2+1,val);
		push_up(num);
	}
}
long long find(int x,int y,int l,int r,int num)
{
	if(x<=l && r<=y)
	{
		return c[num];
	}
		push_down(num,l,r);
		long long mid=l+r>>1,sum=0;
		if(x<=mid) sum+=find(x,y,l,mid,num*2);
		if(y>mid) sum+=find(x,y,mid+1,r,num*2+1);
		return sum;
}
int main()
{
//	freopen("P1438_2.in","r",stdin);
//	freopen("anssssss","w",stdout);
	long long l,r;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}
	build (1,1,n); 
	for(int i=1;i<=m;i++)
	{
		cin>>opt;
		if(opt==1)
		{
			cin>>l>>r>>k>>d;
			add(l,l,1,n,1,k);
			if(l<r)
			add(l+1,r,1,n,1,d);
			if(r<n)
			add(r+1,r+1,1,n,1,-(k+(r-l)*d));
		}
		else
		{
			cin>>p;
			cout<<find(1,p,1,n,1)<<endl;
		}
	}
	return 0;
}
2024/7/11 20:58
加载中...