Description
箱子再分配问题需要解决如下问题：
（1）一共有N个物品，堆成M堆。
（2）所有物品都是一样的，但是它们有不同的优先级。
（3）你只能够移动某堆中位于顶端的物品。
（4）你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。
（5）求出将所有物品删除所需的最小步数。删除操作不计入步数之中。
（6）只是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：
不会有两个物品有着相同的优先级，且M=2
Input
第一行是包含两个整数N1,N2分别表示两堆物品的个数。
接下来有N1行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级，数字越大，优先级越高。
再接下来的N2行按照同样的格式给出了第二堆物品的优先级。
Output
对于每个数据，请输出一个整数，即最小移动步数。
Sample Input
3 3
1
4
5
2
7
3
1
4
5
2
7
3
Sample Output
6
解题思路：
决策已经很明显了，找到最大的，把上面的压到另外一堆里。
考虑splay维护一下。
还要开long long.
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define ls ch[0]
#define rs ch[1]
using std::swap;
const int N=;
typedef long long lnt;
struct data{
lnt Max_val;
lnt Where_is_Max_Val;
bool friend operator < (data x,data y)
{
return x.Max_val<y.Max_val;
}
lnt wp()
{
return Where_is_Max_Val;
}
};
struct trnt{
int ch[];
int fa;
int lzt;
lnt val;
data mxs;
lnt wgt;
}tr[N];
int siz;
int n1,n2;
int root1,root2;
int fst1,lst1;
int fst2,lst2;
lnt ans=;
lnt num[N];
data max(data a,data b)
{
if(a.Max_val<b.Max_val)
return b;
return a;
}
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void res(int spc)
{
tr[spc].wgt=;
tr[spc].mxs=(data){tr[spc].val,spc};
return ;
}
void pushup(int spc)
{
res(spc);
if(lll)
{
tr[spc].wgt+=tr[lll].wgt;
tr[spc].mxs=max(tr[spc].mxs,tr[lll].mxs);
}
if(rrr)
{
tr[spc].wgt+=tr[rrr].wgt;
tr[spc].mxs=max(tr[spc].mxs,tr[rrr].mxs);
}
return ;
}
void trr(int spc)
{
if(!spc)
return ;
tr[spc].lzt^=;
swap(lll,rrr);
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
trr(lll);
trr(rrr);
tr[spc].lzt=;
}
return ;
}
void recal(int spc)
{
if(tr[spc].fa)
recal(tr[spc].fa);
pushdown(spc);
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
return ;
}
int splay(int spc,int f)
{
recal(spc);
while(tr[spc].fa!=f)
{
int ft=tr[spc].fa;
if(tr[ft].fa==f)
{
rotate(spc);
break;
}
if(whc(spc)^whc(ft))
rotate(spc);
else
rotate(ft);
rotate(spc);
}
return spc;
}
void build(int &spc,int l,int r,int f)
{
if(l>r)
return ;
spc=++siz;
int mid=(l+r)>>;
tr[spc].fa=f;
tr[spc].val=num[mid];
res(spc);
build(lll,l,mid-,spc);
build(rrr,mid+,r,spc);
pushup(spc);
return ;
}
int fstfind(int spc)
{
while(lll)
spc=lll;
return spc;
}
int lstfind(int spc)
{
while(rrr)
spc=rrr;
return spc;
}
int maxmin(int spc)
{
pushdown(spc);
spc=lll;
pushdown(spc);
while(rrr)
{
spc=rrr;
pushdown(spc);
}
return spc;
}
int minmax(int spc)
{
pushdown(spc);
spc=rrr;
pushdown(spc);
while(lll)
{
spc=lll;
pushdown(spc);
}
return spc;
}
int lstmax(int spc)
{
pushdown(spc);
if(lll)
return maxmin(spc);
recal(spc);
while(whc(spc)==)
spc=tr[spc].fa;
return tr[spc].fa;
}
int main()
{
scanf("%d%d",&n1,&n2);
for(int i=;i<=n1;i++)
scanf("%lld",&num[n1-i+]);
build(root1,,n1+,);
fst1=fstfind(root1);
lst1=lstfind(root1);
for(int i=;i<=n2;i++)
scanf("%lld",&num[n2-i+]);
build(root2,,n2+,);
fst2=fstfind(root2);
lst2=lstfind(root2);
for(int i=;i<=n1+n2;i++)
{
root1=splay(fst1,);
splay(lst1,root1);
root2=splay(fst2,);
splay(lst2,root2);
int spc1,spc2;
spc1=tr[tr[root1].rs].ls;
spc2=tr[tr[root2].rs].ls;
if(tr[spc1].mxs<tr[spc2].mxs)
{
root2=splay(tr[spc2].mxs.wp(),);
splay(lst2,root2);
int tmp=tr[tr[root2].rs].ls;
tr[tr[root2].rs].ls=;
pushup(tr[root2].rs);
pushup(root2);
ans+=tr[tmp].wgt;
trr(tmp);
int temp=root2;
root2=splay(maxmin(temp),);
splay(minmax(temp),root2);
tr[tr[root2].rs].ls=;
pushup(tr[root2].rs);
pushup(root2);
root1=splay(lstmax(lst1),);
splay(lst1,root1);
tr[tr[root1].rs].ls=tmp;
tr[tmp].fa=tr[root1].rs;
pushup(tr[root1].rs);
pushup(root1);
}else{
root1=splay(tr[spc1].mxs.wp(),);
splay(lst1,root1);
int tmp=tr[tr[root1].rs].ls;
tr[tr[root1].rs].ls=;
pushup(tr[root1].rs);
pushup(root1);
ans+=tr[tmp].wgt;
trr(tmp);
int temp=root1;
root1=splay(maxmin(temp),);
splay(minmax(temp),root1);
tr[tr[root1].rs].ls=;
pushup(tr[root1].rs);
pushup(root1);
root2=splay(lstmax(lst2),);
splay(lst2,root2);
tr[tr[root2].rs].ls=tmp;
tr[tmp].fa=tr[root2].rs;
pushup(tr[root2].rs);
pushup(root2);
}
}
printf("%lld\n",ans);
return ;
}