2007 Asia Regional Chengdu D题：David Shopping 原题链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3673涉及算法：
可修改堆+标记数组（后者不算算法……请勿鄙视）（大牛们都用STL过的，我手写优先队列。。。。蛋都碎了）
题目大意：
你有一个能放M(M <= 50000)个物品的容器，你可能会遇到N（N <= 100000)个物品。
规则：
1.遇到的物品K你如果之前没有遇到过，且你的容器未满，那么把这个物品（编号K），放进容器中，并记录数字1（相当于权值），且记录遇到该物品的时间t。
2.遇到的物品K如果在你的容器里，那么仅仅把它的标记数字（即所谓权值+1）。
3.遇到的物品K你如果之前没有遇到过，且你的容器已满，那么就把容器里标记数字最大的容器移除，如果不止一个，那么就把最先进入容器的那一个移除。（移除的物品就相当于没有遇到过，之后遇到算第一次遇到。）
求解问题：给你M，N，以及一行数字N个K(i)，（K（i）< 2^20,i = 1 to N)，输出共发生移除操作多少次。
（TimeLimit：1s） 算法：
模拟优先队列，实现O(Nlog(M))的时间复杂度的算法。
利用堆的性质，实现插入，删除，维持堆的性质操作均为O(logM)的复杂度。
利用外置标记数组，记录关键值对应元素在书中的位置，类似（计数排序）（或者说哈希表，或者说外部索引数组）的思想。（其实我觉得算是骗过去的。因为空间复杂度O(MAX(K(i)))。。。如果K(i)大一点，内存就爆了。。不过现场赛不卡内存，幸好幸好～ #include <iostream>
#include <cstdio>
#define left(x) (x << 1)
#define right(x) ((x << 1) + 1)
#define parent(x) (x >> 1)
using namespace std;
struct heap
{
int key,t,w;
} h[50005];//key为物品名K，t为入队时间，w为权值
int now,n,m,cnt,fuck[(1 << 21)],pick[100005];//now：初始插入位置，n,m:respectively，cnt:关键计数器，记录出队次数，f**k数组用于计数排序记录某元素在堆/队列中的位置
void init()//初始化
{
for(int i = 1;i <= n + 1;i++)
{
h[i].key = h[i].w = 0;//堆中元素权值为零
h[i].t = m + 1;//堆中元素入队时间均为最大时间值+1
}
}
void make(int i)//保持堆的性质，同时更新外部索引数组(O(h) = O(logM))
{
int large,l,r;
l = left(i);
r = right(i);
if(l <= n && (h[l].w > h[i].w || (h[l].w == h[i].w && h[l].t < h[i].t)))//同时对权值和时间进行对比，维持性质
large = l;
else
large = i;
if(r <= n && (h[r].w > h[large].w || (h[r].w == h[large].w && h[r].t < h[large].t)))
large = r;
if(large != i)
{
int tempp = fuck[h[i].key];//先交换外部索引数组中对应元素的位置，再维护堆的性质，保持实时更新
fuck[h[i].key] = fuck[h[large].key];
fuck[h[large].key] = tempp;
swap(h[i],h[large]);
make(large);
}
}
void insert(int key,int p,int t)//插入函数，先插入，通过now记录暂时的初始位置，再用保持堆的性质来维护堆且维护元素位置(O(h) = O(logM)，等价于维护堆性质的复杂度)
{
h[p].key = key;
h[p].t = t;
h[p].w = 1;
fuck[key] = p;
make(1);
now ++;
}
void insert2(int key,int t)//同时实现出队和入队操作。（此时为队列已满的情况）(O(h) = O(logM)，等价于维护堆性质的复杂度)
{
fuck[h[1].key] = -1;//一句话出队，哇卡卡～
fuck[key] = 1;
h[1].key = key;
h[1].t = t;
h[1].w = 1;
make(1);
}
int re(int i)//所谓的权值修护（堆的可修改性）(O(h) = O(logM)，等价于维护堆性质的复杂度)
{
bool mark = false;
int p = parent(i);//对于权值增加的堆元素，沿路向上，进行反向堆维护，从而使权值更改的元素达到正确的位置，方便之后重新进行维护堆的性质操作
if(p >= 1 && (h[p].w < h[i].w || (h[p].w == h[i].w && h[p].t > h[i].t)))
{
mark = true;
int tempp = fuck[h[i].key];
fuck[h[i].key] = fuck[h[p].key];
fuck[h[p].key] = tempp;
swap(h[i],h[p]);
return re(p);
}//重新堆维护的起始点，某祖先点，或者该点
if(mark)
return p;
else
return i;
}
void print()//这脑残函数是用来测试sample的。。帮了我大忙阿。。。其实大神们的调试都是各有风格的，而小菜们的调试，如我，都是类似的。。。
{
cout << endl;
for(int i = 1;i <= n;i++)
{
printf("h[%d] %d %d %d %d\n",i,h[i].key,h[i].w,h[i].t,fuck[h[i].key]);
}
}
int FIND(int key){return fuck[key];}//索引查找，一句话函数～
void solve()
{
now = 1;
cnt = 0;
int key,pos,Max = 0;
init();
for(int i = 1;i <= m;i++)//缓存读入，查找最大key值元素
{
scanf("%d",&pick[i]);
Max = (Max < pick[i]) ? pick[i] : Max;
}
for(int i = 0;i <= Max;i++)//通过key值元素的最大值，开适合大小的索引数组（节省内存和时间）
fuck[i] = -1;
for(int i = 1;i <= m;i++)
{
key = pick[i];
pos = FIND(key);//查找是否已入队
if(pos == -1)//新插
{
if(now > n)//已满
{
cnt ++;
insert2(key,i);
}
else//未满
insert(key,now,i);
}
else//已有
{
h[pos].w ++;
//WA POINT
make(re(pos));//可修改堆。。。之前一直忘记了这个根本。。。加了修改权值操作之后就过了。。蛋碎。。。。。
}
//print();
}
printf("%d\n",cnt);
}
int main()
{
int CAS = 1;
while(scanf("%d%d",&n,&m) != EOF && (n || m))
{
printf("Case %d: ",CAS++);
solve();
}
}
//小菜出品，欢迎大牛拍我。。。。