题目描述

食堂有N个打饭窗口，现在正到了午饭时间，每个窗口都排了很多的学生，而且每个窗口排队的人数在不断的变化。
现在问你第i个窗口到第j个窗口一共有多少人在排队？

输入

输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是一个正整数N（N<=30000），表示食堂有N个窗口。
接下来一行输入N个正整数，第i个正整数ai表示第i个窗口最开始有ai个人排队。（1<=ai<=50）
接下来每行有一条命令，命令有四种形式：
(1)Add i j，i和j为正整数，表示第i个窗口增加j个人（j不超过30）；
(2)Sub i j，i和j为正整数，表示第i个窗口减少j个人（j不超过30）；
(3)Query i j，i和j为正整数，i<=j，表示询问第i到第j个窗口的总人数；
(4)End 表示结束，这条命令在每组数据最后出现；
每组数据最多有40000条命令。

输出

对于每组输入，首先输出样例号，占一行。
然后对于每个Query询问，输出一个整数，占一行，表示询问的段中的总人数，这个数保持在int以内。

样例输入

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

样例输出

Case 1:
6
33
59
#include<bits/stdc++.h> 
#define maxn 500005
#define ll long long
using namespace std;
ll a,b,c;
ll ans=0;
struct node              
{
	int l,r,f;          
	ll w;    
}tree[maxn];          
void down(int k)                    
{
	tree[k*2].f+=tree[k].f;        
	tree[k*2+1].f+=tree[k].f; 
	tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);      
	tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1); 
	tree[k].f=0;                   
}
void build (int k,int lt,int rr)    
{
	tree[k].l=lt,tree[k].r=rr;      
	if (rr==lt)        
	{
		cin>>tree[k].w;
		return ;                    
	}
	int mid=(lt+rr)/2;
	build (k*2,lt,mid);             
	build (k*2+1,mid+1,rr);        
	tree[k].w=tree[k*2].w+tree[k*2+1].w;    
}
void add(int k)                      
{
	if (tree[k].l>=a&&tree[k].r<=b)  
	{
		tree[k].w+=(tree[k].r-tree[k].l+1)*c;   
		tree[k].f+=c;
		return ;                      
	}                                
	if (tree[k].f) down(k);           
	int mid=(tree[k].l+tree[k].r)/2;
	if (a<=mid) add(k*2);               
	if (b>mid) add(2*k+1);             
	tree[k].w=tree[k*2].w+tree[2*k+1].w;
}
void sum(int k)
{
	if (tree[k].l>=a&&tree[k].r<=b)
	{
		ans+=tree[k].w;
		return ;                      
	}
	if (tree[k].f) down(k);
	int mid=(tree[k].l+tree[k].r)/2; 
	if (a<=mid) sum(2*k);
	if (b>mid) sum(2*k+1);
} 
int main ()
{
	int n,q,t;
	char s[10001];
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cout<<"Case "<<i<<":"<<endl;
		cin>>n; 
		build(1,1,n);
		while(~scanf("%s",s))
		{
			if(s[0]=='E')
			break;
			if (s[0]=='A') 
			{
				cin>>a>>c;
				b=a;
				add(1); 
			}
			if (s[0]=='S') 
			{
				cin>>a>>c;
				b=a;
				c=-c;
				add(1); 
			}
			if (s[0]=='Q') 
			{
				ans=0;
				cin>>a>>b;
				sum(1);
				cout<<ans<<endl;
			}
		} 
	}
	
	return 0;
}