娃娃机
如果每个点坐标都已经确定，可以形式化的得到一个直接计算答案的式子。
[ans=10^6-y_0+(sum_{i=2}^nmax_y[min(x_i,x_{i-1}),max(x_i,x_{i-1})]-y_i-y_{i+1})+10^6-y_n
]
带中括号的表示区间最大值
化简一下可以得到
[2(10^6-sum y_i+(sum_{i=2}^nmax_y[min(x_i,x_{i-1}),max(x_i,x_{i-1})]))
]
考虑通过调制最大化这个式子
[sum y_i-(sum_{i=2}^nmax_y[min(x_i,x_{i-1}),max(x_i,x_{i-1})])
]
可以发现，对于每一个最大值，是可以独立的去讨论的，也就是说，考虑枚举最大值，那么可以得到跨过这个最大值的一些区间，对每个最大值可以独立统计。
于是问题转换成了可以对某个最大值的某些点+1,最大化 +1的个数-区间内存在+1的数的区间的个数。
再补集转换一下统计 +1的个数+区间内不存在+1的数的区间的个数
这样可以dp了，设(dp_i)表示从小到大对点排序第(i)个点钦定+1的最大值
[dp_i=max_{j<i}(dp_j+calc_{j+1,i-1}+1)
]
中间的(calc_{l,r})表示区间([l,r])完全覆盖的区间个数
这个转移可以拿线段树优化
总复杂度(O(nlog n))
Code:
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#define ll long long
using std::min;
using std::max;
const int N=1e6+10;
const int M=1e6;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int st[21][N],Log[N];
int qry(int l,int r)
{
if(l>r) std::swap(l,r);
int d=Log[r+1-l];
return max(st[d][l],st[d][r-(1<<d)+1]);
}
int n,dx[N],dy[N];
ll ans;
std::vector<int> pot[N],seg[N];
struct node
{
int l,r;
node(){}
node(int L,int R){l=L,r=R;}
bool friend operator <(node a,node b){return a.r<b.r;}
}bee[N];
int yuy[N];
int mx[N<<2],tag[N<<2];
#define ls id<<1
#define rs id<<1|1
void pushdown(int id)
{
if(tag[id])
{
tag[ls]+=tag[id];
mx[ls]+=tag[id];
tag[rs]+=tag[id];
mx[rs]+=tag[id];
tag[id]=0;
}
}
void ins(int id,int l,int r,int p,int d)
{
if(l==r){mx[id]=d;return;}
pushdown(id);
int mid=l+r>>1;
if(p<=mid) ins(ls,l,mid,p,d);
else ins(rs,mid+1,r,p,d);
mx[id]=max(mx[ls],mx[rs]);
}
void modi(int id,int l,int r,int p)
{
if(!p) return;
if(r==p)
{
++tag[id],++mx[id];
return;
}
pushdown(id);
int mid=l+r>>1;
if(p<=mid) modi(ls,l,mid,p);
else modi(ls,l,mid,mid),modi(rs,mid+1,r,p);
mx[id]=max(mx[ls],mx[rs]);
}
void build(int id,int l,int r)
{
mx[id]=tag[id]=0;
if(l==r) return;
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
}
void work(int x)
{
if(seg[x].empty())
{
ans=ans-pot[x].size();
return;
}
int n=1,m=0;
for(int i=0;i<pot[x].size();i++) yuy[++n]=dx[pot[x][i]];
std::sort(yuy+1,yuy+1+n);
for(int i=0;i<seg[x].size();i++)
{
int p=seg[x][i],l=dx[p-1],r=dx[p];
if(l>r) std::swap(l,r);
l=std::lower_bound(yuy+1,yuy+1+n,l)-yuy;
r=std::upper_bound(yuy+1,yuy+1+n,r)-yuy-1;
bee[++m]=node(l,r);
}
std::sort(bee+1,bee+1+m);
build(1,1,n);
int j=1;
for(int i=1;i<n;i++)
{
while(j<=m&&bee[j].r==i) modi(1,1,n,bee[j++].l-1);
ins(1,1,n,i+1,mx[1]+1);
}
while(j<=m&&bee[j].r==n) modi(1,1,n,bee[j++].l-1);
ans-=1ll*(mx[1]-m);
}
int main()
{
read(n);
for(int i=1;i<=n;i++) read(dx[i]),read(dy[i]),++dx[i],pot[dy[i]].push_back(i);
for(int i=1;i<=n;i++) st[0][dx[i]]=dy[i];
for(int i=2;i<=M;i++) Log[i]=Log[i>>1]+1;
for(int j=1;j<=20;j++)
for(int i=1;i<=M+1-(1<<j)+1;i++)
st[j][i]=max(st[j-1][i],st[j-1][i+(1<<j-1)]);
ans=M-dy[1];
for(int i=2;i<=n;i++)
{
int mx=qry(dx[i-1],dx[i]);
ans=ans+mx-dy[i];
seg[mx].push_back(i);
}
for(int i=0;i<=M;i++)
work(i);
printf("%lld
",2ll*ans);
return 0;
}
2019.3.23