HDU 1166敵兵布陣(線段樹)

HDU 1166敵兵布陣(線段樹)敵兵布陣
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 52962 Accepted Submission(s): 22180
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は「自分で計算してみろ.これは本当に疲れた仕事だ.私を首にするのが憎い」と思った.仕方なく、Tidyはコンピューター専門家のWindbreakerに電話して助けを求めるしかなかった.Windbreakerは言った.「デブだ.普段acmの問題をたくさん作って、計算書をたくさん読むように言ったが、今は苦果を味わっただろう.」Tidyは言った.「私は間違っている」.しかし、Windbreakerはもう電話を切った.Tidyは悩んでいます.これで彼は本当に崩壊します.賢い読者、プログラムを書いて彼にこの仕事を完成させることができますか.しかし、プログラムの効率が足りなければ、TidyはDerekに叱られます.
Inputの最初の行は整数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
标题:典型的な線分樹問題は、まず各キャンプの兵士数を保存し、その後更新し、区間と照会する.コードは次のとおりです.

//By 0o0Endhiran
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lid (id<<1)
#define rid ((id<<1)+1)
#define ll long long
using namespace std;
//const int inf=0x3f3f3f3f;
const int N=5e4+5;
ll pep[N];
struct tree{
    ll l,r;
    ll sum,m;
}tr[4*N];
void push_up(ll id)
{
    tr[id].sum=tr[lid].sum+tr[rid].sum;
}
void build(ll id,ll l,ll r)//  
{
    tr[id].l=l;tr[id].r=r;
    if(l==r)
    {
        tr[id].sum=tr[id].m=pep[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    push_up(id);
}
void update(ll id,ll x,ll v)//  
{
    if(tr[id].l==tr[id].r)
    {
        tr[id].sum+=v;
        tr[id].m+=v;
        return;
    }
    ll mid=(tr[id].l+tr[id].r)>>1;
    update(x<=mid? lid:rid,x,v);
    push_up(id);
}
int query(ll id,ll l,ll r)//     
{
    if(tr[id].l==l&&tr[id].r==r)
        return tr[id].sum;
    ll mid=(tr[id].l+tr[id].r)>>1;
    if(r<=mid)
        return query(lid,l,r);
    if(l>mid)
        return query(rid,l,r);
    return query(lid,l,mid)+query(rid,mid+1,r);
}

int main()
{
    ll t,n,k=1,kk=1;
    scanf("%I64d",&t);
    while(t--)
    {
        scanf("%I64d",&n);
        for(ll i=1;i<=n;i++)
        scanf("%d",&pep[i]);
        build(1,1,n);
        ll i,j,flag=1,sm=0;
        char s[7];
        while(1)
        {
            scanf("%s",s);
            switch (s[0])
            {
                case 'A':scanf("%I64d%I64d",&i,&j);update(1,i,j);break;
                case 'S':scanf("%I64d%I64d",&i,&j);update(1,i,-j);break;
                case 'Q':scanf("%I64d%I64d",&i,&j);sm=query(1,i,j);
                        if(kk) printf("Case %d:
",k);kk=0;
                        printf("%I64d
",sm);
                        break;
                        default:flag=0;break;
            }
            if(flag==0) break;
        }
        k++;
        kk=1;

    }
    return 0;
}