P3103 [USACO14FEB] Airplane Boarding G
想象一下飞机有N个座位，N个座位相当于数轴上的1至N共N个整点，第1个座位在整点1处，第2个座位在整点2处，……第N个座位在整点N处。
有N个奶牛排好队，要登陆坐飞机，第N头奶牛在数轴的整点0处，第N−1头奶牛在数轴的整点−1处，……第1头奶牛在数轴的整点−N+1处。第i头奶牛的座位号是Si。注意：每头奶牛都有唯一的一个座位，不会出现多头奶牛有相同的座位号。
在每一秒钟，奶牛会向右移动一步到达下一个整点，前提是没有奶牛挡住它。 当第i头奶牛到达它的座位Si时，它需要花费Ti秒去把行李放到头顶的行李架上，然后坐到自己的位置上，在此过程中，由于飞机通道很窄，所以在第i头奶牛坐到自己座位之前，在它左边的所有奶牛都不能动，要等奶牛i放好行李坐好后才能动。
现在的问题是，至少要多少秒之后，所有的奶牛都能做到自己的座位上？
\(N \le2*10^5\)
Solution:
妙妙平衡树思维题，感觉可以入选我写过的的十佳题目了。
我们将点 \(i\) 的起点定义为 \(pos_i\)
首先我们很难不想到我们应该按照时间的顺序，也就是输入顺序的倒序来写这题，然后我们仔细思考一下就会发现其实答案由两部分组成：
从起点到终点的距离加上放行李的时间\(s_{i}-pos_{i}+t_{i}\) 和被挡路的时间 \(tim\).
前一半的答案是固定的，所以我们要做的是如何快速的统计一个点总共会被挡多久的路。
那么什么样的点 \(j\) 会挡当前点 \(i\) 的路呢？
首先要满足的肯定是 $pos_i<pos_j $ \(s_i<s_j\)
然后就是 \(\forall k\in[i+1,j] tim_j>tim_k\)
也就是说，如果一个点 \(j\) 出发的比当前点 \(i\) 早且，而且它被挡路的时间 \(tim_j>tim_{max}\) 它才有可能挡住点 \(j\) 及其后序节点(按时间顺序)的路。所以我们要将那些不满足 \(tim_j>tim_i\) 的点全部删除。这样我们就能保证在数据结构内的点全部都是满足有可能挡住 \(i\) 的。然后每个点的到达时间显然就是该数据结构内的最大值\(tim_{max}\) 加上前半部分的时间 \(s_i+pos_i+t_i\).
然后我们发现我们要维护一种数据结构，单点插入，区间删除，查询区间最大值.那就是平衡树了
然后这题就做完了
Code:
#include<bits/stdc++.h>
const int N=2e5+5;
using namespace std;
int rd(){return rand()*17+rand()*rand()+1;}
inline int Max(int x,int y){return x>y ? x : y;}
struct FHQ_Treap{
int cnt=0;
struct Tree{
int ls,rs,x,y,ans,tag,pri;
}t[N<<2];
int Node(int x,int y)
{
t[++cnt]={0,0,x,y,y,0,rd()};
return cnt;
}
void push(int x,int k){t[x].x-=k;t[x].y+=k,t[x].ans+=k,t[x].tag+=k;}
void pushdown(int x)
{
if(!t[x].tag)return;
if(t[x].ls)push(t[x].ls,t[x].tag);
if(t[x].rs)push(t[x].rs,t[x].tag);
t[x].tag=0;
}
void pushup(int x)
{
if(!x)return;
t[x].ans=t[x].y;
if(t[x].ls)t[x].ans=Max(t[x].ans,t[t[x].ls].ans);
if(t[x].rs)t[x].ans=Max(t[x].ans,t[t[x].rs].ans);
return ;
}
void splite_pos(int x,int &a,int &b,int k)
{
if(!x){a=b=0;return;}
pushdown(x);
if(k>=t[x].x) {a=x;splite_pos(t[x].rs,t[x].rs,b,k);}
if(k<t[x].x){b=x;splite_pos(t[x].ls,a,t[x].ls,k);}
pushup(x);
}
void splite_val(int x,int &a,int &b,int k)
{
if(!x){a=b=0;return;}
pushdown(x);
if(k>=t[x].y) {a=x;splite_val(t[x].rs,t[x].rs,b,k);}
if(k<t[x].y){b=x;splite_val(t[x].ls,a,t[x].ls,k);}
pushup(x);
}
int merge(int x,int y)
{
if(!x||!y)return x|y;
pushdown(x);pushdown(y);
if(t[x].pri<t[y].pri)
{
t[x].rs=merge(t[x].rs,y);
pushup(x);return x;
}
else
{
t[y].ls=merge(x,t[y].ls);
pushup(y);return y;
}
}
}T;
int s[N],t[N];
int n,rt,ans=0;
void work()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
rt=T.Node(0,0);
for(int i=1;i<=n;i++)
{
cin>>s[i]>>t[i];
}
int a,b,c,tmp;
for(int i=n;i;i--)
{
T.splite_pos(rt,a,b,s[i]);
tmp=T.t[a].ans+s[i]+t[i];
ans=Max(ans,tmp);
T.push(a,1);
T.splite_val(b,b,c,tmp-s[i]+1);
rt=T.merge(a,T.merge(T.Node(s[i],tmp-s[i]+1),c));
}
cout<<ans;
}
int main()
{
//freopen("P3103.in","r",stdin);freopen("P3103.out","w",stdout);
work();
return 0;
}