题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2149
题解：
斜率优化DP，栈维护凸包，LIS，分治（我也不晓得是不是CDQ分治...）
一)、解决“旧房子保留”最多
这是一个经典的问题(套路)。
令 d[i]=a[i]-i，对 d 数组求LIS得到 f[i] 即可。
f[i] 的含义：
1).d 数组中以i位置结尾的最长上升子序列长度;
2).以i位置结尾，且保留i号房子时最多可以保留的房子数。
二)、解决“总花费”最小
令 g[i] 为 以i结尾，保留i号房子且保留的房子最多时的最小花费。
看看如何转移 g 数组：
${g[i]}={min(g[j]}+frac{(a[j]+1+a[j]+i-j-1)*(i-j-1)}{2}{)}+a[i]+b[i];;{(需满足f[j]+1=f[i])}$
这个DP转移的意思还是很显然的：（以j结尾的贡献+（j+1～i-1）的贡献+i 位置的贡献）
因为j位置和i位置要保留，那么中间的区域$[ j+1, i-1]$要修改，
那自然是贪心地依次定为${a[j]+1,a[j]+2,}cdots{，a[j]+i-j-1}$的美观值
这样的话，中间的贡献就直接用等差数列求和计算。
然后可以把转移式化成如下形式（...还是很好化的）：
${g[i]}={min(g[j]}-{(j+1)a[j]}+frac{j(j+1)}{2}+{icdot d[j]}+frac{i(i-1)}{2}{)}+a[i]+b[i]$
把取小项里面只含i的项提出来：
$mathbf{{g[i]}={min(g[j]}-{(j+1)a[j]}+frac{j(j+1)}{2}+{icdot d[j]}{)}+a[i]+b[i]+frac{i(i-1)}{2}}$
现在这个转移是不是一个典型的可以斜率优化的形式？
(即${g[i]}={只有j为变量的函数}+{i,j为变量且各自的次数都为1的函数}+{只有i为变量的函数}$ )
先令 $y[j]={g[j]}-{(j+1)a[j]}+frac{j(j+1)}{2}$
错误的尝试：
然后按照斜率优化的套路走，如果对于当前计算的g[i],如果有两个来源 k，j，且k<j，假设j更优。
即 $y[j]+id[j]+a[i]+b[i]+frac{i(i-1)}{2} < y[k]+id[k]+a[i]+b[i]+frac{i(i-1)}{2}$
移项后得到$y[j]-y[k] < i(d[k]-d[j])$
接着把不等式的右边的$(d[k]-d[j])$除到左边去么？
可惜虽然我们令 k<j，但是无法保证d[k]和d[j]的大小关系，即d[i]不是单调变化的。
所以不好直接除过去，因为谁知道什么时候会让不等式变号什么时候又不变号呢？
正确的定义：
所以我们改一改上面的定义：
如果对于当前计算的g[i],如果有两个来源 k，j，且d[k]<d[j]，假设j更优。
即 $y[j]+id[j]+a[i]+b[i]+frac{i(i-1)}{2} < y[k]+id[k]+a[i]+b[i]+frac{i(i-1)}{2}$
移项后得到$y[j]-y[k] < i(d[k]-d[j])$
这时可以保证$(d[k]-d[j])<0$,所以把$(d[k]-d[j])$除过去，
得到$frac{y[j]-y[k]}{-d[j]-(-d[k])}>i$
令$mathbf{slope(j,k)=frac{y[j]-y[k]}{-d[j]-(-d[k])}}$，
那么得到如下结论：如果d[k]<d[j]且slope(j,k)>i,则 j 比 k 的转移优。
然后可以发现，如果存在三个转移来源k,j,i，且d[k]<d[j]<[i]，
同时又满足slope(i,j)>slope(j,k)，则无论如何j都不会贡献答案，所以可以排除掉j。
这时，没有了d[k]<d[j]<[i]，(令x[i]=-d[i]，即没有x[i]<x[j]<x[k])且slope(i,j)>slope(j,k)的情况，
如果把 -d[ ]看出x轴，y[ ]看出y轴，那么图像上就只剩下了下凸图形：
现在有了转移的斜率优化，可是任然有一些问题：
1).斜率优化是建立在d[k]<d[j]的基础上而不是k<j，但是dp转移却要满足j < i且d[j]<=d[i]，那如何枚举进行凸包维护和DP转移。
2).转移还有一个强限制 f[i]=f[j]+1，这个又怎么办呢？
做法如下：分治+栈维护+二分，复杂度 $O(Nlog_2^2N)$
首先把所有房子按f值分组，每次用 f=p 的组去贡献 f=p+1 的组（来满足强限制）。
枚举一个p，我们把f值等于p和p+1的位置放在一个数组h里，然后按编号排序。
接下来对h数组进行分治，用f[j]=p的g[j]去得到f[i]=p+1的g[i]。
对于分治的每一层，
把 l~mid 里面的f[j]=p 的转移来源提出来到一个数组L，
把 mid+1~r 里面的f[i]=p+1 的位置提出来到另一个数组R，
那么显然用L里面的位置转移到R里面的位置是可以满足dp的转移顺序：从前转移到后面。
然后对L，R数组分别按d值从小到大排序，
对于每一个要计算的g[R[i]],
我们先把L数组里满足d[L[j]]<d[R[i]]的j位置用栈维护好一个下凸包，（由于d[L[j]]随j单调，所以可以直接O(1)往凸包中插入一个点）
显然栈里面维护的凸包的斜率单调递增(下凸包啦)，
所以直接在栈里面二分查找到最优的位置作为g[R[i]]的转移来源点即可。
差不多就这样子了， 代码的实现——特别是分治+栈维护这一部分，如果思路还不是特别清楚的话，强烈建议看看代码。
我的错点：
1).维护凸包时，单调栈的栈顶弹出操作需要满足栈里面至少有2个元素才能进行。
2).二分取答案的时候没有写 mid=(l+r)/2,......样例居然还过了？？？
3).二分取答案写成了一个函数，同时定义了 static int l=1，r=top-1;
导致每次进入函数时没有给 l,r赋初值，......样例居然还是过了？？？
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100050
#define ll long long
#define INFi 0x3f3f3f3f
#define INFl 0x3f3f3f3f3f3f3f3fll
using namespace std;
int a[MAXN],b[MAXN],d[MAXN],f[MAXN],h[MAXN][2],cnt;
ll g[MAXN],y[MAXN],ANS2;
int N,ANS1;
struct Link{
int head[MAXN],nxt[MAXN];
Link(){memset(head,-1,sizeof(head));}
void Add(int u,int p){nxt[p]=head[u]; head[u]=p;}
}lk;
struct BIT{
int val[MAXN],N;
int Lowbit(int x){return x&-x;}
void Reset(int n){N=n; memset(val,0xc0,sizeof(val));}
void Modify(int p,int v){while(p<=N) val[p]=max(val[p],v),p=p+Lowbit(p);}
int Query(int p){
static int ret; ret=-INFi;
while(p) ret=max(ret,val[p]),p-=Lowbit(p);
return ret;
}
}DT;
double slope(int i,int j){
return 1.0*(y[i]-y[j])/(-d[i]-(-d[j]));
}
struct STK{
int s[MAXN],top;
void Reset(){top=0;}
void Push(int i){
if(top&&d[i]==d[s[top]]) top--;
while(top>1&&slope(i,s[top])>slope(s[top],s[top-1])) top--;
s[++top]=i;
}
ll Query(int i){
static int l,r,mid,ret;
if(!top) return INFl;
l=1; r=top-1; ret=top;
while(l<=r){
mid=(l+r)>>1;
if(slope(s[mid],s[mid+1])<i) ret=mid,r=mid-1;
else l=mid+1;
}
return y[s[ret]]+1ll*i*d[s[ret]];
}
}S;
void read(int &x){
static int sign; static char ch;
x=0; sign=1; ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')sign=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x=x*sign;
}
bool cmp(int i,int j){
return d[i]==d[j]?y[i]>y[j]:d[i]<d[j];
}
void solve(int l,int r){
static int L[MAXN],R[MAXN],cl,cr;
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid); solve(mid+1,r); S.Reset(); cl=cr=0;
for(int i=l;i<=mid;i++) if(!h[i][1]) L[++cl]=h[i][0];
for(int i=mid+1;i<=r;i++) if(h[i][1]) R[++cr]=h[i][0];
if(!cl||!cr) return;
sort(L+1,L+cl+1,cmp); sort(R+1,R+cr+1,cmp);
for(int i=1,j=1;i<=cr;i++){
while(j<=cl&&d[L[j]]<=d[R[i]]) S.Push(L[j]),j++;
g[R[i]]=min(g[R[i]],S.Query(R[i]));
}
}
int main(){
static int tmp[MAXN],tnt;
read(N); tmp[tnt=1]=0; ANS2=INFl;
for(int i=1;i<=N;i++) read(a[i]),tmp[++tnt]=d[i]=a[i]-i;
for(int i=1;i<=N;i++) read(b[i]);
sort(tmp+1,tmp+tnt+1);
tnt=unique(tmp+1,tmp+tnt+1)-tmp-1;
DT.Reset(tnt); int p=lower_bound(tmp+1,tmp+tnt+1,0)-tmp;
DT.Modify(p,0);
for(int i=1;i<=N;i++){
g[i]=INFl;
p=lower_bound(tmp+1,tmp+tnt+1,d[i])-tmp;
f[i]=DT.Query(p)+1; DT.Modify(p,f[i]);
}
ANS1=DT.Query(tnt);
for(int i=N;~i;i--) if(f[i]>=0) lk.Add(f[i],i);
for(int q=0,j,k;q<ANS1;q++){
cnt=0; j=lk.head[q]; k=lk.head[q+1];
while(~j||~k){
++cnt;
if(!~j) h[cnt][0]=k,h[cnt][1]=1,k=lk.nxt[k];
else if(!~k||j<k) h[cnt][0]=j,h[cnt][1]=0,j=lk.nxt[j];
else h[cnt][0]=k,h[cnt][1]=1,k=lk.nxt[k];
}//按序号排好序
solve(1,cnt);//分治
for(int i=lk.head[q+1];~i;i=lk.nxt[i]){
g[i]+=1ll*(i-1)*i/2+a[i]+b[i];
y[i]=g[i]-1ll*(i+1)*a[i]+1ll*i*(i+1)/2;
}
}
for(int i=0;i<=N;i++) if(f[i]==ANS1)
ANS2=min(ANS2,g[i]+1ll*(2*a[i]+N-i+1)*(N-i)/2);
printf("%d %lld",ANS1,ANS2);
return 0;
}