HDU-1166 敌兵布阵

2016年04月14日 |

acm

| acm 线段树

题目：

敌兵布阵
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 69427 Accepted Submission(s): 29197


Problem Description
C 国的死对头 A 国这段时间正在进行军事演习，所以 C 国间谍头子 Derek 和他手下 Tidy 又开始忙乎了。A 国在海岸线沿直线布置了 N 个工兵营地,Derek 和 Tidy 的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数 C 国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过 C 国的监视。
中央情报局要研究敌人究竟演习什么战术,所以 Tidy 要随时向 Derek 汇报某一段连续的工兵营地一共有多少人,例如 Derek 问:“Tidy,马上汇报第 3 个营地到第 10 个营地共有多少人!”Tidy 就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而 Derek 每次询问的段都不一样，所以 Tidy 不得不每次都一个一个营地的去数，很快就精疲力尽了，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）。
接下来每行有一条命令，命令有 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 询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在 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

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
#include <numeric>
#include <string>

using namespace std;

int tree[900000];
int L[50010];

int insert(int now, int beg, int end)
{
    if (end - beg <= 1)
    {
        tree[now] = L[beg];
        return tree[now];
    }
    int mid = beg + (end - beg) / 2;
    tree[now] = insert(now * 2, beg, mid)
        + insert(now * 2 + 1, mid, end);
    return tree[now];
}

void add(int now, int beg, int end, int i, int x)
{//i>=0
    tree[now] += x;
    if (end-beg <= 1)
        return;
    int mid = beg + (end - beg) / 2;
    if (mid > i)
        add(now * 2, beg, mid, i, x);
    else
        add(now * 2 + 1, mid, end, i, x);
}

int sumt(int now, int beg, int end, int i, int j)
{
    if (beg >= j || end <= i)
        return 0;
    if (beg >= i && end <= j)
        return tree[now];
    int mid = beg + (end - beg) / 2;
    return sumt(now * 2, beg, mid, i, j)
        + sumt(now * 2 + 1, mid, end, i, j);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, T;
    cin >> T;
    for (int i = 0;i < T;++i)
    {
        cout << "Case " << i+1 << ":\n";
        cin >> N;
        for (int i = 0;i < N;++i)
            cin >> L[i];
        insert(1, 0, N);
        string S;
        while (cin >> S&&S != "End")
        {
            int i, j;
            cin >> i >> j;
            --i;
            if (S == "Add")
            {
                add(1, 0, N, i, j);
            }
            else if (S == "Sub")
            {
                add(1, 0, N, i, -j);
            }
            else
            {
                cout << sumt(1, 0, N, i, j) << endl;
            }
        }
    }
}

解析：

刚学了线段树就拿来练手了:trollface:

这里总结一下线段树的模板。

建树

int insert(int now, int beg, int end)
{
    if (end - beg <= 1)
    {
        tree[now] = L[beg];
        return tree[now];
    }
    int mid = beg + (end - beg) / 2;
    tree[now] = insert(now * 2, beg, mid)
        + insert(now * 2 + 1, mid, end);
    return tree[now];
}

虽然我在代码里面写的是 insert，但其实是 build 过程。

形参：

• now: 树中节点的指针
• beg: 这个节点表示的区间的开头的索引
• end: 这个节点表示的区间的结尾的下一个元素索引

注意本代码的所有 end 都是超尾，和 stl 的 end 类似。

全局变量：

• tree[]: 二叉树
• L[]: 要求和的区间中各个元素的值

树中节点的值表示此区间的和，如果是 RMQ 问题的题的话，值就是区间中的最大值。 这个函数找到 beg 和 end 的中点，将区间分成两部分，然后把这两部分交给左右子 节点递归解决。如果当前区间只剩下了一个值，就结束递归，节点的值就是区间中这个 元素的值。

更新

void add(int now, int beg, int end, int i, int x)
{//i>=0
    tree[now] += x;
    if (end-beg <= 1)
        return;
    int mid = beg + (end - beg) / 2;
    if (mid > i)
        add(now * 2, beg, mid, i, x);
    else
        add(now * 2 + 1, mid, end, i, x);
}

形参：

• now beg end: 与上文一样
• i: 区间中要更新的值的索引
• x: 要增加（或者减少）的值

因为在线段树中上一个节点存储了两个子节点的和，而要更新的那个元素必然属于两个 子节点之一。因此我们在更新了当前节点之后需要判断要更改的元素属于哪个子节点， 并且递归处理。如果是 RMQ 问题的题的话，我们需要在当前区间只有一个值时更新 区间，然后在子节点的递归结束后再根据两个子节点的值来判断当前的节点的值。

查询

int sumt(int now, int beg, int end, int i, int j)
{
    if (beg >= j || end <= i)
        return 0;
    if (beg >= i && end <= j)
        return tree[now];
    int mid = beg + (end - beg) / 2;
    return sumt(now * 2, beg, mid, i, j)
        + sumt(now * 2 + 1, mid, end, i, j);
}

形参：

• now beg end: 同上
• i j: 要查询的区间的开头和结尾。

找到树中恰好可以拼出 [i,j) 区间的区间。需要在左右子树中分别寻找可以拼出指定的 区间的部分。由于节点可以表示的最小的区间长度为 1，所以在 log n 步之后一定可以 正好拼出这个区间来。函数返回的是（当前节点表示的）beg 到 end 区间内可以匹配 i 到 j 区间的所有值的和。至于 RMQ 问题，只要把 return 语句中的 + 改成 max 函数就可以了。