今日主要复习&学习了一些基本的数据结构：树状数组，线段树，单调队列，单调栈，并做了一些简单例题。
确实短小精悍。
能做的事情：
一道例题：
构造：右端点从小到大排序。每个数最后一次出现的位置记为1，其余为0。则区间和即为不同数个数。
实现：设置last数组，last[i]表示i上一次出现的位置。这样输入一个数就先删掉上一个，再把这一个变成1。
注意：离线处理，排序时要用结构体，多加一个输入编号。依次处理的时候只要直接赋值ans[输入编号]，最后依次输出即可。
总结：
树状数组基本到此为止，只要背模板直接套用即可。看起来并不需要精通原理。
最终还是用了wzk的风格，即每次只修改lazy，pushdown操作先修改当前节点，再将lazy下放到儿子。
三道例题：
注意：如果不同操作是用不同字母来代替的话，一定要按照%s字符串读入，不然会死的很惨……
总结：
线段树的题目每天都要做，明天找一下区间加减或修改+区间查询最大值的题目，一定要好好熟练pushdown怎么写，记得上次就是这道题调不出来，很难顶。
之后还有今天没写的题目，洛谷P2161。先按照自己的搜索写一下，之后再看看线段树染色的标解。
今天学了学这两个单调数据结构，真是神仙……
思路：用双端队列。队首元素可能需要维护，一般队首元素为答案。每次从队尾插入元素之前，先检验是否从头到尾是单调的，否则就从队尾弹出元素，直到单调时再插入元素。
复杂度：\(O(n)\)
能做的事情：
别的还在挖掘中……
一道例题：
若发现i<j&&a[i]>a[j]，如5 3，那么从最小值意义上讲，5已经毫无用处了，因此插入3之前就直接扔掉5。对最大值同理。
每次首先维护队首元素看是否在当前窗格内，否则弹出。之后从队尾插入元素时检验是否单调，到单调或空再插入。复杂度\(O(n)\)。
注意：POJ上stl慢的一批，听说数组模拟队列很好用，回头学一下。
原理和单调队列差不多，只不过这次是在栈上操作，而不是双端队列。每次弹入元素之前先检验是否单调，到单调或空再弹入。答案可能在弹出时进行计算。和单调队列一样，一般插入时还需要配上位置（编号）
能做的事情：
一道例题：
单调栈，弹出的时候，被弹元素右边第一个比他大的数就是待插入元素，减去相应编号即可。同样也是离线处理。
总结：
单调数据结构的用处在于，如果在维护东西的时候，有很多冗余元素，比如没用的5，那么就可以利用单调性，进行删除，方便得出答案。这部分的例题还有很多，明天把那几道经典题都做了。
今天还做了一个优先队列的，POJ2431卡车加油题。这个直接想到了，就不写了。主要还是贪心。
最近半个月拼了！
原文：https://www.cnblogs.com/diorvh/p/11973994.html