【BZOJ4367】[IOI2014]holiday假期

Description

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

Input

第1行: n, start, d.
第2行: attraction[0], ..., attraction[n-1].
n: 城市数。
start: 起点城市的编号。
d: 假期的天数。
attraction: 长度为n的数组；attraction[i] 表示城市i的景点数目，其中0≤i≤n-1。

Output

输出一个整数表示健佳最多可以参观的景点数。

Sample Input

5 2 7
10 2 20 30 1

Sample Output

HINT

假设健佳有 7 天假期，有 5 个城市（参见下表），而且他由城市 2 开始。在第一天，健佳参观城市2的 20 个景点。第二天，健佳由城市 2 去往城市 3。而在第三天，健佳参观城市 3 的30 个景点。接下来的3天，健佳由城市 3 前往城市 0。而在第 7 天，健佳参观城市0的 10 个景点。这样健佳参观的景点总数是20+30+10=60，这是他由城市 2 开始、在 7 天假期内最多能参观的景点数目。

【BZOJ4367】[IOI2014]holiday假期分治+主席树-LMLPHP

题解：【BZOJ4367】[IOI2014]holiday假期分治+主席树-LMLPHP

解决一个本人脑抽的问题：既然单调了为啥不能双指针？d[i]单调又没说一定是连续的单调。。。

#include <cstring>

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=100010;

int n,S,m,tot,N,cost;

int v[maxn],rt[maxn];

ll ans;

ll f1[maxn<<1],g1[maxn<<1],f2[maxn*3],g2[maxn*3],ref[maxn];

struct sag

{

	int ls,rs,siz;

	ll sum;

}s[maxn*20];

struct number

{

	int val,org;

}num[maxn];

void insert(int x,int &y,int l,int r,int a)

{

	y=++tot,s[y]=s[x],s[y].siz++,s[y].sum+=ref[a];

	if(l==r)	return ;

	int mid=(l+r)>>1;

	if(a<=mid)	insert(s[x].ls,s[y].ls,l,mid,a);

	else	insert(s[x].rs,s[y].rs,mid+1,r,a);

}

ll query(int x,int l,int r,int y)

{

	if(y<0)	return -1;

	if(!y)	return 0;

	if(!x||y>=s[x].siz)	return s[x].sum;

	if(l==r)	return y*ref[l];

	int mid=(l+r)>>1;

	if(s[s[x].rs].siz>=y)	return query(s[x].rs,mid+1,r,y);

	else	return s[s[x].rs].sum+query(s[x].ls,l,mid,y-s[s[x].rs].siz);

}

void solve(ll *f,int l,int r,int L,int R)

{

	if(l>r)	return ;

	int mid=(l+r)>>1,MID=0,i;

	ll tmp,mx=-1;

	for(i=L;i<=R;i++)

	{

		tmp=query(rt[i],1,N,mid-i*cost);

		if(tmp>mx)	mx=tmp,MID=i;

	}

	f[mid]=mx;

	solve(f,l,mid-1,L,MID);

	solve(f,mid+1,r,MID,R);

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

bool cmp(number a,number b)

{

	return a.val<b.val;

}

int main()

{

	n=rd(),S=rd()+1,m=rd();

	int i;

	for(i=1;i<=n;i++)	num[i].val=rd(),num[i].org=i;

	sort(num+1,num+n+1,cmp);

	for(i=1;i<=n;i++)

	{

		if(i==1||num[i].val>ref[N])	ref[++N]=num[i].val;

		v[num[i].org]=N;

	}

	for(i=1;i<S;i++)	insert(rt[i-1],rt[i],1,N,v[S-i]);

	cost=1,solve(f1,0,(S-1)*2,0,S-1);

	cost=2,solve(f2,0,(S-1)*3,0,S-1);

	memset(s,0,sizeof(s[0])*(tot+5));

	tot=0;

	for(i=0;i<=n-S;i++)	insert(rt[max(i-1,0)],rt[i],1,N,v[S+i]);

	cost=1,solve(g1,0,(n-S)*2+1,0,n-S);

	cost=2,solve(g2,0,(n-S)*3+1,0,n-S);

	for(i=0;i<=m;i++)

	{

		ans=max(ans,max(f1[min(i,(S-1)*2)]+g2[min(m-i,(n-S)*3+1)],f2[min(i,(S-1)*3)]+g1[min(m-i,(n-S)*2+1)]));

	}

	printf("%lld",ans);

	return 0;

}

假期