Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 162203 Accepted Submission(s): 67064

Problem Description

Country C's deadly rival, Country A, was conducting military exercises during this time, so Derek, the country's spy chief, and Tidy under him were busy again.State A has N camps along a straight line along the coastline, and Derek and Tidy are tasked with monitoring their activities.As a result of some advanced means of monitoring, the number of people in each of the camps is clear to all in Country C. The number of people in each of the camps may change, increasing or decreasing the number of people, but these will not escape the surveillance of Country C.

The CIA is investigating what tactics the enemy is trying to execute, so Tidy needs to report to Derek at any time how many people there are in a consecutive engineering camp. For example, Derek asks, "Tidy, now report how many people there are from the third to the tenth camps!" Tidy is about to start calculating and reporting the total number in this section.But the number of enemy camps often changes, and Derek asks for different sections each time, so Tidy had to go to one camp at a time, and was soon exhausted. Derek became increasingly dissatisfied with Tidy's calculation speed: "You fat boy, you're so slow, I'm fired you squid!" Tidy thought: "Look at it yourself, it's really a tiresome job! I hate it!"You stir-fry me squid!"Unfortunately, Tidy had to call the computer expert Windbreaker for help. Windbreaker said:"Dead fat boy, ask you to do more acm questions and read more algorithmic books in normal time. Now it's bitter!"Tidy said:"I know it's wrong.""But Windbreaker has hung up the phone.Tidy is distressed. He's really going to crash, smart reader. Can you write a program to help him do this?But if your program isn't efficient enough, Tidy will still be scolded by Derek.

Input

The first row is an integer T, indicating that there is a T group of data.

Each set of data has a positive integer N (N<=50000) in the first row, indicating that the enemy has N camps, followed by N positive integers, and a positive integer AI in the second row represents an AI individual at the beginning of the first camp (1<=ai<=50).

Next, there is a command on each line in four forms:

(1) Add i j,i and j are positive integers, indicating an increase of J individuals (j not more than 30) in the first camp

(2) Sub i j, i and j are positive integers, indicating a reduction of J individuals in site i I (j not exceeding 30);

(3) Query I j, I and j are positive integers, i<=j, indicating the total number of camps I to J being asked;

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

Up to 40,000 commands per set of data

Output

For group I data, first output "Case i:" and carriage return.

For each Query query, output an integer and return, indicating the total number of people in the query segment, which remains 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

Author

Windbreaker

Recommend

Eddy

Ideas:

The simplest single point modification, interval query

Tree Array Writing

#include<bits/stdc++.h> using namespace std; const int N = 1e5+6; int n,m; int tr[N],a[N]; int lowbit(int x){ return x & (-x); } void add(int x,int y){ while(x<=n){ tr[x]+=y; x+=lowbit(x); } // for(int i=0;i<=x;i+=lowbit(i)) tr[i]+=y; } int sum(int x){ int res=0; while(x>0){ res+=tr[x]; x-=lowbit(x); } // for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } int main(){ int t; scanf("%d",&t); for(int i=1;i<=t;i++){ cout<<"Case "<<i<<":"<<endl; memset(tr,0,sizeof tr); memset(a,0,sizeof a); // int n; scanf("%d",&n); for(int j=1;j<=n;j++){ scanf("%d",&a[j]); add(j,a[j]); } char s[10]; int x,y; while(~scanf("%s",s)&&strcmp(s,"End")){ scanf("%d%d",&x,&y); if(s[0]=='Q') cout<<sum(y)-sum(x-1)<<endl; else if(s[0]=='A') add(x,y); else if(s[0]=='S') add(x,-y); //else break; } } return 0; }

Segment Tree Writing

#pragma GCC optimize(2) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<cmath> #include<algorithm> #include <vector> #include<stdio.h> using namespace std; typedef long long ll; #define I_int ll inline int read() { int 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; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=51000; struct node{ int l,r; int sum;///Total maintenance }tr[maxn*4]; int n,a[maxn]; void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r){ if(l==r){ tr[u].l=l;tr[u].r=r;tr[u].sum=a[r]; } else{ tr[u].l=l;tr[u].r=r; int mid=tr[u].l+tr[u].r >>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void add(int u,int x,int y){ if(tr[u].l==tr[u].r) tr[u].sum+=y; else{ int mid= tr[u].l+tr[u].r >> 1; if(x<=mid) add(u<<1,x,y); else add(u<<1|1,x,y); pushup(u); } } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l + tr[u].r >> 1; int sum=0; if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum; } int main(){ int t;t=read(); for(int num=1;num<=t;num++){ // memset(tr,0,sizeof tr); // memset(a,0,sizeof a); n=read(); for(int i=1;i<=n;i++) a[i]=read(); build(1,1,n); string op; int x,y; printf("Case %d:\n",num); while(1){ cin>>op; if(op=="End") break; else if(op=="Add"){ x=read();y=read(); add(1,x,y); } else if(op=="Sub"){ x=read();y=read(); add(1,x,-y); } else{ x=read();y=read(); printf("%d\n",query(1,x,y)); } } } return 0; }