HDU 1166(敵兵布陣)

敵兵が布陣する
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9597    Accepted Submission(s): 4072
Problem Description
C国の死対頭A国はこの間軍事演習を行っていたので、C国のスパイの頭のDerekと彼の部下のTidyはまた忙しくなった.A国は海岸線に沿って直線的にN個の工兵キャンプを配置し、DerekとTidyの任務はこれらの工兵キャンプの活動状況を監視することである.ある種の先進的な監視手段を採用したため、各工兵キャンプの人数C国が把握しているのははっきりしていて、各工兵キャンプの人数が変動する可能性があり、数人の人手を増加したり減らしたりする可能性があるが、これらはC国の監視から逃れられない.
中央情報局は敵がどのような戦術を演習しているのかを研究しなければならないので、TidyはいつでもDerekにある連続した工兵キャンプが全部で何人いるかを報告しなければならない.例えば、Derekは「Tidy、すぐに3番目のキャンプから10番目のキャンプまで何人いるかを報告しなさい」と聞いた.Tidyはすぐにこのセグメントの総人数を計算し、報告しなければならない.しかし、敵兵キャンプの人数は常に変動しているが、Derekは尋ねるたびにセグメントが異なるので、Tidyは毎回1つ1つのキャンプの数を数えなければならず、すぐに疲れ果てて、DerekはTidyの計算速度にますます不満を持っている.「自分で計算してみてください.これは本当に疲れた仕事ですね.私はあなたが私を首にするのが嫌いです.」仕方なく、Tidyはコンピュータの専門家Windbreakerに電話して助けを求めるしかありませんでした.Windbreakerは言いました.「肥えた子、普段acmの問題をたくさん作って、アルゴリズムの本をたくさん読んでください.今は苦果を味わったでしょう.」Tidyは言いました.「私は間違っています.....「でもWindbreakerはもう電話を切った.Tidyは悩んでいる.これで彼は本当に崩壊するだろう.賢い読者、プログラムを書いてこの仕事を完成させることができるのか.しかし、プログラムの効率が足りなければ、TidyはDerekに叱られるだろう.
Input
1行目の整数Tは、Tグループのデータがあることを示す.
各グループのデータの最初の行には正の整数N(N<=50000)があり、敵にはN個の工兵キャンプがあり、次にはN個の正の整数があり、i個目の正の整数aiはi個目の工兵キャンプの開始時にai人がいることを示している(1<=ai<=50).
次に、各行に1つのコマンドがあります.コマンドには4つの形式があります.
(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は終了を示し、このコマンドは各グループのデータの最後に現れる.
データのセットあたり最大4,000個のコマンド
Output
i番目のグループのデータに対して、まず「Case i:」とリターンを出力し、
Queryクエリごとに整数を出力して車に戻り、クエリのセグメントの合計数を表します.この数は最大1000000を超えません.
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

#include <iostream>
using namespace std;

const int _N = 50005;
int a[_N << 2];
//           
void pushUp(int rt)
{
	a[rt] = a[rt << 1] + a[rt << 1 | 1];
}
void build(int l, int r, int rt)
{
	if(l == r)
	{
		cin>>a[rt];
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, rt << 1);
	build(m + 1, r, rt << 1 | 1);
	pushUp(rt);
}

void update(int p, int v, int l, int r, int rt)
{
	if(l == r)
	{
		a[rt] += v;
		return;
	}
	int m = (l + r) >> 1;
	if(p <= m)
		update(p, v, l, m, rt << 1);
	else
		update(p, v, m + 1, r, rt << 1 | 1);
	pushUp(rt);
}

int query(int L, int R, int l, int r, int rt)
{
	int v = 0;
	if(L <= l && r <= R)
	{
		return a[rt];
	}
	int m = (l + r) >> 1;
	if(L <= m)
		v += query(L, R, l, m, rt << 1);
	if(R > m)
		v += query(L, R, m + 1, r, rt << 1 | 1);
	return v;
}
int main()
{
	int t, n, cas;
	char op[10];
	cin>>t;
	for(cas = 1; cas <= t; cas++)
	{
		cout<<"Case "<<cas<<":
";
		cin>>n;
		build(1, n, 1);
		while(true)
		{
			cin>>op;
			if(op[0] == 'E')
				break;
			int a, b;
			cin>>a>>b;
			if(op[0] == 'Q')
				cout<<query(a, b, 1, n, 1)<<endl;
			else if(op[0] == 'A')
				update(a, b, 1, n, 1);
			else
				update(a, -b, 1, n, 1);
		}
	}
	return 0;
}

ツリー配列コードを添付します.

#include <iostream>
using namespace std;

const int _N = 50005;
int tree[_N];

int lowbit(int i)
{
	return i & (i ^ (i - 1));
}

void update(int i, int v, int n)
{
	while(i <= n)
	{
		tree[i] += v;
		i += lowbit(i);
	}
}

int query(int i)
{
	int sum = 0;
	while(i > 0)
	{
		sum += tree[i];
		i -= lowbit(i);
	}
	return sum;
}

int main()
{
	int t, cas, n, i, v;
	int a, b;
	char op[20];
	cin>>t;
	for(cas = 1; cas <= t; cas++)
	{
		cout<<"Case "<<cas<<":"<<endl;
		memset(tree, 0, sizeof(tree));
		cin>>n;
		for(i = 1; i <= n; i++)
		{
			cin>>v;
			update(i, v, n);
		}
		while(true)
		{
			cin>>op;
			if(op[0] == 'E')
				break;
			cin>>a>>b;
			if(op[0] == 'Q')
				cout<<query(b) - query(a - 1)<<endl;
			else if(op[0] == 'A')
				update(a, b, n);
			else
				update(a, -b, n);
		}
	}
	return 0;
}