题目描述

健佳正在制定下个假期去台湾的游玩计划。在这个假期，健佳将会在城市之间奔波，并且参观这些城市的景点。

在台湾共有n个城市，它们全部位于一条高速公路上。这些城市连续地编号为0到n-1。对于城市i(0<i<n-1)而言，与其相邻的城市是i-1和i+1。但是对于城市 0，唯一与其相邻的是城市 1。而对于城市n-1，唯一与其相邻的是城市n-2。

每个城市都有若干景点。健佳有d天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天，健佳可以选择去一个相邻的城市，或者参观所在城市的所有景点，但是不能同时进行。即使健佳在同一个城市停留多次，他也不会去重复参观该城市的景点。请帮助健佳策划这个假期，以便能让他参观尽可能多的景点。

题解

很容易发现，路线只有四种可能，一直往左走，一直往右走，先左走后右走，先右走后左走。

他能够游览的范围是一段区间，暴力的话就是枚举这段区间的左右端点，然后查一下区间前k大。

然后考虑优化，一直往左或往右这个可以直接扫描+主席树，不用优化。

后面两种情况本质相同，下面只讨论先左走后右走的情况。

假设我们有一堆询问，为先向左走到i这个点，再往右走到y这个点，当y为多少时最优。

结论，当i减小的时候，y是单调不增的。证明自己yy一下就差不多。

然后我们就可以solve(l,r,L,R)表示询问为l~r，答案区间为L~R，类似整体二分的做就可以了。

细节：又犯了SB错误，这个错误犯了好几次了，就是主席树查询到叶子节点时要

if(l==r)return (tr[now]-tr[pre])/(cnt[now]-cnt[pre])*k;

代码

#include
     
      #include
      
       #include
       
        #define N 100009 using namespace std;typedef long long ll;int b[N],a[N],tot,L[N*30],R[N*30],cnt[N*30],s,d,n,top,T[N];ll ans,tr[N*30];inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}inline void upd(int &now,int pre,int l,int r,int x){    now=++tot;L[now]=L[pre];R[now]=R[pre];tr[now]=tr[pre]+b[x];cnt[now]=cnt[pre]+1;    if(l==r)return;    int mid=(l+r)>>1;    if(mid>=x)upd(L[now],L[pre],l,mid,x);    else upd(R[now],R[pre],mid+1,r,x);}inline ll query(int now,int pre,int l,int r,int k){    if(cnt[now]-cnt[pre]<=k)return tr[now]-tr[pre];    if(l==r)return (tr[now]-tr[pre])/(cnt[now]-cnt[pre])*k;     int mid=(l+r)>>1,num=cnt[R[now]]-cnt[R[pre]];    if(num
        
         r)return;    int mid=(l+r)>>1,id=L;ll num=0;    for(int i=L;i<=R;++i){        int kk=i-mid+s-mid;if(i==s)kk=i-mid;        if(kk>d)continue;        ll x=query(T[i],T[mid-1],1,top,d-kk);            if(x>num)num=x,id=i,ans=max(ans,x);    }    solve1(l,mid-1,L,id);solve1(mid+1,r,id,R);}void solve2(int l,int r,int L,int R){    if(l>r)return;    int mid=(l+r)>>1,id=R;ll num=0;    for(int i=L;i<=R;++i){        int kk=mid-i+mid-s;if(i==s)kk=mid-i;        if(kk>d)continue;        ll x=query(T[mid],T[i-1],1,top,d-kk);        if(x>num)num=x,id=i,ans=max(ans,x);    }    solve2(l,mid-1,L,id);solve2(mid+1,r,id,R);}int main(){    n=rd();s=rd();d=rd();s++;    for(int i=1;i<=n;++i)a[i]=rd(),b[i]=a[i];    sort(b+1,b+n+1);top=unique(b+1,b+n+1)-b-1;    for(int i=1;i<=n;++i){        a[i]=lower_bound(b+1,b+top+1,a[i])-b;        upd(T[i],T[i-1],1,top,a[i]);    }    solve1(1,s,s,n);solve2(s,n,1,s);    cout<