hdu-1166 - mfcheer

http://acm.hdu.edu.cn/showproblem.php?pid=1166

线段树点操作

代码风格更新后：

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>

#define Mid(a,b) ( a+((b-a)>>1))
#define ll(x) (x<<1)
#define rr(x) (x<<1|1)

const int N = 50010;

using namespace std;

int t,n;

int a[N];

struct node
{
    int left;
    int right;
    int sum;
    int mid() { return Mid(left, right); }
};

struct segtree
{
    node tree[N * 4];

    void buildtree(int left,int right,int ind)
    {
        tree[ind].left = left;
        tree[ind].right = right;
        tree[ind].sum = 0;

        if (left == right)
            tree[ind].sum = a[left];
        else
        {
            int mid = tree[ind].mid();

            buildtree(left,mid,ll(ind));
            buildtree(mid+1,right,rr(ind));
            tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
        }
    }

    void update(int pos,int ind,int val)
    {
        if (tree[ind].left == tree[ind].right) tree[ind].sum += val;
        else
        {
            int mid = tree[ind].mid();

            if (pos <= mid)
                update(pos,ll(ind),val);
            else
                update(pos,rr(ind),val);
            tree[ind].sum = tree[ll(ind)].sum + tree[rr(ind)].sum;
        }
    }

    int query(int st ,int ed,int ind)
    {
        int left = tree[ind].left;
        int right = tree[ind].right;

        if (st <= left && right <= ed)
            return tree[ind].sum;

        else
        {
            int mid = tree[ind].mid();
            int sum1 = 0;
            int sum2 = 0;
            if (st <= mid)
                sum1 = query(st,ed,ll(ind));
            if (ed > mid)
                sum2 = query(st,ed,rr(ind));

            return sum1 + sum2;
        }
    }
}seg;

int main()
{
    scanf("%d",&t);
    int cases = 1;
    while (t--)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
        }

        seg.buildtree(1, n, 1);

        cout << "Case " << cases++ << ":" << endl;
        char opr[20];
        while (1)
        {
            scanf("%s",opr);
            int c, d;
            if (!strcmp(opr, "End"))
                break;
            scanf("%d %d",&c,&d);

            if (!strcmp(opr, "Add"))
            {
                seg.update(c, 1, d);
            }
            else if (!strcmp(opr, "Sub"))
            {
                seg.update(c, 1, -d);
            }
            else if (!strcmp(opr, "Query"))
            {
                printf("%d\n", seg.query(c, d, 1));
            }
        }
    }
    return 0;
}

之前

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <sstream>
#include <time.h>
#include <utility> 
#include <malloc.h> 

using namespace std;

struct node
{
    int left ;
    int right;
    int sum;
}b[5001000];

int a[5000010];

void build(int left ,int right ,int i)
{
    int mid;
    b[i].left =left;
    b[i].right =right ;
    if (left == right )
    {
        b[i].sum=a[left];
        return ;
    }

    mid = (left + right )/2;
    build(left ,mid,2*i);
    build( mid+1,right ,2*i+1);
    b[i].sum=b[i*2].sum+b[i*2+1].sum;
}

void add (int id,int num,int i)//add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）</span>
{
    if(b[i].left == b[i].right )
    {
        b[i].sum += num;
        return ;
    }
    else 
    {
        b[i].sum=b[i].sum+num;
        if (id<= b[i*2].right )
            add (id,num,i*2);
        else
            add    (id,num,i*2+1);
    }
}

int query (int left,int right ,int i)//query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;</span>
{
    int mid;
    if (b[i].right  == right && b[i].left ==left )
    return b[i].sum ;

    mid=(b[i].left +b[i].right )/2;    
    if (right <= mid)
        return query (left ,right,2*i);
    else if (left > mid)
        return query (left ,right,2*i+1);
    else
        return query (left ,mid,2*i)+query (mid+1 ,right,2*i+1);
}

int main()
{
    int t;
    int l=1;
    scanf ("%d",&t);
    while (t--)
    {
        int n;
        scanf ("%d",&n);
        for (int i=1;i<=n;i++)
            scanf ("%d",&a[i]);

        build(1,n,1);

        char bb[100];
        int c,d;

        printf("Case %d:\n",l++);

        while (scanf ("%s",bb)  && strcmp (bb,"End"))
        {
            scanf ("%d%d",&c,&d);
            if(!strcmp(bb,"Add"))
            {
                add(c,d,1);
            }
            else if(!strcmp(bb,"Sub"))
            {
                add(c,-d,1);
            }
            else if(!strcmp(bb,"Query"))
            {
                printf("%d\n",query (c,d,1));
            }
        }
    }
    return 0;
}