区间交
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1424 Accepted Submission(s): 543
Problem Description
小A有一个含有n个非负整数的数列与m个区间。每个区间可以表示为li,ri。
它想选择其中k个区间， 使得这些区间的交的那些位置所对应的数的和最大。
例如样例中，选择[2,5]与[4,5]两个区间就可以啦。
Input
多组测试数据
第一行三个数n,k,m(1≤n≤100000,1≤k≤m≤100000)。
接下来一行n个数ai，表示lyk的数列(0≤ai≤109)。
接下来m行，每行两个数li,ri，表示每个区间(1≤li≤ri≤n)。
Output
一行表示答案
Sample Input
5 2 3 1 2 3 4 6 4 5 2 5 1 4
Sample Output
10
Source
2016"百度之星" - 初赛（Astar Round2B）
Recommend
wange2014 | We have carefully selected several similar problems for you: 6331 6330 6329 6328 6327
Statistic | Submit | Discuss | Note
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll long long
#define maxn 100005
#define MAX 1000000000
#define ms memset
using namespace std;int n,k,m,x;
ll seq[maxn];
int tree[maxn];///树状数组
/*
中文题目，题意不解释首先我们需要数组的前缀和，这个就不用树状数组来维护了，
因为结果和查询的数量没有关系的。
题目给定了m个区间要求选k个，最终结果是所有区间重叠的部分。又是这种组合优化问题，
m个中选择k个最大化答案。
直接枚举超时没话说。（C(m,k)）不妨观察答案区间的性质，首先如果存在一个答案区间，
那么其左边界一定是区间的一个左边界。
不妨遍历所有区间的左边界，对每个遍历到的区间，
用线段树维护其过程中区间重叠的最大次数，
因为观察加上自己想也可以知道这个序列应该是递减的，
二分查找满足大于等于k的最右边界（贪心）。
那么每次遍历时就可以维护一个最大值，即答案。
用二分得来的右界和遍历到的左边界构造出最大答案参与比较即可。*/struct node
{int l,r;
};
node q[maxn];bool cmp(node x,node y)
{if(x.l==y.l) return x.r<y.r;return x.l<y.l;
}int lowbit(int x) {return x&(-x);}ll sum(int x) { ll res=0;for(;x>0;res+=tree[x],x-=lowbit(x)); return res;}void add(int x,int d) { for( ; x<=n ; tree[x]+=d , x+=lowbit(x) ); }int main( )
{while(scanf("%d%d%d",&n,&k,&m)!=EOF){memset(tree,0,sizeof(tree));for(int i=1;i<=n;i++) { scanf("%d",&x) ; seq[i]=seq[i-1]+x; }for(int i=0;i<m;i++) scanf("%d%d",&q[i].l,&q[i].r);sort(q,q+m,cmp);ll ans=0;for(int i=0;i<m;i++){add(q[i].l,1);add(q[i].r+1,-1);int l=q[i].l,r=q[i].r;int pos=-1;// for(int i=l;i<=r;i++) cout<<sum(i)<<" ";puts("");while(r>=l){int mid=(l+r)>>1;if(sum(mid)>=k){pos=mid;l=mid+1;///取其最右的端点边界}else r=mid-1;}if(pos==-1) continue;else ans=max(ans,seq[pos]-seq[q[i].l-1]);}printf("%lld\n",ans);}return 0;
}