线段树水题几枚

coolsooner

浏览: 1310993 次

最近访客更多访客>>

lwvermds

神乎其技1412

枫叶灬

jacket233

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1948)

社区版块

存档分类

2012-02 ( 3)
2012-01 ( 250)
2011-12 ( 113)
更多存档...

最近接触了一下线段树，按理来说这个半年前就该看了，实际上自己却总想刷水题而躲避难题，不过，该来的还是要来的，既然选择了数据结构，就让各种树来的猛烈些吧。

以下为最初级的线段树，只更新点，没有delay操作

1.HDU 1166 敌兵布阵

这道题用线段树或者树状数组都可以做，HDU上的数据貌似很弱，模拟竟然都能过

首先是线段树版，线段树所带信息为当前区间所有点的值的和

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int a[MAXN];
struct node
{
    int left, right, mid;
    int sum;
}tree[4 * MAXN];
int ans;
void up(int C)
{
    tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = (s + e) / 2;
    tree[C].sum = 0;
    if(s == e)
    {
        tree[C].sum = a[s];
        return;
    }
    make_tree(s, tree[C].mid, L(C));
    make_tree(tree[C].mid + 1, e, R(C));
    up(C);
}
void update(int C, int p, int v)
{
    if(tree[C].left == p && tree[C].right == p)
    {
        tree[C].sum += v;
        return;
    }
    if(p <= tree[C].mid)
    update(L(C), p, v);
    else update(R(C), p, v);
    up(C);
}
void search(int s, int e, int C)
{
    if(s <= tree[C].left && tree[C].right <= e)
    {
        ans += tree[C].sum;
        return;
    }
    if(tree[C].mid >= e) search(s, e, L(C));
    else if(tree[C].mid < s) search(s, e, R(C));
    else
    {
        search(s, tree[C].mid, L(C));
        search(tree[C].mid + 1, e, R(C));
    }
}
int main()
{
#ifdef LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    char s[20];
    int t, n, i, cas = 0, x, y;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        make_tree(1, n, 1);
        printf("Case %d:\n", ++cas);
        while(scanf("%s", s) != EOF)
        {
            if(s[0] == 'E') break;
            else if(s[0] == 'Q')
            {
                ans = 0;
                scanf("%d%d", &x, &y);
                search(x, y, 1);
                printf("%d\n", ans);
            }
            else if(s[0] == 'A')
            {
                scanf("%d%d", &x, &y);
                update(1, x, y);
            }
            else if(s[0] == 'S')
            {
                scanf("%d%d", &x, &y);
                update(1, x, -y);
            }
        }
    }
    return 0;
}

然后是树状数组版

/*
ID: sdj22251
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
using namespace std;
int a[50005], n, b[50005];
int lowbit(int x)
{
    return x & -x;
}
void modify(int x)
{
    for(int i = x; i <= n; i += lowbit(i))
    a[i] += b[x];
}
void modify2(int x, int y)
{
    for(int i = x; i <= n; i += lowbit(i))
    a[i] += y;
}
int sum(int x)
{
    int ans = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
    ans += a[i];
    return ans;
}
int main()
{
#ifdef LOCAL
    freopen("lamps.in","r",stdin);
    freopen("lamps.out","w",stdout);
#endif
    int t, cas = 0, i, x, y;
    char s[15];
    scanf("%d", &t);
    while(t--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &b[i]);
            modify(i);
        }
        printf("Case %d:\n", ++cas);
        while(scanf("%s", s) != EOF)
        {
            if(s[0] == 'E')
            break;
            else if(s[0] == 'Q')
            {
                scanf("%d%d", &x, &y);
                printf("%d\n", sum(y) - sum(x - 1));
            }
            else if(s[0] == 'A')
            {
                scanf("%d%d", &x, &y);
                modify2(x, y);
            }
            else if(s[0] == 'S')
            {
                scanf("%d%d", &x, &y);
                modify2(x, -y);
            }
        }
    }
    return 0;
}

2.HDU 1754 I Hate It

同样是点更新，外加up操作即可，线段树所带信息是当前区间的最大值

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 200005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct node
{
    int left, right, mid;
    int l, mx;
} tree[4 * MAXN];
int ans, num[MAXN];
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = ((s + e) >> 1);
    tree[C].l = tree[C].right - tree[C].left + 1;
    tree[C].mx = 0;
    if(s == e) {tree[C].mx = num[s]; return;}
    make_tree(s, tree[C].mid, (C << 1));
    make_tree(tree[C].mid + 1, e, (C << 1) | 1);
    tree[C].mx = max(tree[C << 1].mx, tree[(C << 1) + 1].mx);
}
void update(int s, int v, int C)
{
    if(tree[C].left == s && tree[C].right == s)
    {
        tree[C].mx = v;
        return;
    }
    if(s > tree[C].mid)
    {
        update(s, v, (C << 1) | 1);
    }
    else update(s, v, C << 1);
    tree[C].mx = max(tree[C << 1].mx, tree[(C << 1) + 1].mx);
}
void search(int s, int e, int C)
{
    if(tree[C].left >= s && tree[C].right <= e)
    {
        if(tree[C].mx > ans)
        ans = tree[C].mx;
        return;
    }
    if(s > tree[C].mid)
    {
        search(s, e, (C << 1) | 1);
    }
    else if(e <= tree[C].mid)
    {
        search(s, e, C << 1);
    }
    else
    {
        search(s, tree[C].mid, C << 1);
        search(tree[C].mid + 1, e, (C << 1) | 1);
    }
}
int main()
{
#ifdef LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    int n, m, i, x, y;
    char s[5];
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(i = 1; i <= n; i++)
        scanf("%d", &num[i]);
        make_tree(1, n, 1);
        while(m--)
        {
            scanf("%s %d %d", s, &x, &y);
            if(s[0] == 'Q')
            {
                ans = 0;
                search(x, y, 1);
                printf("%d\n", ans);
            }
            else
            {
                update(x, y, 1);
            }
        }
    }
    return 0;
}

3.HDU 1394Minimum Inversion Number

题意就是求逆序数，然后每次把当前序列的第一个数放到序列末尾求一次逆序数，总共n次，求其中最小的逆序数

其实求出最初的逆序数就行了，因为随后的逆序数能推导出来，总共n个数，0到n-1都有，比a[i]小的数是a[i] 个，大的数是n-1-a[i]个。

求逆序数时所用的方法是先查询再更新，查询的是已经存在的比自己大的数的个数，而线段树中所带的信息就是这一区间有几个数存在。

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 50005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
    int left, right, mid;
    int sum;
}tree[4 * MAXN];
int tmp, a[MAXN];
void up(int C)
{
    tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = (s + e) / 2;
    tree[C].sum = 0;
    if(s == e) return;
    make_tree(s, tree[C].mid, L(C));
    make_tree(tree[C].mid + 1, e, R(C));
}
void search(int s, int e, int C)
{
    if(s <= tree[C].left && e >= tree[C].right)
    {
        tmp += tree[C].sum;
        return;
    }
    if(tree[C].mid >= e) search(s, e, L(C));
    else if(tree[C].mid < s) search(s, e, R(C));
    else
    {
        search(s, tree[C].mid, L(C));
        search(tree[C].mid + 1, e, R(C));
    }
}
void update(int p, int s, int e, int C)
{
    if(s == e && s == p) {tree[C].sum++; return;}
    if(tree[C].mid >= p) update(p, s, tree[C].mid, L(C));
    else update(p, tree[C].mid + 1, e, R(C));
    up(C);
}
int main()
{
#ifdef LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    int n, i;
    while(scanf("%d", &n) != EOF)
    {
        make_tree(0, n - 1, 1);
        int sum = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            tmp = 0;
            search(a[i], n - 1, 1);
            sum += tmp;
            update(a[i], 0, n - 1, 1);
        }
        int ret = sum;
        for(i = 0; i < n; i++)
        {
            sum = sum + n - a[i] - a[i] - 1;
            ret = min(ret, sum);
        }
        printf("%d\n", ret);
    }
    return 0;
}

4.HDU 2795 Billboard

题意是给出一个高为h宽为w的木板，然后往上贴高度为1，宽度wi的纸条，每次帖优先找到最高的帖，高度相同的要尽量往左边贴。

其实把板子横过来的话就好理解了，横坐标是h，然后尽量往左边贴条子

数据范围貌似挺大的，其实也不大，因为n只有20万，也就是说线段树的范围1到20万够用了

然后线段树的附加信息是这个区间内每一段h的剩余空间的最大值，查询的时候最终查到叶子节点，减掉消耗的长度就行了。

然后做了这几个初级题目后，发现查询的时候，一种是需要自定义查询范围的，还有一种是不需要自定义查询范围，直接从祖先开始查的，查询函数的参数的个数自然就不同了

分享到：

POJ 2828 Buy Tickets | 新手浅谈CSS 之突破局限小技巧！

2011-10-15 21:57
浏览 985
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论