1。首先求出在最终状态下，哪些格子中的数为0。将这些各自标记成0，其他各自标记成1。
2。记b[i]为在插入i之前，1..a[i]-1中已经有几个格子插入了数字。
3。愿问题转化为了pku2828。这里的b[i]对应pos[i],i对应vel[i]。
4。2828中的将1..n标记为1，已在（1）中完成。
2828题解：
{
Problem B: Buy Tickets

本题的算法是利用线段树（树状数组也可）进行倒推。基本思想是拿一个N个1的序列，从最后一次插入开始倒推。设当前插入的是Pos Val，那么找到从左边数第Pos + 1个1的位置就是最终需要插入Val的位置，然后把那个1改成0。
}

谁想看我的程序可以发邮件给我

• Re:这题可以只用树状数组完成！！ (47) notsure 2008-07-22 11:51:38