IOI2014 假期

题目:

   健佳正在制定下个假期去台湾的游玩计划。在这个假期,健佳将会在城市之间奔波,并且参观这些城市的景点。
   在台湾共有n个城市,它们全部位于一条高速公路上。这些城市连续地编号为。对于城市() 而言,与其相邻的城市是。但是对于城市,唯一与其相邻的是城市。而对于城市,唯一与其相邻的是城市
   每个城市都有若干景点。健佳有天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天,健佳可以选择去一个相邻的城市,或者参观所在城市的所有景点,但是不能同时进行。即使健佳在同一个城市停留多次,他也不会去重复参观该城市的景点。请帮助健佳策划这个假期,以便能让他参观尽可能多的景点。

思路:

   先考虑枚举区间的两个端点,如果走遍这个区间还剩天,那么只要在区间内求前大的权值和即可。求前大的权值和可以通过堆(离线)或主席树(在线)。这样就能得到一个的暴力了。
   考虑优化这个暴力,假设表示区间左端点为时,最优的右端点的位置。不难猜到(感性理解,对拍验证)。也就是说这个区间的右端点是满足单调性的,所以可以用分治优化这个枚举。
   当要计算这些点的时,假设我们已知这些值都在之间。设,,每次暴力的扫出,剩下的的解就在的解就在。因为这两个区间没有重叠(的重叠可以忽略),所以每层暴力扫描的点就只有个。枚举的次数就是次,在加上前面求区间前大和的复杂度,就是

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
template<class T> inline bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
typedef long long ll;
const int MN=1e5+5;
int a[MN],b[MN];
int ls_[MN*20],rs_[MN*20],cnt[MN*20],tot;
ll sum[MN*20];
#define ls ls_[o]
#define rs rs_[o]
#define mid (L+R>>1)
#define lson ls,L,mid
#define rson rs,mid+1,R
void upd(int x,int v,int &o,int L,int R){
    ls_[++tot]=ls_[o];
    rs_[tot]=rs_[o];
    cnt[tot]=cnt[o]+1;
    sum[tot]=sum[o]+v;
    o=tot;
    if(L==R)return;
    if(x<=mid)upd(x,v,lson);
    else upd(x,v,rson);
}
ll qry(int ld,int rd,int k,int L,int R){
    if(cnt[rd]-cnt[ld]<=k)return sum[rd]-sum[ld];
    if(L==R)return (ll)b[L]*k;
    int t=cnt[rs_[rd]]-cnt[rs_[ld]];
    if(k<=t)return qry(rs_[ld],rs_[rd],k,mid+1,R);
    return qry(ls_[ld],ls_[rd],k-t,L,mid)+qry(rs_[ld],rs_[rd],t,mid+1,R);
}
#undef mid
int rt[MN],n,t,s,d;
ll ans;
void solve(int l,int r,int L,int R){
    if(l>r)return;
    int mid=l+r>>1,ch=L;
    ll now=-1;
    rep(i,L,R){
        int k=d-((s-mid<<1)+(i-s<<1)-std::max(s-mid,i-s));
        if(k<=0)break;
        ll tmp=qry(rt[mid-1],rt[i],k,1,t);
        if(tomax(now,tmp))
            ch=i;
    }
    tomax(ans,now);
    solve(l,mid-1,L,ch);
    solve(mid+1,r,ch,R);
}
int main(){
//  printf("%lf\n",(&cur2-&cur1)/1024.0/1024);
//  File(holiday);
    scanf("%d%d%d",&n,&s,&d);s++;
    rep(i,1,n){
        scanf("%d",a+i);
        b[i]=a[i];
    }
    std::sort(b+1,b+1+n);
    t=std::unique(b+1,b+1+n)-b-1;
    rep(i,1,n)
        a[i]=std::lower_bound(b+1,b+1+t,a[i])-b;
    rep(i,1,n){
        rt[i]=rt[i-1];
        upd(a[i],b[a[i]],rt[i],1,t);
    }
    solve(1,s,s,n);
    printf("%lld\n",ans);
    return 0;
}