FIMO序列:对空序列执行如下十种操作:
0、将x插入序列尾部,同一个x只出现一次
1、删除中点元素并输出该元素
2、输出前半段的最小元素
3、输出后半段的最小元素
4、假设重复2和1,输出属于{2的输出}且属于{初始状态前半段的元素}中的第i小的元素
5、假设重复3和1,输出属于{3的输出}且属于{初始状态后半段的元素}中的第i小的元素
6、输出前半段的最大元素
7、输出后半段的最大元素
8、假设重复2和1,输出属于{2的输出}且属于{初始状态前半段的元素}中的第i大的元素
9、假设重复3和1,输出属于{3的输出}且属于{初始状态后半段的元素}中的第i大的元素
4.4常用技巧精选(二)
双端队列
这是对双端队列的终极应用,因为一下子用了6个……
题目怪长的,还是举例说明比较快。日本人的英文跟中国人的英文半斤八两,都难以理解,只能看日语原文去揣摩。
拿31那个case举例如下
query | fh.data|sh.data | fh.MIN|sh.MIN | fh.MAX|sh.MAX | output |
0 6 | 6 | | 6 | | 6 | | |
0 2 | 6 | 2 | 6 | 2 | 6 | 2 | |
0 3 | 6 2 | 3 | 6 2 | 3 | 6 | 3 | |
0 4 | 6 2 | 3 4 | 6 2 | 3 4 | 6 | 4 | |
0 5 | 6 2 3 | 4 5 | 6 2 | 4 5 | 6 | 5 | |
0 1 | 6 2 3 | 4 5 1 | 6 2 | 1 | 6 | 5 1 | |
0 8 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | |
4 1 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 2 |
4 2 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 6 |
5 1 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 1 |
5 2 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 8 |
2 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 2 |
3 | 6 2 3 4 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 1 |
1 | 6 2 3 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 4 |
2 | 6 2 3 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 2 |
3 | 6 2 3 | 5 1 8 | 6 2 | 1 8 | 6 | 8 | 1 |
1 | 6 2 5 | 1 8 | 6 2 | 1 8 | 6 | 8 | 3 |
2 | 6 2 5 | 1 8 | 6 2 | 1 8 | 6 | 8 | 2 |
3 | 6 2 5 | 1 8 | 6 2 | 1 8 | 6 | 8 | 1 |
1 | 6 2 | 1 8 | 6 2 | 1 8 | 6 | 8 | 5 |
2 | 6 2 | 1 8 | 6 2 | 1 8 | 6 | 8 | 2 |
3 | 6 2 | 1 8 | 6 2 | 1 8 | 6 | 8 | 1 |
1 | 6 1 | 8 | 6 1 | 8 | 6 | 8 | 2 |
2 | 6 1 | 8 | 6 1 | 8 | 6 | 8 | 1 |
3 | 6 1 | 8 | 6 1 | 8 | 6 | 8 | 8 |
1 | 6 | 8 | 6 | 8 | 6 | 8 | 1 |
2 | 6 | 8 | 6 | 8 | 6 | 8 | 6 |
3 | 6 | 8 | 6 | 8 | 6 | 8 | 8 |
1 | 8 | | 8 | | 8 | | 6 |
2 | 8 | | 8 | | 8 | | 8 |
1 | | | | | | | 8 |
将序列分为前半段和后半段,每部分都用双端队列维护原始数据data,最小值MIN和最大值MAX。
观察样例
Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}. {6,2,3,4,5,1,8} The minimum element in the first half of the sequence is 2. {6,2,3,5,1,8} The minimum element in the first half of the sequence is 2. {6,2,5,1,8} The minimum element in the first half of the sequence is 2. {6,2,1,8} The minimum element in the first half of the sequence is 2. {6,1,8} The minimum element in the first half of the sequence is 1. {6,8} The minimum element in the first half of the sequence is 6. {8} The minimum element in the first half of the sequence is 8. {} The first half of the sequence is empty. For the initial state, {6,2,3,4} is the first half of the sequence. 2 and 6 become the minimum element of the first half of the sequence. In this example, the 1-st minimum element is 2 and the 2-nd is 6.
由于操作1总是删除前半段的尾部,查询其最小值。如果尾部能被输出,它必须是整个前半段的最小元素。又因为要查询第i小,所以MIN是一个单调减的队列,仅需要在尾部插入时检查新元素是否比尾部小,小就插入,否则丢弃。同理维护MAX。
而后半段就不一样了
Assume that deletion will be repeated to the sequence {6,2,3,4,5,1,8}. {6,2,3,4,5,1,8} The minimum elemets in the latter half of the sequence is 1. {6,2,3,5,1,8} The minimum elemets in the latter half of the sequence is 1. {6,2,5,1,8} The minimum elemets in the latter half of the sequence is 1. {6,2,1,8} The minimum elemets in the latter half of the sequence is 1. {6,1,8} The minimum elemets in the latter half of the sequence is 8. {6,8} The minimum elemets in the latter half of the sequence is 8. {8} The latter half of the sequence is empty. {} The latter half of the sequence is empty. For the initial state, {5,1,8} is the latter half of the sequence. 1 and 8 becomes the minimum element of the latter half ot the sequence. In this example, the 1-st minimum element is 1 and the 2-nd is 8.
由于操作1执行后,后半段可能失去首部(转让成为前半段的尾部),如果首部能被输出,它必须是整个后半段的最小元素。又因为要查询第i小,所以MIN是一个单调增的队列,在尾部插入时要弹出所有比新元素大的既存元素。同理维护MAX。
#include <iostream> #include <deque> using namespace std; struct FIMO_sequence { struct first_half { deque<int> data; deque<int> MAX, MIN; /** * 添加到尾部 * @param x */ void add(int x) { data.push_back(x); if (data.size() == 1) { MAX.push_back(x); MIN.push_back(x); } else { if (MAX.back() < x) { MAX.push_back(x); } if (MIN.back() > x) { MIN.push_back(x); } } } /** * 从尾部删除 * @return */ int remove() { int x = data.back(); data.pop_back(); if (MIN.back() == x) MIN.pop_back(); if (MAX.back() == x) MAX.pop_back(); return x; } int size() const { return data.size(); } } fh; struct second_half { deque<int> data; deque<int> MAX, MIN; /** * 添加到尾部 * @param x */ void add(int x) { data.push_back(x); if (data.size() == 1) { MAX.push_back(x); MIN.push_back(x); } else { while ((!MAX.empty()) && MAX.back() < x) { MAX.pop_back(); } while ((!MIN.empty()) && MIN.back() > x) { MIN.pop_back(); } MAX.push_back(x); MIN.push_back(x); } } /** * 删除首部元素 * @return */ int remove() { int x = data.front(); data.pop_front(); if (MIN.front() == x) MIN.pop_front(); if (MAX.front() == x) MAX.pop_front(); return x; } int size() const { return data.size(); } } sh; int size() { return sh.size() + fh.size(); } void add(int x) { sh.add(x); if (sh.size() > fh.size()) { fh.add(sh.remove()); } } int remove() { int r = fh.remove(); if (sh.size() > fh.size()) { fh.add(sh.remove()); } return r; } /** * 前半段第i小 * @param i * @return */ int min_fh(int i) { return *(fh.MIN.end() - i); } /** * 后半段第i小 * @param i * @return */ int min_sh(int i) { return *(sh.MIN.begin() + i - 1); } /** * 前半段第i大 * @param i * @return */ int max_fh(int i) { return *(fh.MAX.end() - i); } /** * 后半段第i大 * @param i * @return */ int max_sh(int i) { return *(sh.MAX.begin() + i - 1); } }; int main() { while (true) { int q; scanf("%d", &q); if (q == 0) break; FIMO_sequence fimo; for (int i = 0; i < q; i++) { int qt, t; scanf("%d", &qt); switch (qt) { case 0: scanf("%d", &t); fimo.add(t); break; case 1: printf("%d\n", fimo.remove()); break; case 2: printf("%d\n", fimo.min_fh(1)); break; case 3: printf("%d\n", fimo.min_sh(1)); break; case 4: scanf("%d", &t); printf("%d\n", fimo.min_fh(t)); break; case 5: scanf("%d", &t); printf("%d\n", fimo.min_sh(t)); break; case 6: printf("%d\n", fimo.max_fh(1)); break; case 7: printf("%d\n", fimo.max_sh(1)); break; case 8: scanf("%d", &t); printf("%d\n", fimo.max_fh(t)); break; case 9: scanf("%d", &t); printf("%d\n", fimo.max_sh(t)); break; } } puts("end"); } return 0; }
Reference
http://d.hatena.ne.jp/k_operafan/20110925/1316916422
知识共享署名-非商业性使用-相同方式共享:码农场 » AOJ 1070 FIMO sequence 题解《挑战程序设计竞赛》