3036062_ac_2061ms_8840k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#define INIT (node *)malloc(sizeof(node))

int n, q;
__int64 A[100005];
struct node
{
	__int64 sum;
	int l, r;
	__int64 c;
	node *left, *right;
};

node *root;

node *create(node *s,int l,int r,__int64 &sum)
{
	int mid;
	__int64 a, b;
	node *p, *q;

	if(l==r)
	{
		s->sum = A[l];
		sum = s->sum;
		s->l = s->r = l;
		s->left = NULL;
		s->c = 0;
		s->right = NULL;
		return s; 
	}
	mid = (l+r)/2;
	p = INIT;q = INIT;
	s->l = l;
	s->r = r;
	s->c = 0;
	s->left = create(p,l,mid,a);
	s->right = create(q,mid+1,r,b);
	sum = s->sum = a+b;
	return s;
}

__int64 find(node *s,int l,int r)
{
	int mid;
	__int64 ret, t;

	t = r-l+1;
	ret = s->c*t;
	if(s->l==l&&s->r==r)
	{
		return ret+s->sum;
	}
	mid = (s->l+s->r)/2;
	if(mid>=r)
		return ret+find(s->left,l,r);
	else
	{
		if(mid<l)
			return ret+find(s->right,l,r);
		else
			return ret+find(s->left,l,mid)+find(s->right,mid+1,r);
	}
}

void update(node *s,int l,int r,__int64 c)
{
	int mid;
	__int64 t;

	if(l==s->l&&r==s->r)
	{
		s->c += c;
		return ;
	}
	t = r-l+1;
	t *= c;
	s->sum += t;
	mid = (s->l+s->r)/2;
	if(mid >= r)
	{
		update(s->left,l,r,c);
	}
	else
	{
		if(mid < l)
		{
			update(s->right,l,r,c);
		}
		else
		{
			update(s->left,l,mid,c);
			update(s->right,mid+1,r,c);
		}
	}
}

int main()
{
	int i;
	char op[2];
	__int64 c;
	int a, b;

	scanf("%d%d",&n,&q);
	for(i = 1; i <= n; i++)
	{
		scanf("%I64d",&A[i]);
	}
	root = INIT;
	create(root,1,n,c);
	for(i = 0; i < q; i++)
	{
		scanf("%s",op);
		if(op[0]=='C')
		{
			scanf("%d%d%I64d",&a,&b,&c);
			if(c!=0)
			{
				update(root,a,b,c);
			}
		}
		else
		{
			scanf("%d%d",&a,&b);
			printf("%I64d\n",find(root,a,b));
		}
	}
	return 0;
}