首页 > 代码库 > HDU 5700 区间交（线段树）
HDU 5700 区间交（线段树）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5700
【题目大意】
给出一个长度为n的数列和m个区间，现在求k个区间，使得他们的区间交内的数列项和最大。
【题解】
将区间按照右端点为第一关键字排序，
那么在从后往前扫描的过程中，已经扫过的部分右端点一定大于当前
所以我们可以枚举区间交的右端点，找出第k小的左端点，来更新答案
因为右端点固定，因此左端点越小，答案一定越大，
所以枚举右端点不会遗漏答案。
【代码】
#include <cstdio> #include <cstring>#include <algorithm>using namespace std;const int N=200000,M=200000;typedef long long LL;int k,q,x,y,T[M<<2],n,m;void up(int x){T[x]=T[x<<1]+T[x<<1|1];}void update(int t,int num,int l,int r,int x){ if(l==r){T[x]+=num;return;} int mid=(l+r)>>1; if(t<=mid)update(t,num,l,mid,x<<1); else update(t,num,mid+1,r,x<<1|1); up(x);} int find(int k,int l,int r,int x){ int mid=(l+r)>>1,tmp=T[x<<1]; if(l==r)return l; if (k<=tmp)return find(k,l,mid,x<<1); else return find(k-tmp,mid+1,r,x<<1|1);}LL s[N];struct data{int l,r;}p[N];bool cmp(data a,data b){return a.r<b.r||a.r==b.r&&a.l<b.l;}int main(){ while(~scanf("%d%d%d",&n,&k,&m)){ memset(T,0,sizeof(T)); for(int i=1;i<=n;i++){ scanf("%d",&x); s[i]=s[i-1]+x; }for(int i=1;i<=m;i++)scanf("%d%d",&p[i].l,&p[i].r); sort(p+1,p+m+1,cmp); for(int i=m;i>m-k+1;i--)update(p[i].l,1,1,n,1); LL ans=0; for(int i=m-k+1;i;i--){ update(p[i].l,1,1,n,1); int t=find(k,1,n,1); if(t<=p[i].r)ans=max(ans,s[p[i].r]-s[t-1]); }printf("%lld\n",ans); }return 0;}
HDU 5700 区间交（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。