数据结构 (习题): 树状数组相关

缺乏、安全感 2022-02-04 07:43 257阅读 0赞

### 树状数组习题 ###

*  PKU 2352
 *   *  思路
     *  代码
 *  PKU 2481
 *   *  代码
 *  POJ 3067
 *   *  思路
     *  代码

# PKU 2352 #

[链接在这里][Link 1].  
题目大意: 一个点的 order 是不包括它在内的所有在它左下方的点的总数, 问你点集中每个 order 的点的数量.

## 思路 ##

树状数组的牛逼之处在于, 它可以动态地查询比当前值小的元素个数 (要求取值范围不要太大). 在这题当中, 因为有两个维度, 所以我们可以先通过排序 (题目已经提前排好序了, 所以这道题不用排序) 将数据按照两个维度按照从小到大的顺序排好, 比如题目中它已经为你按照 y 轴第一顺序, x 轴第二顺序排好, 那么当你访问到第 n 个点时, 前面 n-1 个点必定在你的下方, 而后面的所有点必定要么在你上方, 要么在你右方, 反正都不可能在你左下方, 那么你只需要统计**目前为止所有横坐标小于该点的元素数量**. 方法是维护一个数组 (BIT), 每个元素表示一个横坐标的个数, 当遍历到第 n 个点时, 只需要求  p r e f i x ( x n ) prefix(x\_n) prefix(xn) 的值即可.

## 代码 ##

// 以下是上一个博客的模板
    
    #define MAXN 40000
    int bit[MAXN];
    
    int lowbit(int x) { return x&-x;}
    //void init() {memset(bit, 0, sizeof(bit));}
    
    void add(int pos, int val) { 
    	while (pos < MAXN) { 
    		bit[pos] += val;
    		pos += lowbit(pos);
    	}
    }
    
    int prefixSum(int pos) { 
    	int sum = 0;
    	while (pos > 0) { 
    		sum += bit[pos];
    		pos -= lowbit(pos);
    	}
    	return sum;
    }
    
    int rangeSum(int from, int to) { 
    	return prefixSum(to) - prefixSum(from-1);
    }
    
    // 以上是上一个博客的模板
    
    #include <stdio.h>
    #include <stdlib.h>
    int count[15000];
    int main() { 
    	int n;
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) { 
    		int x, y;
    		scanf("%d %d", &x, &y);
    		x++; // 因为BIT的下标不能是0, 所以全部加一
    		count[prefixSum(x)]++;
    		add(x, 1);
    	}
    	for (int i = 0; i < n; i++) printf("%d\n", count[i]);
    }

# PKU 2481 #

[链接在这里][Link 2]  
和上题类似, 同样是处理两个维度, 不过这次需要自己来排序

## 代码 ##

#define MAXN 100010
    int bit[MAXN];
    
    int lowbit(int x) { return x&-x;}
    //void init() {memset(bit, 0, sizeof(bit));}
    
    void add(int pos, int val) { 
        while (pos < MAXN) { 
            bit[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    int prefixSum(int pos) { 
        int sum = 0;
        while (pos > 0) { 
            sum += bit[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
    
    int rangeSum(int from, int to) { 
        return prefixSum(to) - prefixSum(from-1);
    }
    
    // 以上是上一个博客的模板
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    
    typedef struct { 
        int from;
        int to;
        int id;
    } Range;
    
    int compare(Range a, Range b) { 
        if (a.to == b.to) return a.from < b.from;
        return a.to > b.to;
    }
    
    Range ranges[100000];
    int count[100000];
    int main() { 
        int n;
        while(scanf("%d", &n) != EOF) { 
            memset(bit, 0, sizeof(bit));
            if (!n) break;
            for (int i = 0; i < n; i++) { 
                int x, y;
                scanf("%d %d", &x, &y);
                x++;
                y++;
                ranges[i].from = x;
                ranges[i].to = y;
                ranges[i].id = i;
            }
            std::sort(ranges, ranges+n, compare);
            int sameCount = 0;
            int prevX = -1;
            int prevY = -1;
            int lastValue = -1;
            for (int i = 0; i < n; i++) { 
                int x = ranges[i].from;
                int y = ranges[i].to;
                if (x==prevX && y==prevY) count[ranges[i].id] = lastValue;
                else count[ranges[i].id] = prefixSum(x);
                prevX = x;
                prevY = y;
                add(x, 1);
                lastValue = count[ranges[i].id];
            }
            printf("%d", count[0]);
            for (int i = 1; i < n; i++) { 
                printf(" %d", count[i]);
            }
            printf("\n");
        }
    }

这题卡时间卡的不要DBL了, 我改了三个地方才不超时:

1.  排序算法从 <stdlib.h> 的 qsort 改成了 <algorithm> 的sort (自己试了一下, 对于 1e5 的数据量后者的排序时间大概是前者的 1/8)
2.  因为题干要求两个区间不能完全一样, 我之前的写法是比他强壮的数量等于前缀和减去区间相同的数量, 这样做会重复计算相同的前缀和, 我改成了如果区间和前一个相同, 就使用前一个的结果的缓存
3.  **最坑的点**, 最后输出的时候我习惯上用 if(i) printf(" “) 来打印中间的空格, 但是这样会造成 printf 函数调用的次数多了一倍, 而如果使用 if (i) printf(” %d") 来写就不会超时…

# POJ 3067 #

[链接在这里][Link 3]

## 思路 ##

先按照递增顺序排序, 然后对于每条边只需要记录当前有多少边的另一端点比它的另一端大即可.  
**因为最多可能有 1000 \* 1000 个边, 最坏情况下的交点个数可能爆 INT (虽然我不是很会算最坏情况有多少个交点)**

## 代码 ##

#define MAXN 1011
    int bit[MAXN];
    
    int lowbit(int x) { return x&-x;}
    //void init() {memset(bit, 0, sizeof(bit));}
    
    void add(int pos, int val) { 
        while (pos < MAXN) { 
            bit[pos] += val;
            pos += lowbit(pos);
        }
    }
    
    int prefixSum(int pos) { 
        int sum = 0;
        while (pos > 0) { 
            sum += bit[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
    
    int rangeSum(int from, int to) { 
        return prefixSum(to) - prefixSum(from-1);
    }
    
    // 以上是上一个博客的模板
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    
    typedef struct { 
        int left;
        int right;
    } Road;
    
    int compare(Road a, Road b) { 
        if (a.right == b.right) return a.left < b.left;
        return a.right < b.right;
    }
    
    Road roads[1000000];
    int main() { 
        int T;
        scanf("%d", &T);
        for (int testcase = 1; testcase <= T; testcase++) { 
            memset(bit, 0, sizeof(bit));
            int n,m,k;
            scanf("%d%d%d", &n, &m, &k);
            for (int i = 0; i < k; i++) { 
                int left, right;
                scanf("%d%d", &left, &right);
                roads[i].left = left;
                roads[i].right = right;
            }
            std::sort(roads, roads+k, compare);
            long long ans = 0;
            for (int i = 0; i < k; i++) { 
                int left = roads[i].left;
                ans += rangeSum(left+1, 1000);
                add(left, 1);
            }
            printf("Test case %d: %lld\n",testcase, ans);
        }
    }

[Link 1]: http://poj.org/problem?id=2352
[Link 2]: http://poj.org/problem?id=2481
[Link 3]: http://poj.org/problem?id=3067