HDU 1166 敵兵布陣（分塊寫法）

老是鞭屍這道題，我也挺不好意思的，但是沒辦法，練手還是挺好的

​​敵兵布陣​​

分塊做法題解：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
//分塊單點修改
#define ll long long
const ll maxn=1e5+5;
ll n,pos[maxn];//塊
ll l[maxn],r[maxn];//左右區間
ll sum[maxn],a[maxn];
void modify(ll poi,ll w)//單點修改
{
    ll blk=pos[poi];
    a[poi]+=w;
    sum[blk]+=w;
}
ll query(ll lx,ll rx)
{
    ll blk=pos[lx];
    ll blc=pos[rx];
    ll res=0;
    if(blk==blc)
    {
        for(ll i=lx;i<=rx;i++)
        {
            res+=a[i];
        }
    }
    else
    {
        for(ll i=lx;i<=r[blk];i++)
        {
            res+=a[i];
        }
        for(ll i=blk+1;i<=blc-1;i++)
        {
            res+=sum[i];
        }
        for(ll i=l[blc];i<=rx;i++)
        {
            res+=a[i];
        }
    }
    return res;
}
int main()
{
    ll t,d=0;
    scanf("%lld",&t);
    while(t--)
    {
        memset(sum,0,sizeof(sum));
        scanf("%lld",&n);
        ll dis=sqrt(n);
        ll num=ceil(n*1.0/dis);
        for(ll i=1;i<=num;i++)//處理塊和區間
        {
            l[i]=(i-1)*dis+1;
            r[i]=i*dis;
//            pos[i]=((i-1)/dis)+1;
        }
        r[num]=n;
        for(ll i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            pos[i]=((i-1)/dis)+1;
            sum[pos[i]]+=a[i];
        }
       char s[10];
       printf("Case %lld:\n",++d);
       while(scanf("%s",s)&&s[0]!='E')
       {
           ll l,r,w,poi;
           if(s[0]=='Q')
           {
               scanf("%lld %lld",&l,&r);
               printf("%lld\n",query(l,r));
           }
           else if(s[0]=='A')
           {
                scanf("%lld %lld",&poi,&w);
                modify(poi,w);
           }
           else
           {
                scanf("%lld %lld",&poi,&w);
                modify(poi,-w);
           }
       }
    }
}