HDU 1166 敵兵布陣 (線段樹點更新模闆題)

題目連結

HDU1166

題目大意

有N個(N<=50000)工兵營地，有N個工兵營地開始時有ai個人(1<=ai<=50)。有以下四種指令：

(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 表示結束，這條指令在每組資料最後出現;

每組資料最多有40000條指令

分析

寫線段樹的第一道題，點更新模闆題。

注意較多資料若都用輸入輸出流，會TLE。解決方法：關閉和stdio同步，即調用ios::sync_with_stdio(false);

代碼

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int MAXN=;
int a[MAXN],ans[*MAXN];

void PushUp(int rt)
{
    ans[rt]=ans[rt<<]+ans[rt<<|];
}
void Build(int l,int r,int rt)
{
    if (l==r)
    {
        ans[rt]=a[l];
        return;
    }
    int mid=(l+r)>>;
    Build(l,mid,rt<<);
    Build(mid+,r,rt<<|);
    PushUp(rt);
}
void Add(int L,int C,int l,int r,int rt)
{
    if (l==r)
    {
        ans[rt]+=C;
        return;
    }
    int mid=(l+r)>>;
    if (L<=mid)
        Add(L,C,l,mid,rt<<);
    else
        Add(L,C,mid+,r,rt<<|);
    PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
        return ans[rt];
    int mid=(l+r)>>;
    int ANS=;
    if (L<=mid)
        ANS+=Query(L,R,l,mid,rt<<);
    if (R>mid)
        ANS+=Query(L,R,mid+,r,rt<<|);
    return ANS;
}
int main()
{
    ios::sync_with_stdio(false); ///加速流輸入輸出，否則會逾時
    int t,n,i,x,y,cnt=;
    string op;
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (i=;i<=n;i++)
            cin>>a[i];
        memset(ans,,sizeof(ans));
        Build(,n,);
        cout<<"Case "<<++cnt<<":"<<endl;
        while ()
        {
            cin>>op;
            if (op=="End") break;
            cin>>x>>y;
            if (op=="Add") Add(x,y,,n,);
            if (op=="Sub") Add(x,-y,,n,);
            if (op=="Query") cout<<Query(x,y,,n,)<<endl;
        }
    }
    return ;
}