In c + +, cin is a big pit. Why do you say that? Let's look at the solution first.

The operation of this problem on the line segment tree is very simple (if you are lazy, you don't write the detailed process...), If you don't know the line segment tree, click the link below (this is equal to this question)
Important line segment tree algorithm

Title: enemy troop deployment

Country A, the sworn enemy of country C, is conducting military exercises these days, so Derek, the spy leader of country C, and his Tidy are busy again. Country A has arranged N engineering camps along A straight line along the coastline. Derek and Tidy's task is to monitor the activities of these engineering camps. Due to the adoption of some advanced monitoring means, the number of people in each engineering camp is well known in country C. the number of people in each engineering camp may change, and some people may be increased or reduced, but these can not escape the monitoring of country C.

The CIA needs to study what tactics the enemy is practicing, so tidy should report to Derek at any time how many people there are in a continuous engineering camp. For example, Derek asked, "tidy, report immediately how many people there are from the third camp to the tenth camp!" Tidy is about to start counting the total number of people in this section and report it. However, the number of enemy soldiers in the camp often changes, and Derek's paragraphs are different every time, so tidy had to count one camp at a time and was soon exhausted, Derek is more and more dissatisfied with tidy's calculation speed: "you dead fat boy, if you calculate so slowly, I'll fire you!" tidy thought: "calculate it yourself. It's really a tiring job! I wish you could fire me!" In desperation, tidy had to call windbreaker, a computer expert, for help. Windbreaker said, "dead fat boy, I told you to do more acm problems and read more algorithm books. Now you have tasted the bitter fruit!" Tidy said, "I know I'm wrong..." But windbreaker has hung up. Tidy is very upset. He will really collapse. Smart reader, can you write a program to help him finish the work? However, if your program is not efficient enough, tedy will still be scolded by Derek

Input

The first line is an integer T, which indicates that there are t groups of data.

The first row of each group of data has a positive integer N (N < = 50000), indicating that the enemy has N engineering camps, followed by N positive integers. The i positive integer ai represents that there are ai individuals at the beginning of the i engineering camp (1 < = ai < = 50).

Next, there is a command on each line. The command has four forms:

(1) Add i, J, i and j are positive integers, indicating that J people are added in the ith camp (J does not exceed 30)

(2) Sub i, J, i and j are positive integers, indicating the reduction of J persons in the ith camp (J does not exceed 30);

(3) Query i, J, i and j are positive integers, i < = J, indicating the total number of people from camp i to camp J;

(4)End indicates the end, and this command appears at the end of each group of data;

Up to 40000 commands per set of data

Output

For group i data, first output "Case i:" and enter,

For each Query query, output an integer and enter, indicating the total number of people in the Query segment. This number should be kept within int.

Sample Input

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

Sample Output

Case 1:
6
33
59

Here is the AC Code:

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdio.h>
const int maxn = 1e5+5;
using namespace std;
struct Nd //Define segment tree nodes 
{
	int left;//Left child 
	int right;//Right child 
	int val;//The node value 
};
static Nd arr[maxn*4]; //There are 1024 nodes randomly 
//initialization 
void build(int l,int r,int i)//Using recursion to construct line segment tree 
{
	arr[i].left=l;//Assign the values of the left and right intervals to the nodes 
	arr[i].right=r;
	if(r==l)
	{
		scanf("%d",&arr[i].val);
		return ;
	} 
	build(l,(l+r)/2,i<<1);//Recursion to left node 
	build((r+l)/2+1,r,i<<1|1); //Recursion to right node 
	arr[i].val = arr[i<<1].val+arr[i<<1|1].val;//Complete the assignment of the child node to the parent node during recursive backtracking 
} 
void update(int d,int r,int b)// d is the current node, r is the updated node, and b is the value of the changed node. This recursive algorithm is actually binary search 
{
	if(arr[d].left==arr[d].right)//When recursing to the leaf node, the subscript must be r. note that only the leaf node can be changed 
	{
		arr[d].val+=b;//update value 
		return;
	}	
	int mid = (arr[d].left+arr[d].right)>>1;
	if(r>mid)update(d<<1|1,r,b);//Recursion to right
	else
	update(d<<1,r,b);//Recursion to left
	arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//Complete the assignment of the child node to the parent node during recursive backtracking 
} 
int query(int d,int l,int r)//This is the sum of the return interval 
{
	 int sum = 0;
	if(l<=arr[d].left&&r>=arr[d].right)//1. If within the scope of purpose 2 If it is a leaf node 
		sum += arr[d].val;
	else{
		int mid = ((arr[d].left+arr[d].right)/2);
		if(l<=mid)		
			(r>mid)?sum+=query(d<<1,l,mid):sum+=query(d<<1,l,r);
		if(r>mid)
			(l<=mid)?sum+=query(d<<1|1,mid+1,r):sum+=query(d<<1|1,l,r);
	}
	return sum;
}
int main()
{
	
	int n1,a,n,m;
	scanf("%d",&n1);
	for(int k=0;k<n1;k++)
	{
		scanf("%d",&a);
		build(1,a,1);
		string str;
		cout<<"Case "<<k+1<<":"<<endl;
		while(1)
		{
			scanf("%s",str.begin());
			if(str[0]=='E')break;
			else{
				scanf("%d%d",&n,&m);
				if(str[0]=='A')
				{
					update(1,n,m);
				}else
				if(str[0]=='S')
				{
					update(1,n,m*-1);
				}else
				if(str[0]=='Q')
				{
					cout << query(1,n,m) << endl;
				}
			}
		}
	}
	return 0;
} 

It takes only about 360ms after submission, which is far less than 1 second.

But if you change the input function of the above code to cin. Then directly Time out (time > 1000ms).

I foolishly studied for an hour before I found this bug.

I checked some data and found that cin can actually be adjusted to the same efficiency as scanf. Just add:

std::ios::sync_with_stdio(false);
So I submitted it again.

Fast, I didn't feel it, and then when time=25ms, directly Time errors. Cause an exception occurred inside the function.

Using this code is said to have many bug s. I don't know the details...

To sum up:

In the future, in the topic with a large amount of data, remember to use cin input in the loop.

Thank you for watching. I hope you can give your advice. If there is anything wrong, you can point it out.

It's not easy to create. If you feel it's helpful, please praise it. Thank you.