树状数组练习

  • 时间:
  • 浏览:
  • 来源:互联网



目录

敌兵布阵   HDU-1166
Stars   HDU-1541
Tunnel Warfare   POJ-2892
Apple Tree   POJ-3321 未做
Mobile phones   POJ-1195 未做
Minimum Inversion Number   HDU-1394



不理解树状数组的可以看一下这两个博客
树状数组详解
夜深人静写算法(三)- 树状数组




目录

敌兵布阵   HDU-1166

题意

敌人有 NN 个工兵营地,第 ii 个工兵营地里开始时有 aia_i个人
每行有一条命令,命令有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 表示结束,这条命令在每组数据最后出现;

做法

树状数组模板题,当然线段树也可以
属于单点更新,区间查询
区间查询即 query® - query(l-1) ,这里利用的是差分的思想

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

int tr[maxn], n;

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

void update(int id, int val) {
    for(int i = id; i <= n; i += lowbit(i))
        tr[i] += val;
}

int query(int id) {
    int ans = 0;
    for(int i = id; i > 0; i -= lowbit(i))
        ans += tr[i];
    return ans;
}


int main() {
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; ++i) {
        printf("Case %d:\n", i);
        int x, y;
        scanf("%d", &n);
        for(int i = 0; i <= n; ++i) tr[i] = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            update(i, x);
        }
        char s[10];
        while(~scanf("%s", s)) {
            if(s[0] == 'E') break;
            scanf("%d%d", &x, &y);
            if(s[0] == 'Q') 
                printf("%d\n", query(y) - query(x - 1));
            else if(s[0] == 'A')
                update(x, y);
            else if(s[0] == 'S') 
                update(x, -y);
        }
    }
    return 0;
}



目录

Stars   HDU-1541

题意

每个星星有一个坐标 (xi,yi)(x_i,y_i),当有另一个星星的坐标 (xj,yj)(x_j,y_j),且 xjxi&&yjyix_j \leq x_i \&\& y_j \leq y_i 时,ii 星星的层次加 11
输入保证 yy 是升序的(也就是强行变一维)
最后询问层次 0(n1)0 \rightarrow (n-1) 的各有多少颗星星

做法

树状数组模板题,当然线段树也可以
属于单点更新,单点查询
单点查询即 query(x)query(x),因为保证 yy 是升序,那么后面的星星对当前的星星都不会有贡献
统计当前星星的层次
然后单点更新 update(x, 1)
要注意的的一个地方是,本题是多组数据(很迷,我觉得题目看着是说单组数据的亚子啊 _(:з」∠)_ )

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 5e4 + 5;

int tr[maxn], n;
int res[maxn];

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

void update(int id, int val) {
    for(int i = id; i < maxn; i += lowbit(i))
        tr[i] += val;
}

int query(int id) {
    int ans = 0;
    for(int i = id; i > 0; i -= lowbit(i))
        ans += tr[i];
    return ans;
}


int main() {
    int x, y, ans = 0;
    while(~scanf("%d", &n)) {
        memset(tr, 0, sizeof(tr));
        memset(res, 0, sizeof(res));
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &x, &y); 
            res[query(++x)] += 1;
            update(x, 1);
        }
        for(int i = 0; i < n; ++i)
            printf("%d\n", res[i]);
    }
    return 0;
}




目录

Tunnel Warfare   POJ-2892

未AC
究竟是道德的沦丧还是人性的扭曲
为何poj半夜无法登陆

题意

最初相邻村庄(编号从 1n1 \rightarrow n)之间有一条道路连接
接下来几条命令:
‘D x’: 摧毁编号为 xx 的村庄被摧毁,即相邻两个村庄到这个村庄的道路也没了
‘R’: 修复最后摧毁的那个村庄,即相邻两个村庄到这个村庄的道路也会修复
‘Q x’: 询问标号为 xx 的村庄最大连续可以互通的村庄长度

做法

看到这个下意识就想写线段树
线段树的话就是维护区间最大连续长度
然鹅,正在练习树状数组
最初可以初始化每个村庄的树状数组值为 11,一开始村庄都还在,update(x,1)update(x, 1)
那么摧毁也就只需要 update(x,1)update(x, -1)

主要在于询问部分
询问部分需要用到二分来查询,二分区间的边界,下面详细说明
query(x)query(x) 可以得到 1x1 \rightarrow x 间,所有还在的村庄的个数,也就是说,
如果询问一个区间内村庄的个数,那么当 query(r)query(l1)==rl+1query(r) - query(l - 1) == r - l + 1 时,说明这一段区间内的村庄都存在
那么为了得到包含 xx 在内的连续村庄的个数,可以二分两次,
分别找到 LidL \rightarrow id 最左边满足条件的 LL, idRid \rightarrow R 最右边满足条件的 RR
最后 RL+1R - L + 1 就是最终的答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define min(a,b)    ((a)>(b)?(b):(a))
#define max(a,b)    ((a)>(b)?(a):(b))
const int inf = 0x3f3f3f3f;
const int maxn = 5e4 + 5;

bool vis[maxn];
int tr[maxn];
int st[maxn];
int n;

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

void update(int id, int val) {
    for(int i = id; i < maxn; i += lowbit(i))
        tr[i] += val;
}

int query(int id) {
    int ans = 0;
    for(int i = id; i > 0; i -= lowbit(i))
        ans += tr[i];
    return ans;
}

void solve(int id) {
    if(!vis[id]) {
        puts("0");
        return ;
    }
    int L, R; // 最有边界
    int l = 1, r = id, mid, x = query(id);
    while(l <= r) {
        mid = (l + r) >> 1;
        if(x - query(mid - 1) >= id - mid + 1)
            L = mid, r = mid - 1;
        else 
            l = mid + 1;
    }
    l = id, r = n, x = query(id - 1);
    while(l <= r) {
        mid = (l + r) >> 1;
        if(query(mid) - x >= mid - id + 1)
            R = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d\n", R - L + 1);
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    memset(tr, 0, sizeof(tr));
    memset(vis, true, sizeof(vis));
    for(int i = 1; i <= n; ++i) update(i, 1);
    char s[2]; int id, top = 0;
    while(m--) {
        scanf("%s", s);
        if(s[0] == 'R' && top) {
            id = st[top--], vis[id] = true;
            update(id, 1);
        }else{
            scanf("%d", &id);
            if(s[0] == 'D') {
                st[++top] = id, vis[id] = false;
                update(id, -1);
            }else{
                solve(id);
            }
        }
    } 
    return 0;
}



目录

Apple Tree   POJ-3321

题意

做法

代码




目录

Mobile phones   POJ-1195

题意

做法

代码




目录

Minimum Inversion Number   HDU-1394

题意

做法

代码




目录

1  

题意

做法

代码


本文链接http://element-ui.cn/news/show-340071.aspx