码农场
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 题解《挑战程序设计竞赛》