SPOJ 9887 – NWERC2011C – Movie collection

$1 \leq n, m \leq 10^5$ 意味着如果用数组模拟这个栈,数组的长度最大需要开到$2 \times 10^5$。这里的栈不同的是我们可以对中间的点进行操作,操作完之后需要统计一个前缀和。

所以假如我们把原始数据填入一个$n+m$长度的数组的尾部,维护每一个元素的位置以及“栈顶”的位置,每一次操作都把相应的位取出放到栈顶,接着用树状数组维护前缀和,就能实现这里的功能了。

 

说点什么

avatar
50
  Subscribe  
提醒