首页 > 代码库 > HDU5124 lines
HDU5124 lines
离散化 + 树状数组。
这些东西自己都是刚接触不久的，所以需要多写点题练练手。
题目描述：
一维坐标中有N条线段，其中有一个点上面覆盖的线段数是最多的，求该点上面的线段数目。
这道题和HDU1556特别相似，不过这道题数据比较大，所以要离散化预处理一下数据。
个人常用的离散化方法：先预存一下数据，然后用数组tmp[]存一下数据，对tmp[]数组排序，然后二分查找原数据在tmp[]数组中的下标，并且把下标作为离散化的数据。
然后就是树状数组这部分，一维树状数组支持两种操作: 1. 单点更新，区间求和 ； 2 . 区间更新，单点求值。这两种操作的更新和求和这部分是反过来的，前者是对上更新，对下求值，后者是对下更新，对上求值。所以说树状数组比较好实现也容易推广到多维，但是功能不如线段树。
算法：
用树状数组来存每个点的覆盖次数，覆盖一次即视为该点的数值+1；由于更新的时候是区间更新，所以对[a , b]这个区间覆盖的话，先把[1 , a-1]区间更新-1，然后把[1,b]区间更新+1，所以求最后所有点的最大值即可。
#include <iostream>#include <iomanip>#include <stdio.h>#include <stdlib.h>#include <algorithm>#include <functional>#include <vector>#include <cmath>#include <string>#include <stack> #include <queue>using namespace std;const int maxn = 110000 + 500;int c[maxn] , n , k;int L[maxn][2] , tmp[maxn];int lowbit(int x){ return x & (-x);}void update(int x , int num){ while(x > 0) { c[x] += num; x -= lowbit(x); }}int getsum(int i){ int res = 0; while(i <= k) { res += c[i]; i += lowbit(i); } return res;}int binary_Search(int a[] , int l , int r , int x){ int m = (l + r) >> 1; while(l <= r) { if(a[m] == x) return m; if(a[m] < x) l = m + 1; if(a[m] > x) r = m; m = (l + r) >> 1; } return -1;}int main() { int T , i , j; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(c , 0 , sizeof(c)); for(i = 1 , k = 0 ; i <= n ; i++) { scanf("%d %d" , &L[i][0] , &L[i][1]); tmp[++k] = L[i][0]; tmp[++k] = L[i][1]; } sort(tmp + 1 , tmp + k +1); for(i = 1 ; i <= n ; i++) { for(j = 0 ; j <= 1 ; j++) { int pos = binary_Search(tmp , 1 , k , L[i][j]); L[i][j] = pos; } } for(i = 1 ; i <= n ; i++) { update(L[i][0] - 1 , -1); update(L[i][1] , 1); } int max = 1; for(i = 1 ; i <= k ; i++) { if(getsum(max) < getsum(i)) max = i; } printf("%d\n",getsum(max)); } return 0;}
HDU5124 lines
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。