记录编号	142557	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]拆迁队	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.167 s
提交时间	2014-12-09 19:23:31	内存使用	37.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL INF=(LL)1e18;
const int SIZEN=100010;
class Point{
public:
	LL x,y;
};
Point operator - (Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}
LL Cross(Point a,Point b){//叉积,a逆时针旋转到b的有向三角形面积
	return a.x*b.y-b.x*a.y;
}
LL Calc(Point p,LL k){//p.x*k+p.y
	return p.x*k+p.y;
}
class Hull{//凸包中的点横坐标递增
public:
	Point *s;
	int n;//0~n-1
	//下凸壳,形状类似y=1/x在第一象限的部分
	void clear(Point *s_){
		s=s_;
		n=0;
	}
	void Insert(Point p){//向凸包后端插入一个点
		while(n>=2&&Cross(s[n-1]-p,s[n-2]-p)>=0) n--;
		s[n++]=p;
	}
	Point Find_Best(LL k){//x*k+y最小的点
		int l=0,r=n-1;
		while(l<r){
			int mid=(l+r)/2;
			if(Calc(s[mid],k)<=Calc(s[mid+1],k)) r=mid;
			else l=mid+1;
		}
		return s[l];
	}
	LL Calc_Best(LL k){//凸包上所有点中,x*k+y的最小值
		if(!n) return INF;
		return Calc(Find_Best(k),k);
	}
};
class Node{//线段树的节点
	public:
		int a,b;//范围
		int lc,rc;
		Hull H;
	};
class Segment_Tree{
public:
	Node Tree[SIZEN*2];
	int Tree_tot;
	Point Hull_Pool[SIZEN*17];
	int Hull_tot;
	void clear(void){Tree_tot=Hull_tot=0;}
	Segment_Tree(void){clear();}//两个指针都初始化为零
	Point* Quest_Hull(int n){//申请一块长度为n的凸包池
		Point *p=&Hull_Pool[Hull_tot];
		Hull_tot+=n;
		return p;
	}
	int Build(int l,int r){
		if(l>r) return 0;
		int p=++Tree_tot;
		Node &now=Tree[p];
		now.a=l,now.b=r;
		now.H.clear(Quest_Hull(r-l+1));
		if(l==r) now.lc=now.rc=0;
		else{
			int mid=(l+r)/2;
			now.lc=Build(l,mid);
			now.rc=Build(mid+1,r);
		}
		return p;
	}
	void Modify(int root,int x,Point p){//向位置x加入点p
		if(!root) return;
		Node &now=Tree[root];
		if(now.a>x||now.b<x) return;
		now.H.Insert(p);
		Modify(now.lc,x,p);
		Modify(now.rc,x,p);
	}
	LL Calc_Best(int root,int l,int r,LL k){//位置l~r的点中,x*p+y的最小值
		if(!root) return INF;
		Node &now=Tree[root];
		if(now.a>r||now.b<l) return INF;
		if(now.a>=l&&now.b<=r) return now.H.Calc_Best(k);//[l,r]覆盖此段
		else return min(Calc_Best(now.lc,l,r,k),Calc_Best(now.rc,l,r,k));
	}
};
int N;
LL A[SIZEN],B[SIZEN];
LL F[SIZEN],G[SIZEN];
vector<int> G_pos[SIZEN];//G_pos[i]中是所有G值为i的位置
int G_root[SIZEN]={0};
Segment_Tree SGT;
LL Calc_Const(LL k){//F[k]中和k相关的数
	return (k*k-k)/2+A[k]+B[k];
}
Point Turn_Point(LL k){//将k位置的信息转化成点的坐标
	Point p;
	p.x=A[k]-k;
	p.y=F[k]-A[k]*k-A[k]+(k*k+k)/2;
	return p;
}
LL Calc(int i,int j){//上一个不拆的是i,这次不拆j
	return Calc(Turn_Point(i),j)+Calc_Const(j);
}
void Calc_F(int i){//计算F[i]
	if(G[i]<=1){
		if(A[i]<i) F[i]=INF;//必须要从1开始吧......
		else F[i]=Calc(0,i);//由于A[0]=B[0]=0,所以这么计算是正确的
	}
	else{
		vector<int> &g=G_pos[G[i]-1];
		int b=upper_bound(g.begin(),g.end(),i)-g.begin()-1;//找到其离散化后的位置
		F[i]=SGT.Calc_Best(G_root[G[i]-1],0,b,i)+Calc_Const(i);
	}
}
void Add_To_Tree(int i){//信息加入线段树中
	if(F[i]==INF) return;
	vector<int> &g=G_pos[G[i]];
	int x=lower_bound(g.begin(),g.end(),i)-g.begin();
	SGT.Modify(G_root[G[i]],x,Turn_Point(i));
}
bool Cmp_DP_Order(int i,int j){//A[i]-i小的先DP,如果相同那么G小的先DP
	if(A[i]-i==A[j]-j) return G[i]<G[j];
	return A[i]-i<A[j]-j;
}
void Process(void){//主处理过程
	static int lis[SIZEN];
	for(int i=1;i<=N;i++) lis[i]=i;
	sort(lis+1,lis+1+N,Cmp_DP_Order);
	A[0]=A[N+1]=B[0]=B[N+1]=0;//将用到这一性质
	for(int i=1;i<=N;i++){
		Calc_F(lis[i]);
		Add_To_Tree(lis[i]);
	}
	LL mx=0,ans=INF;
	for(int i=1;i<=N;i++) mx=max(mx,G[i]);
	for(int i=1;i<=N;i++){
		if(G[i]==mx)
			ans=min(ans,Calc(i,N+1));//由于A[N+1]=B[N+1]=0所以这么算是对的
	}
	printf("%lld %lld\n",mx,ans);
}
void Calc_LNDS(LL a[],int n,LL f[]){//求数列a[i]的最长非降子序列
	static LL bst[SIZEN];
	int len=0;
	bst[0]=-INF;
	for(int i=1;i<=n;i++){
		if(a[i]<0){
			f[i]=0;//设为-INF会在按G统计时造成不必要的麻烦
			continue;
		}
		int k=upper_bound(bst,bst+len+1,a[i])-bst;
		if(k>len) len=k;
		f[i]=k;
		bst[k]=a[i];
	}
}
void Prepare(void){//预处理
	static LL A1[SIZEN];
	for(int i=1;i<=N;i++) A1[i]=A[i]-i;
	Calc_LNDS(A1,N,G);
	for(int i=1;i<=N;i++) G_pos[G[i]].push_back(i);
	for(int i=1;i<=N;i++) sort(G_pos[i].begin(),G_pos[i].end());//离散化
	for(int i=1;i<=N;i++) G_root[i]=SGT.Build(0,G_pos[i].size()-1);
}
void Read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lld",&A[i]);
	for(int i=1;i<=N;i++) scanf("%lld",&B[i]);
}
int main(){
	freopen("lanxisi.in","r",stdin);
	freopen("lanxisi.out","w",stdout);
	Read();
	Prepare();
	Process();
	return 0;
}