首页 > 代码库 > hdu5124（树状数组+离散化）
hdu5124（树状数组+离散化）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5124
题意：有n条线段，求被覆盖到次数最多的点的次数
分析：
1.可以转化成求前缀和最大的问题：将区间改成左闭右开（即右端点加1），排序，从左往右遍历，若为左端点则加一，右端点则减一。
2.树状数组，离散化一下，然后区间更新，单点查询。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;int a[500010],n,m;int c[200010];struct node{ int l,r;}s[100010];int bin(int key,int n,int a[]){ int l=0,r=n-1; while(l<=r) { int m=(l+r)>>1; if(a[m]==key)return m; if(a[m]<key)l=m+1; else r=m-1; } return -1;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt=0,l,r; memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) { scanf("%d%d",&l,&r); s[i].l=l;s[i].r=r; a[cnt++]=l;a[cnt++]=r; } sort(a,a+cnt); m=1; //离散化好模板 for(int i=1;i<cnt;i++) if(a[i]!=a[i-1])a[m++]=a[i]; for(int i=m-1;i>=0;i--) if(a[i]!=a[i-1]+1)a[m++]=a[i-1]+1; sort(a,a+m); for(int i=1;i<=n;i++) { l=bin(s[i].l,m,a); r=bin(s[i].r,m,a); c[l]++;c[r+1]--; } int ans=0,sum=0; for(int i=0;i<m;i++) { sum+=c[i]; ans=max(ans,sum); } printf("%d\n",ans); }}
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;int a[500010],n,m;int c[200010];struct node{ int l,r;}s[100010];int lowbit(int x){ return x&(-x);}void update(int x,int d){ while(x) { c[x]+=d; x-=lowbit(x); }}int sum(int x){ int res=0; while(x<=m+1) { res+=c[x]; x+=lowbit(x); } return res;}int bin(int key,int n,int a[]){ int l=0,r=n-1; while(l<=r) { int m=(l+r)>>1; if(a[m]==key)return m; if(a[m]<key)l=m+1; else r=m-1; } return -1;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt=0,l,r; memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) { scanf("%d%d",&l,&r); s[i].l=l;s[i].r=r; a[cnt++]=l;a[cnt++]=r; } sort(a,a+cnt); m=1; //离散化好模板 for(int i=1;i<cnt;i++) if(a[i]!=a[i-1])a[m++]=a[i]; for(int i=m-1;i>=0;i--) if(a[i]!=a[i-1]+1)a[m++]=a[i-1]+1; sort(a,a+m); for(int i=1;i<=n;i++) { l=bin(s[i].l,m,a); r=bin(s[i].r,m,a); //树状数组习惯把区间右移了1，防止x+=lowbit(x)陷于死循环，不过这里加不是这个原因 l+=2;r+=2; update(l-1,-1);update(r,1); } int ans=0; for(int i=2;i<=m+1;i++)ans=max(ans,sum(i)); printf("%d\n",ans); }}
当然不一定非得把坐标映射到x轴上，vextor<pair<int,int> >v;v[i].first用来把坐标排序，起到映射的作用。然后数组的下标就起到了压缩的作用。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;vector <pair<int,int> > v;int main(){ int T; scanf("%d",&T); while (T--) { v.clear(); int n; scanf("%d",&n); for (int i = 0; i < n; i++) { int x; scanf("%d",&x); v.push_back(make_pair(x,1)); scanf("%d",&x); v.push_back(make_pair(x + 1,-1)); } sort(v.begin(), v.end()); int ans = 0; int sum = 0; for (int i = 0; i < v.size(); i++) { sum += v[i].second; ans = max(sum,ans); } printf("%d\n",ans); }}
hdu5124（树状数组+离散化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。