枚举左端点,然后在线段树内,更新所有左边界小于当前点的区间的右端点,然后查线段树二分查第k大就好
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = ;
LL a[N];
struct Node{
int l,r;
bool operator<(const Node &rhs)const{
if(l==rhs.l)return r<rhs.r;
return l<rhs.l;
}
}p[N];
int c[N<<];
void add(int rt,int l,int r,int x){
++c[rt];
if(l==r)return;
int m=(l+r)>>;
if(x<=m)add(rt<<,l,m,x);
else add(rt<<|,m+,r,x);
}
int ask(int rt,int l,int r,int k){
if(l==r)return l;
int m=(l+r)>>;
if(c[rt<<|]>=k)ask(rt<<|,m+,r,k);
else ask(rt<<,l,m,k-c[rt<<|]);
}
int main(){
int n,k,m;
while(~scanf("%d%d%d",&n,&k,&m)){
for(int i=;i<=n;++i){
LL x;scanf("%I64d",&x);
a[i]=a[i-]+x;
}
for(int i=;i<=m;++i){
scanf("%d%d",&p[i].l,&p[i].r);
}
sort(p+,p++m);
memset(c,,sizeof(c));
int cnt=;
LL res=;
for(int i=;i<=m;++i){
for(;cnt<=m&&p[cnt].l<=p[i].l;++cnt)
add(,,n,p[cnt].r);
if(c[]<k)continue;
int cur=ask(,,n,k);
if(cur>=p[i].l)res=max(res,a[cur]-a[p[i].l-]);
}
printf("%I64d\n",res);
}
return ;
}