avatar
fireworks99
keep hungry keep foolish

HDU 1166 敌兵布阵

Description

区间1~n初始有一些人，某个区间可以增加人数、减少人数、询问人数。

LINK

线段树

1.N * 4 + 1的空间（有N * 2节省空间的方法）

2.用 位运算符时注意其优先级低，用 (num << 1) + 1 或 num << 1 | 1

3.更新末操作：a[num].val = a[num << 1].val + a[(num << 1) + 1].val;

4.单点更新、单点查询、区间查询都可套用模板，但区间更新分①普通更新②lazy标记

Code of ordinary Segment tree

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50005;

map<string, int> mp;

struct node
{
    int L, R, val;
}a[(N << 2) + 1];

void init(int num, int l, int r)///r = 6,r = 10数组并没有充分利用
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 0;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);///mid被分到左孩子
    init((num << 1) + 1, mid + 1, r);///忽略了位运算符优先级低
}

///设flag为1对应增加,为0对应减少
void update(int num, int l, int r, bool flag, int tot)
{
    if(a[num].L == l && a[num].R == r)///找到区间，去做任务
    {
        if(flag)
            a[num].val += tot;
        else
            a[num].val -= tot;
        return ;///这里的return都能忘？！
    }

    if(a[num].L == a[num].R)///未找到区间，返回上一级，程序向下运行
        return ;

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r, flag, tot);
    else if(mid < l)///此处无等号(mid被分到左孩子)
        update((num << 1) + 1, l, r, flag, tot);
    else
    {
        update(num << 1, l, mid, flag, tot);
        update((num << 1) + 1, mid + 1, r, flag, tot);
    }

    a[num].val = a[num << 1].val + a[(num << 1) + 1].val;
}

int query(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)///找到区间，去做任务
            return a[num].val;

    if(a[num].L == a[num].R)
        return 0;

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        return query(num << 1, l, r);
    else if(mid < l)
        return query((num << 1) + 1, l, r);
    else
        return (query(num << 1, l, mid) + query((num << 1) + 1, mid + 1, r));
}

int main()
{
    int t;
    string s[4];
    s[0] = "End";///字符串对应时，尽量控制只比较第一个字符
    s[1] = "Add";
    s[2] = "Sub";
    s[3] = "Query";
    for(int i = 0; i < 4; ++i)
        mp[ s[i] ] = i;
    scanf("%d", &t);
    int tot = t;
    while(t--)
    {
        int n, tem;
        scanf("%d", &n);
        init(1, 1, n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(1, i, i, 1, tem);
        }
        printf("Case %d:\n", tot - t);
        string ch;
        while(cin >> ch)
        {
            bool flag = 0;
            int x, y;
            switch(mp[ch])
            {
            case 0:
                flag = 1;
                break;
            case 1:
                scanf("%d%d", &x, &y);
                update(1, x, x, 1, y);
                break;
            case 2:
                scanf("%d%d", &x, &y);
                update(1, x, x, 0, y);
                break;
            case 3:
                scanf("%d%d", &x, &y);
                cout << query(1, x, y) << '\n';
                break;
            }
            if(flag)
            break;
        }

    }
    return 0;
}

Code of Improved Segment tree(by lazy array)

1.区间结构体中除L、R、val，増一个lazy

2.init时lazy赋0

3.更新时，若当前区间是目标区间，更新val顺便，更新lazy

若当前区间不是目标区间，数据下传：down（传完记得lazy清零）

#include <map>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50005;

map<string, int> mp;

struct node
{
    int L, R, val, lazy;
} a[N << 2 | 1];

void down(int x)///将x区间数据下传
{
    ///子区间继承父区间的lazy以便下传
    ///更新子区间的val
    a[x << 1].lazy += a[x].lazy;
    a[x << 1].val += a[x].lazy;
    a[x << 1 | 1].lazy += a[x].lazy;
    a[x << 1 | 1].val += a[x].lazy;
    a[x].lazy = 0;///下传完了lazy清零
}

void init(int num, int l, int r)///r = 6,r = 10数组并没有充分利用
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = 0;
    a[num].lazy = 0;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);///mid被分到左孩子
    init(num << 1 | 1, mid + 1, r);///忽略了位运算符优先级低
}

///设flag为1对应增加,为0对应减少
void update(int num, int l, int r, bool flag, int tot)
{
    if(a[num].L == l && a[num].R == r)///找到区间，去做任务
    {
        if(flag)
        {
            a[num].val += tot;
            a[num].lazy += tot;
        }
        else
        {
            a[num].val -= tot;
            a[num].lazy -= tot;
        }
        return ;
    }

    if(a[num].L == a[num].R)///未找到区间，返回上一级，程序向下运行
        return ;

    down(num);///此区间非目标区间，数据下传

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        update(num << 1, l, r, flag, tot);
    else if(mid < l)///此处无等号(mid被分到左孩子)
        update(num << 1 | 1, l, r, flag, tot);
    else
    {
        update(num << 1, l, mid, flag, tot);
        update(num << 1 | 1, mid + 1, r, flag, tot);
    }

    a[num].val = a[num << 1].val + a[num << 1 | 1].val;
}

int query(int num, int l, int r)
{
    if(a[num].L == l && a[num].R == r)///找到区间，去做任务
        return a[num].val;

    if(a[num].L == a[num].R)
        return 0;

    int mid = (a[num].L + a[num].R) >> 1;
    if(mid >= r)
        return query(num << 1, l, r);
    else if(mid < l)
        return query(num << 1 | 1, l, r);
    else
        return (query(num << 1, l, mid) + query(num << 1 | 1, mid + 1, r));
}

int main()
{
    int t;
    string s[4];
    s[0] = "End";///字符串对应时，尽量控制只比较第一个字符
    s[1] = "Add";
    s[2] = "Sub";
    s[3] = "Query";
    for(int i = 0; i < 4; ++i)
        mp[ s[i] ] = i;
    scanf("%d", &t);
    int tot = t;
    while(t--)
    {
        int n, tem;
        scanf("%d", &n);
        init(1, 1, n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(1, i, i, 1, tem);
        }
        printf("Case %d:\n", tot - t);
        string ch;
        while(cin >> ch)
        {
            bool flag = 0;
            int x, y;
            switch(mp[ch])
            {
            case 0:
                flag = 1;
                break;
            case 1:
                scanf("%d%d", &x, &y);
                update(1, x, x, 1, y);
                break;
            case 2:
                scanf("%d%d", &x, &y);
                update(1, x, x, 0, y);
                break;
            case 3:
                scanf("%d%d", &x, &y);
                cout << query(1, x, y) << '\n';
                break;
            }
            if(flag)
                break;
        }

    }
    return 0;
}

Try to save time and memory

1.张昆玮线段树：循环代替递归 张昆玮线段树

2.N * 2空间：空间节省

树状数组

三个函数：lowbit、单点更新、区间查询

Code of Binary Index Tree

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 50005;

map<string, int> mp;

int n;///区间上限
int tree[N];///树状数组C[N]
///原始数组A[N]假设存在

int lowbit(int x)
{
    return x & (-x);
}

///单点更新
void update(int x, int y)///修改A[x]对应相关C[]的更新
{
    for(int i = x; i <= n; i += lowbit(i))///要求n为全局变量
        tree[i] += y;
}

///区间查询
int get_sum(int x)///求A[]前x项的和
{
    int ans = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        ans += tree[i];
    return ans;
}

int main()
{
    int t;
    string s[4];
    s[0] = "End";///字符串对应时，尽量控制只比较第一个字符
    s[1] = "Add";
    s[2] = "Sub";
    s[3] = "Query";
    for(int i = 0; i < 4; ++i)
        mp[ s[i] ] = i;
    scanf("%d", &t);
    int tot = t;
    while(t--)
    {
        int tem;
        scanf("%d", &n);
        memset(tree, 0, sizeof(tree));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &tem);
            update(i, tem);
        }

        printf("Case %d:\n", tot - t);
        string ch;
        while(cin >> ch)
        {
            bool flag = 0;
            int x, y;
            switch(mp[ch])
            {
            case 0:
                flag = 1;
                break;
            case 1:
                scanf("%d%d", &x, &y);
                update(x, y);
                break;
            case 2:
                scanf("%d%d", &x, &y);
                update(x, -y);
                break;
            case 3:
                scanf("%d%d", &x, &y);///注意区间保留x
                cout << get_sum(y) - get_sum(x - 1) << '\n';
                break;
            }
            if(flag)
                break;
        }

    }
    return 0;
}
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy