Trancy

4月8日

在网上查着树上莫队,查着查着就变成了

树上莫队->莫队算法->序列上的莫队->块状数组

突然发现块状数组真是一个好东西

就是解决这样一个问题:
先给字符串s,后续后n个操作,在x位置插入一个字符,然后选问在某一个位置的字符是多少。

如果数据太大显然会超时,就是用到了块状数组。

我们设字符串的长度为n,把它分成若干个长度为根号n的链表,具体可以用队列阿什么的来实现,还有一个问题就是,如果我们在第一个块进行插入,第一个块就满了,就觉得方法就是,多出来的都往后面移一位,队列就很方便啊。

复杂度貌似是n*根号n??不会证明

评论