https://cn.vjudge.net/problem/HDU-4027
这个题，本身并没有用到区间修改的什么操作。。如果不加优化就基本可以认为是单点修改区间查询的线段树，但是int64的最大值也只需要6次开根号就会收敛到1，因此我们可以加一个优化就是当子区间每一个都是1的话就不再更新区间（就这一个优化真的可以搞定吗。。。）其他的都跟普通的线段树一样了，只不过初始化建树的时候需要一个单独的点修改函数来操作。
继续阅读“[线段树][优化][特征分析] HDU 4027 Can you answer these queries?”
一开始脑子里总是想今天听讲时候的set，可是怎么也想不出来这个怎么用set做。然后又以为必须离线因为1e7 ,可是后来发现给了500mb内存。。。就愉快的离线了。离线的话可以从后往前单调队列。坑点一个是运算中间结果long long，另外一个是我自己手残，单调队列的尾指针用了r，和参数r重合然后把他覆盖了。。。。这是最傻的一次错误了吧。。。
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”
题意问给出一个序列然后q个询问问[l,r]之间有多少种不同的数。这里最简单的思想就是用可持久化线段树，每加入一个点作为一个版本，然后如果某一个点之前出现过那么就在新版本里把那个位置点的计数-1，再把现在这个位置+1，这样的话要求[l,r]中的数字有多少种那就只需要对第r个版本的线段树求[l,r]之间的和就行了，思路并不复杂（毕竟入门题 继续阅读“[算法学习] 可持久化线段树基础题 SPOJ D-query”
终于要搞可持久化数据结构了
在综合看了了n个大犇的博客和clj的论文之后总算是写了第一道可持久化线段树的题目。话说SCU真的很严格，这个代码在其他地方都过了就是在SCU上TLE。。。所以这个更快版本的今天先放着以后搞出来再说。。。
其实思路倒也不是很复杂，首先说求[1,n]的第k大。 继续阅读“[算法学习] 可持久化线段树基础题 K-th Number”
