题目
这题还是很有意思的，一开始没想到，这题学会了如何处理区间交集。
对于区间问题的解法，我们通常一般固定一个端点，然后枚举另一个端点。
我们对左端点排序，然后用小根堆储存右端点，这样做取出来的区间一定是区间交集（这个非常妙，不懂的模拟一下样例，非常清楚），然后对每一个区间取max就可以了。
注意，当不满足要求时，输出0.
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<vector> #include<cmath> #include<map> #include<string> #include<queue> #include<stack> #include<bitset> #include<list> #include<set> #include<utility> #include<functional> #include<iomanip> #define IO ios::sync_with_stdio(false) #define eps 1e-7 #define int long long using namespace std; int k,n,m,sum[100005],ans; priority_queue<int,vector<int>,greater<int> >q; struct node { int l,r; }a[100005]; bool cmp(node x,node y) { if(x.l==y.l)return x.r<y.r; return x.l<y.l; } signed main() { IO; while(cin>>n>>k>>m) { ans=0; memset(sum,0,sizeof(sum)); while(!q.empty())q.pop(); for(int i=1;i<=n;i++) { int x; cin>>x; sum[i]=sum[i-1]+x; } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; a[i].l=x,a[i].r=y; } sort(a+1,a+m+1,cmp); for(int i=1;i<=k-1;i++) { q.push(a[i].r); } for(int i=k;i<=m;i++) { int l=a[i].l; q.push(a[i].r); if(q.size()>k)q.pop(); ans=max(ans,sum[q.top()]-sum[l-1]); } cout<<ans<<endl; } }