早上学,中午做,晚上走,救救孩子!
查看原帖
早上学,中午做,晚上走,救救孩子!
265037
UntilR楼主2020/7/25 17:03

只A了一个点,求助大佬!!

#include <bits/stdc++.h>
using namespace std;
struct tree
{
	int l,r;
	long long pl,mi,tag;
}a[2000001];
int n,m,ori[1000001];
long long an,in;
void make_down(int dot,int k)
{
	a[dot*2].tag+=k;
	a[dot*2].pl+=k*(a[dot*2].r-a[dot*2].l+1);
	//a[dot*2].mi+=k;
	a[dot*2+1].tag+=k;
	a[dot*2+1].pl+=k*(a[dot*2+1].r-a[dot*2+1].l+1);
	//a[dot*2+1].mi+=k;
	return;
}
void check_down(int tl,int tr,int l,int r,int dot)
{
	if(tl<=l&&r<=tr)
	{
		an+=a[dot].pl;
		//in=min(in,a[dot].mi);
		return;
	}
	make_down(dot,a[dot].tag);
	int mid=(l+r)/2;
	if(tl<=mid)
		check_down(tl,tr,l,mid,dot*2);
	if(tr>mid)
		check_down(tl,tr,mid+1,r,dot*2+1);
	return;
}
void tag_down(int tl,int tr,int l,int r,int k,int dot)
{
	if(tl<=l&&r<=tr)
	{
		a[dot].pl+=k*(r-l+1);
		//a[dot].mi+=k;
		a[dot].tag=k;
		return;
	}
	make_down(dot,a[dot].tag);
	int mid=(l+r)/2;
	if(tl<=mid)
		tag_down(tl,tr,l,mid,k,dot*2);
	if(tr>mid)
		tag_down(tl,tr,mid+1,r,k,dot*2+1);
	a[dot].pl=a[dot*2].pl+a[dot*2+1].pl;
	//a[dot].mi=min(a[dot*2].mi,a[dot*2+1].mi);
	return;
}
void build_tree(int dot,int left,int right)
{
	a[dot].l=left;
	a[dot].r=right;
	if(left==right)
	{
		a[dot].mi=ori[left];
		a[dot].pl=ori[left];
		return;
	}
	int mid=(left+right)/2;
	build_tree(dot*2,left,mid);
	build_tree(dot*2+1,mid+1,right);
	a[dot].pl=a[dot*2].pl+a[dot*2+1].pl;
	//a[dot].mi=min(a[dot*2].mi,a[dot*2+1].mi);
	return; 
}
int main()
{
	std::ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>ori[i];
	build_tree(1,1,n);
	for(int k=1;k<=m;k++)
	{
		int step;
		cin>>step;
		if(step==1)
		{
			int left,right,weight;
			cin>>left>>right>>weight;
			tag_down(left,right,1,n,weight,1);
		}
		else
		{
			int left,right;
			cin>>left>>right;
			an=0;
			//in=1e9;
			check_down(left,right,1,n,1);
			cout<<an<<endl;
		}
	}
	return 0;
}
2020/7/25 17:03
加载中...