很久很久没空写博客了…这两天学了点分块和莫队,瞎jb写点..
分块
一个对于一些线段树之类无法解决的区间问题十分6的暴力算法.它的思想简单来说就是把一整个序列分成几块(一般为根号数列长度,不过也要视情况),然后维护每个块里的答案,当查询[l,r]时对于l和r所在区间暴力求解,再扫一遍l所在加一块到r所在减一块这些分出的块里的答案.这个操作显然可以看到是max(块大小,块数量)这个级别,因此取根号时就是根号的复杂度.再讲下修改,基本也是类似,暴力搞就行(也要视题目而定,有可能要O(n)来更新). 一个对于
