BZOJ 4896 [Thu Summer Camp2016] 补退选

发布于 2017-07-08  155 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4896

题意:n 个事件,每次可以:

  1. 插入一个串 S
  2. 删除一个串 S
  3. 最早在第几个事件之后,姓名以 S 为前缀的学生数量超过了某值

Trie 树的复杂度果然很搞笑 qwq

对每个点开 vector,记录第一次超过 i 的事件节点

然后就没了...

坑点:

有一处需要开 long long...

实测 loj 比 bzoj 快了四倍...

 


一个非常弱的准退役OIER