意甲冠军：一个典型的段树C，Q问题，有n的数量a[i] (1~n),C， a， b，c在[a,b]加c

Q a b 求[a,b]的和。

#include<cstdio>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<map>

#include<cmath>

#include<iostream>

#include <queue>

#include <stack>

#include<algorithm>

#include<set>

using namespace std;

#define INF 1e8

#define eps 1e-8

#define ll __int64

#define maxn 100005

#define mod  1000000009

struct node

{

	ll l,r,sum;

	ll lazy;

}tree[maxn*10];

ll a[maxn];

void Pushup(ll rt)

{

	tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;

}

void Pushdown(ll rt)

{

	if(tree[rt].lazy!=0)

	{

		tree[rt<<1].lazy+=tree[rt].lazy;//注意是+=,不是=;

		tree[rt<<1|1].lazy+=tree[rt].lazy;

		tree[rt<<1].sum+=(tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].lazy;

		tree[rt<<1|1].sum+=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*tree[rt].lazy;

		tree[rt].lazy=0;

	}

}

void build(ll l,ll r,ll rt)

{

	tree[rt].l=l;tree[rt].r=r;

	tree[rt].sum=0;tree[rt].lazy=0;

	if(l==r)

	{

		tree[rt].sum=a[l];

		return;

	}

	ll mid=(l+r)/2;

	build(l,mid,rt<<1);

	build(mid+1,r,rt<<1|1);

	Pushup(rt);

}

void update(ll rt,ll l,ll r,ll v)

{

	Pushdown(rt);

	if(tree[rt].l==l&&tree[rt].r==r)

	{

		tree[rt].lazy=v;

		tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*v;

		return ;

	}

	ll mid=(tree[rt].l+tree[rt].r)>>1;

	if(mid<l)

		update(rt<<1|1,l,r,v);

	else if(mid>=r)

		update(rt<<1,l,r,v);

	else

	{

		update(rt<<1,l,mid,v);

		update(rt<<1|1,mid+1,r,v);

	}

	Pushup(rt);

}

ll query(ll rt,ll l,ll r)

{

	if(tree[rt].l==l&&tree[rt].r==r)

		return tree[rt].sum;

	Pushdown(rt);

	ll mid=(tree[rt].l+tree[rt].r)>>1,ret=0;

	if(mid<l)

		ret+=query(rt<<1|1,l,r);

	else if(mid>=r)

		ret+=query(rt<<1,l,r);

	else

	{

		ret+=query(rt<<1,l,mid);

		ret+=query(rt<<1|1,mid+1,r);

	}

	Pushup(rt);

	return ret;

}

int main()

{

	ll n,m;

	while(~scanf("%I64d%I64d",&n,&m))

	{

		for(int i=1;i<=n;i++)

			scanf("%I64d",&a[i]);

		build(1,n,1);

		char s[2];

		ll u,v,c;

		while(m--)

		{

			scanf("%s",s);

			if(s[0]=='Q')

			{

				scanf("%I64d%I64d",&u,&v);

				printf("%I64d\n",query(1,u,v));

			}

			else

			{

				scanf("%I64d%I64d%I64d",&u,&v,&c);

				update(1,u,v,c);

			}

		}

	}

	return 0;

}

/*

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

10 22

1 2 3 4 5 6 7 8 9 10

Q 4 4

C 1 10 3

C 6 10 3

C 6 9 3

C 8 9 -100

C 7 9 3

C 7 10 3

C 1 10 3

Q 6 10

Q 6 9

Q 8 9

Q 7 9

Q 7 10

Q 1 10

Q 2 4

C 3 6 3

Q 9 9

Q 1 1

Q 5 5

Q 6 6

Q 7 7

Q 6 8

*/