51nod 1785 数据流中的算法 【D(x)与E(x)+队列+线段树】

第一行是整数n与k，代表有n次操作，时间窗口大小为k。 （1 <= n <= 10^6， 1 <= k <= 100）接下来的n行，每行代表一次操作。操作有“用户访问”、“查询均值”、“查询方差”、“查询中位数”四种。每行的第一个数代表操作类型。操作数1：用户访问输入格式：<1, v>用户的满意度v为闭区间[0, 100]中的任意整数。用户每访问一次，数据更新，移动统计窗口。操作数2：查询均值输入格式：<2>统计窗口内的用户满意度的均值。操作数3：查询方差输入格式：<3>统计窗口内用户满意度的方差操作数4：查询中位数输入格式：<4>统计窗口内用户满意度的中位数p.s. 在有查询请求时，窗口保证不为空p.s.s. 有查询请求时，窗口可能不满Output
对于“查询均值”、“查询方差”、“查询中位数”操作的结果，输出保留两位小数。Input示例
12 31 11 21 32341 41 51 6234Output示例
2.000.672.005.000.675.00
首先说一下题意----k-应该理解为只能看到k个人的满意度（最后k个人了）
所以涉及到增加数据与删除数据----中位数可以用线段树来搞定-.-       引用  stdio.h确实比 引用 cstdio  要快几倍
代码：
#include<stdio.h>#include<string.h>#include<math.h>#include<queue>#include<algorithm>using namespace std;#define LL long longdouble he[2];int shu;struct node{int l,r,shu;}PP[300];void creat(int l,int r,int x){    PP[x].l=l;PP[x].r=r;    PP[x].shu=0;    if (l==r) return ;    int m=(l+r)>>1;    creat(l,m,x*2);    creat(m+1,r,x*2+1);}void add(int wei,int x){    PP[x].shu++;    if (PP[x].l==PP[x].r) return ;    int m=(PP[x].l+PP[x].r)>>1;    if (wei>m) add(wei,x*2+1);    else add(wei,x*2);}void jian(int wei,int x){    PP[x].shu--;    if (PP[x].l==PP[x].r) return ;    int m=(PP[x].l+PP[x].r)>>1;    if (wei>m) jian(wei,x*2+1);    else jian(wei,x*2);}int query(int ll,int x){    if (PP[x].l==PP[x].r)        return PP[x].l;    else if (PP[x*2].shu<ll)        query(ll-PP[x*2].shu,x*2+1);    else        query(ll,x*2);}int main(){/*    freopen("in1.txt","r",stdin);    freopen("out.txt","w",stdout);*/    queue<int> que;    int n,k;    scanf("%d%d",&n,&k);    int s=0,a,b;    shu=0;    creat(0,100,1);    while (n--)    {        scanf("%d",&a);        switch(a)        {            case 1:                if (shu==k)                {                    b=que.front();                    que.pop();                    he[0]-=b;                    he[1]-=b*b;                    jian(b,1);                }                else shu++;                scanf("%d",&b);                que.push(b);                he[0]+=b;he[1]+=b*b;                add(b,1);                break;            case 2:                PRintf("%d.00/n",((int)he[0])/shu);                break;            case 3:                printf("%.2lf/n",he[1]/shu-(he[0]/shu)*(he[0]/shu));                break;            case 4:                if (shu%2==0)                {                    a=query(shu/2,1);                    b=query(shu/2+1,1);                    printf("%.2lf/n",(a+b)/2.0);                }                else                {                    b=query(shu/2+1,1);                    printf("%.2lf/n",(double)b);                }                break;        }    }    return 0;}