poj3468 A Simple Problem with Integers

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

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

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.

感觉我开始刷起水题了……线段树不解释

因为数组开不够re了一次，没开long long又wa了一次

#include<cstdio>
#define LL long long
struct segtree{
	int l,r,dat,len;
	LL sum,tag;
}tree[1000000];
LL a[100010];
int n,m,x,y,z;
char ch;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void update(int k)
{
	tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
inline void pushdown(int k)
{
	LL t=tree[k].tag;tree[k].tag=0;
	if (!t)return;
	tree[k<<1].tag+=t;
	tree[k<<1|1].tag+=t;
	tree[k<<1].sum+=(LL)tree[k<<1].len*t;
	tree[k<<1|1].sum+=(LL)tree[k<<1|1].len*t;
}
inline void buildtree(int now,int l,int r)
{
	tree[now].l=l;tree[now].r=r;
	tree[now].len=r-l+1;
	if (l==r)
	{
		tree[now].dat=a[l];
		tree[now].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	buildtree(now<<1,l,mid);
	buildtree(now<<1|1,mid+1,r);
	update(now);
}
inline void change(int now,int l,int r,int d)
{
	pushdown(now);
	int x=tree[now].l,y=tree[now].r;
	if (x==l&&y==r)
	{
		tree[now].sum+=(LL)d*tree[now].len;
		tree[now].tag+=(LL)d;
		return;
	}
	int mid=(x+y)>>1;
	if(mid>=r)change(now<<1,l,r,d);
	else if (mid<l)change(now<<1|1,l,r,d);
	else
	{
		change(now<<1,l,mid,d);
		change(now<<1|1,mid+1,r,d);
	}
	update(now);
}
inline LL ask(int now,int l,int r)
{
	if (tree[now].tag)pushdown(now);
	int x=tree[now].l,y=tree[now].r;
	if(x==l&&y==r)return tree[now].sum;
	int mid=(x+y)>>1;
	if (mid>=r)return ask(now<<1,l,r);
	else if (mid<l)return ask(now<<1|1,l,r);
	else return ask(now<<1,l,mid)+ask(now<<1|1,mid+1,r);
}
int main()
{
	n=read();m=read();
	for (int i=1;i<=n;i++)a[i]=read();
	buildtree(1,1,n);
	for (int i=1;i<=m;i++)
	{
		ch=getchar();
		while (ch!='Q'&&ch!='C')ch=getchar();
		x=read();y=read();
		if (ch=='Q')printf("%lld
",ask(1,x,y));
		if (ch=='C')
		{
			z=read();
			change(1,x,y,z);
		}
	}
}