在我CTSC滚粗了之后,本来想天天喝点小酒消消愁的,结果发现还得去ZJOI day2,讲课也已经排好推不掉了…
于是我讲的是可持久化数据结构…
正好把以前想的一些例题贴出来:
1.QTREE的可持久化版本:修改一条边,询问2点间边的最大值,回到第i个操作结束的时候.必须在线
2.n*n的矩阵,每次询问一个子矩形内部第k大的数,n<=100,询问数<=1kw,时限5s.必须在线.
3.SUBSTRING的可持久化版本:给一个串,支持往后+个字符,询问一个串出现次数,回到第i个操作结束的时候,必须在线.
总长度<=20w,操作数<=10w,时限3s.
4.BZOJ 2787
嘛…有时间可以先看看…反正也很sb…到时候也会讲…
强力推荐可持久化KMP
个人觉得后缀自动机如果仍然使用原先的构造方法可持久化的话复杂度会退化…..
求解BZOJ2787的做法…………就是SPOJ COT4
回复fotile96：额…KMP可持久化了有啥用…或者说啥是可持久化KMP T_T
回复fotile96：我咋感觉KMP可持久化了之后就变AC自动机了??
回复WJBZBMR：没用..不过这玩意大概是可以的..
回复WJBZBMR：看毛皮此就花？
新主题真亮怎么不转百度新空间….
回复yaosiqiu：转了之后很多人不能回复了
回复yaosiqiu：看范围就知道不是后缀自动机吧…
回复19世纪30年代：我不是说了当习题到时候会讲么…
回复WJBZBMR：啊是我傻×了吗……
lverxivheszr