POJ2481-线段树单点更新

发表于 | 分类于 ， | | 阅读次数:

最近刚刚开始做线段树相关的题目，很艰难…依照现在的理解其实线段树的题的暴力求解思路比较容易想到，但是暴力求解的时间复杂度一般肯会超，而线段树也正是这样一种通过区间更新来解决大量输入数据问题、降低时间复杂度的高级数据结构。线段树的关键是确定每个节点维护的是什么数据，以及以什么参数为依据进行区间的查询。
被POJ上的这道题卡了很久，一开始是思路问题，后来是一些细节问题，总之还是熟练度不高…
参考博客链接

题目链接

POJ2481

题目描述

共有N头牛，每头牛对应一个进食区间[$S$,$E$], 对两头牛$i$,$j$来说，假设它们对应的区间分别为[$S_i$,$E_i$]和[$S_j$,$E_j$]，如果满足$S_i<=S_j，E_j<=E_i$且$E_i-S_i>E_j-S_j$,那么我们可以说牛$i$要比牛$j$强壮。
现对于每头牛来说计算比它强壮的牛的数量。

题解

先对区间进行排序，右端点降序为第一关键字，左端点升序为第二关键字。这样进行处理后第$i$个区间的右端点一定小于前$i-1$个区间的右端点了，那么只要进行左端点的判决就可以了，具体做法为：
每次处理一个区间后都将该区间的左端点更新到线段树中（插入后相对应叶节点数值+1，插入前为0）。
那么当我们查询第$i$个区间时其实也就是查询线段树中从1到$i-1$的区间内左端点的标记个数。
于是线段树每个节点维护的就是以该节点为根节点的子树所代表的区间中左端点的个数，而进行区间查询依据的参数也就是每个区间的左端点。
需要注意的问题:
两个区间重合时的情况要特殊处理，这种情况不算在内，做法可以是对排好序的每个区间进行处理前先检查它是否和上一查询区间重合，若重合则直接将上一区间的查询结果赋予该区间，并将该区间对应的左端点在线段树中再次更新（再次加1）,而后跳过该区间的查询。详见代码：

代码

关于线段树的实现部分基于《挑战程序设计竞赛》一书中的实现模板，也可参考其它实现模板，形成自己的书写习惯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//#include <bits/stdc++.h> //POJ上大部分题不支持该头文件
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn = 1 << 18;
typedef struct node{
    int vl;
    int vr;
    int id;
} nod;
nod a[maxn];
int d[2 * maxn];
int n, pn;
int ans[maxn];
//排序部分
bool cmp(const nod& a, const nod& b){
    if(a.vr == b.vr) 
        return a.vl < b.vl;
    else
        return a.vr > b.vr;
}
//初始化
void init(int _n){
    n = 1;
    while(n < _n) n *= 2;
    for(int i = 0; i < 2 * n - 1; i++){
        d[i] = 0;
    }
}
//查询操作
int query(int a, int b, int k, int l, int r){
    if(a <= l && b >= r) return d[k];
    if(b <= l) return 0;
    else{
        int res1 = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int res2 = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return res1 + res2;
    }
}
//更新操作
void update(int k){
    k += n - 1;
    d[k] += 1;
    while(k > 0){
        k = (k - 1) / 2;
        d[k] = d[2 *k + 1] + d[2 * k + 2];
    }
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    int t1, t2;
    while(~scanf("%d", &n)){
        memset(ans, 0, sizeof(ans));
        memset(d, 0, sizeof(d));
	    if(n == 0) break;
	    for(int i = 0; i < n; i++){
            scanf("%d%d", &t1, &t2);
            a[i].vl = t1;
            a[i].vr = t2;
            a[i].id = i;
        }
        sort(a, a + n, cmp);
        pn = n;
        init(n);
        for(int i = 0; i < pn; i++){
            //if内为判断重合区间部分
            if(i >= 1 && a[i].vl == a[i - 1].vl && a[i].vr == a[i - 1].vr){
                ans[a[i].id] = ans[a[i - 1].id];
                update(a[i].vl);
                continue;
            }
            ans[a[i].id] = query(0, a[i].vl + 1, 0, 0, n);
            update(a[i].vl);
			
        }
        for(int i = 0; i < pn; i++){
            printf("%d%c", ans[i], i < pn - 1 ? ' ' : '\n');
        }
    }
	
    return 0;
}