hdu 1166敵兵布陣(線段樹)
敵兵が布陣する
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 45437 Accepted Submission(s): 19314
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クエリごとに整数を出力して車に戻り,クエリのセグメントの総数を表し,この数はint以内に保たれる.
Sample Input
Sample Output
Author
Windbreaker
セグメントツリーの基礎問題、セグメントツリーの問題をブラシし始め、セグメントツリーのこのようなデータ構造を理解し、ツリー構造はこのセグメントを格納する.
単点更新;主に中の木を掌握して、照会して、更新して、操作します;すべて再帰を通じて実現します;
コードは次のとおりです.
この問題は実は木の配列でもできて、線分の木よりもっと簡単です.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 45437 Accepted Submission(s): 19314
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クエリごとに整数を出力して車に戻り,クエリのセグメントの総数を表し,この数は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
セグメントツリーの基礎問題、セグメントツリーの問題をブラシし始め、セグメントツリーのこのようなデータ構造を理解し、ツリー構造はこのセグメントを格納する.
単点更新;主に中の木を掌握して、照会して、更新して、操作します;すべて再帰を通じて実現します;
コードは次のとおりです.
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50050;
struct node//
{
int l,r,val;
}t[maxn*3];
int a[maxn];
void build(int root,int l,int r)//
{
int m;
t[root].l=l;
t[root].r=r;
if(l==r)
{
t[root].val=a[l];
return ;
}
m=(l+r)/2;
build(root*2,l,m);
build(root*2+1,m+1,r);
t[root].val=t[root*2].val+t[root*2+1].val;
}
int query(int root,int l,int r)// ，
{
int m;
if(t[root].l==l && t[root].r==r) return t[root].val;
m=(t[root].l+t[root].r)/2;
if(r<=m) return query(root*2,l,r);
else if(l>m) return query(root*2+1,l,r);
else return query(root*2,l,m)+query(root*2+1,m+1,r);
}
void update(int root,int id,int num)//
{
if(t[root].l==t[root].r)
{
t[root].val+=num;//
return ;
}
else
{
t[root].val+=num;
if(id<=t[root*2].r) update(root*2,id,num);
else update(root*2+1,id,num);
}
}
int main()
{
int t,n,i,id,num;
char s[10];
int k=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
printf("Case %d:
",k++);
while(1)
{
scanf("%s",s);
if(strcmp(s,"End")==0) break;
scanf("%d%d",&id,&num);
if(strcmp(s,"Query")==0)
{
printf("%d
",query(1,id,num));
}
if(strcmp(s,"Add")==0)
{
update(1,id,num);
}
if(strcmp(s,"Sub")==0)
{
update(1,id,-num);
}
}
}
return 0;
}
この問題は実は木の配列でもできて、線分の木よりもっと簡単です.
#include <cstdio>
#include <cstring>
const int maxn=50005;
int n,a[maxn];
char s[10];
int lowbit(int i)//
{
return i&(-i);
}
void update(int i,int val)//
{
while(i<=n)
{
a[i]+=val;
i+=lowbit(i);
}
}
int sum(int i)//
{
int sum=0;
while(i>0)
{
sum+=a[i];
i-=lowbit(i);
}
return sum;
}
int main()
{
int t,i,val,k=1,x,y;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&val);
update(i,val);
}
printf("Case %d:
", k++);
while(scanf("%s",s))
{
if(s[0]=='E') break;
scanf("%d%d",&x,&y);
if(s[0]=='A') update(x, y);
else if(s[0]=='S') update(x,-y);
else
printf("%d
", sum(y)-sum(x-1));
}
}
}