[STL+输入输出挂]数据流中的算法 - 众数 51Nod - 1786

数据流统计功能上线后，为51nod提升用户体验做出了很大的贡献。但是新问题随之而来，夹克老爷还想知道在一个窗口内，访问次数最多用户（即窗口内的众数）。如果有多个众数，取用户ID最小的一个。（窗口的意思是一个固定长度的区间！）

（因为数据流是实时的、在线的，所以不允许使用离线算法^_^）
Input
第一行为整数n, k。(1 <= n <= 5 * 10^6，1 <= k <= 1000）
n代表有多少次操作，k代表窗口大小。

接下来的n行，每行代表一次操作。每行第一个整数为操作数。

操作数1：用户访问
输入格式: <1, id>
用户ID为
0,IN
T
M
AX
0,INTMAX
闭区间内的整数。代表拥有此ID的用户对网站进行了一次访问，窗口进行相应移动。

操作数2：询问众数
输入格式：<2>
输出窗口内的众数，如果有多个，输出ID最小的那个。

p.s. 对于询问众数的操作，窗口保证不空
p.s.s. 对于询问众数的操作，窗口可能不满
Output
对于询问众数的操作，每行输出一个整数。
Sample Input
10 5
1 2
1 1
1 2
1 1
1 2
1 1
2
1 3
1 3
2

这题被学长说 水……
然而 我超时和wa能玩一年。。。。
ps 输入输出挂+个别STL居然还能那样写 也是精了orz

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <list>
using namespace std;
typedef long long ll;

const int maxn=10000000;
int n,k;

struct node{
    int id,cnt;
    friend bool operator <(node a,node b){
        return a.id<b.id||a.id==b.id&&a.cnt>b.cnt;
    }
};

set<node> cid;
map<int,int> idcnt;

int read()
{
    char ch=' ';
    int ans=0;
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch<='9' && ch>='0')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
void out(int a)
{
    if(a > 9)
    {
        out(a/10);
    }
    putchar(a%10 + '0');
}

int main(){
        n=read();
        k=read();
        queue<int> que;
        int cmd,id,pos=0;
        for(int i=0;i<n;i++){
            cmd=read();
            if(cmd==1){
                id=read();
                que.push(id);
                idcnt[id]++;
                pos++;
                cid.insert(node{id,idcnt[id]});
                if(pos>k){
                    pos--;
                    int t=que.front();  que.pop();
                    cid.erase(node{t,idcnt[t]});
                    idcnt[t]--;
                    if(idcnt[t]!=0){
                        cid.insert(node{t,idcnt[t]});
                    }               
                }
            }
            else{
                int ansp,tmp=0;
                set<node>::iterator it;
                it=cid.begin();
                ansp=(*it).id;
                /* for(it=cid.begin();it!=cid.end();it++){ int cids=*it; if(idcnt[cids]>tmp){ ansp=cids; tmp=idcnt[cids]; } } */
                out(ansp);
                printf("\n");
            }
        }
    return 0;
}