ACM 之 D - 敌兵布阵

Description

Lily 特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗？

Input

第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N(N<=50000)，表示Lily有N盆花。接下来有N个正整数，第i个正整数ai表示第i盆花的初始美观值(1<=ai<=50)。
接下来每行有一条命令，命令有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，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条

Output

对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

Sample Input

1
9
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End

Sample Output

Case 1:
13
30
50

理解

这一题可以用线段树也可以用树状数组,我用的线段树.

代码部分

#include<iostream>
#include<cstdio>
using namespace std;
int sum;
struct 
{
    int l,r,m;
}n[50001*4];
int a[50001];
void build(int i,int j,int k)
{
    n[i].l=j;n[i].r=k;
    if(j==k)
    {
        n[i].m=a[j];
        return;
    }
    int m=(n[i].l+n[i].r)/2;
    build(i*2,j,m);build(i*2+1,m+1,k);
    n[i].m=n[2*i].m+n[2*i+1].m;
}
void Q(int i,int j,int k)
{
    if(n[i].r<j||n[i].l>k) return;
    if(n[i].l>=j&&n[i].r<=k)
    {
        sum+=n[i].m; return;
    }
    Q(i*2,j,k);Q(i*2+1,j,k);
}
void A(int i,int j,int k)
{
    if(n[i].l==n[i].r&&n[i].l==j)
    {
        n[i].m+=k;
        return;
    }
    if(j<=n[i*2].r)
        A(i*2,j,k);
    else
        A(i*2+1,j,k);
    n[i].m=n[2*i].m+n[2*i+1].m;//update
}
int main()
{
    int nn,mm;char c[6];
    scanf("%d",&nn);
    for(int i=1;i<=nn;++i)
    {
        scanf("%d",&mm);
        for(int j=1;j<=mm;j++)
            {scanf("%d",&a[j]);}
        build(1,1,mm);
        int x,y;
        cout<<"Case "<<i<<":\n";
        while(scanf("%s",c)&&c[0]!='E')
        {
            scanf("%d %d",&x,&y);
            if(c[0]=='Q')
            {
                sum=0;
                Q(1,x,y);
                printf("%d\n",sum);continue;
            }
            if(c[0]=='A')
            {
                A(1,x,y);continue;
            }
            if(c[0]=='S')
            {
                A(1,x,-y);continue;
            }
            if(c[0]=='E')
            {
                break;
            }
        }
    }
    return 0;
}

意见反馈 || 任何建议

联系我(新浪)
邮箱：qianlizhihao@gmail.com