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）
皮球爷爷出的题（lyk躺枪）
离线排序+线段树+尺取
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define ll long long #define p1 id<<1 #define p2 id<<1^1 using namespace std; int n,m,k; int tree[400005],add[400005],a[100005]; ll ans,s[100005]; struct ty { int x,y; }p[100005]; bool cmp(ty a,ty b) { if(a.y!=b.y) return a.y>b.y; else return a.x<b.x; } void build(int id,int l,int r) { if(l==r) { tree[id]=add[id]=0; return; } int mid=(l+r)>>1; build(p1,l,mid); build(p2,mid+1,r); tree[id]=add[id]=0; } void update(int id,int l,int r,int x,int y) { if(x<=l&&r<=y) { add[id]+=1; return; } add[p1]+=add[id]; add[p2]+=add[id]; add[id]=0; int mid=(l+r)>>1; if(y<=mid) update(p1,l,mid,x,y); else if(x>mid) update(p2,mid+1,r,x,y); else { update(p1,l,mid,x,mid); update(p2,mid+1,r,mid+1,y); } tree[id]=min(tree[p1],tree[p2]); } int query(int id,int l,int r,int x,int y) { if(x<=l&&r<=y) return tree[id]+add[id]; add[p1]+=add[id]; add[p2]+=add[id]; add[id]=0; int mid=(l+r)>>1; int s; if(y<=mid) s=query(p1,l,mid,x,y); else if(x>mid) s=query(p2,mid+1,r,x,y); else s=min(query(p1,l,mid,x,mid),query(p2,mid+1,r,mid+1,y)); tree[id]=min(tree[p1]+add[p1],tree[p2]+add[p2]); return s; } int main() { while(scanf("%d%d%d",&n,&k,&m)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } for(int i=1;i<=m;i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+m+1,cmp); build(1,1,n); ans=0; int l=1e9; for(int i=1;i<=m;i++) { update(1,1,n,p[i].x,p[i].y); l=min(l,p[i].y); while(l>0&&query(1,1,n,l,l)>=k) l--; l++; ans=max(ans,s[p[i].y]-s[l-1]); } printf("%lld\n",ans); } return 0; }