AC日记——数据流中的算法 51nod 1785

数据流中的算法

思路：

　　线段树模拟；

　　时间刚刚卡在边界上，有时超时一个点，有时能过；

来，上代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define maxn 1000005

int n,size,cnt,ai[maxn],L[maxn<<2],R[maxn<<2];
int mid[maxn<<2],dis[maxn<<2],to,x;

double sum[maxn<<2],sum2[maxn<<2];

inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0') Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}

void tree_build(int now,int l,int r)
{
    L[now]=l,R[now]=r;
    if(l==r) return ;
    mid[now]=l+r>>1;
    tree_build(now<<1,l,mid[now]);
    tree_build(now<<1|1,mid[now]+1,r);
}

void tree_add()
{
    int now=1,dis1=to*x,ss=to*dis1;
    while(L[now]!=R[now])
    {
        dis[now]+=x,sum[now]+=dis1,sum2[now]+=ss;
        if(to<=mid[now]) now=now<<1;
        else now=now<<1|1;
    }
    dis[now]+=x,sum[now]+=dis1,sum2[now]+=ss;
}

int tree_query(int k)
{
    int now=1;
    while(L[now]!=R[now])
    {
        if(k<=dis[now<<1]) now=now<<1;
        else k-=dis[now<<1],now=now<<1|1;
    }
    return L[now];
}

inline void out(int X)
{
    if(X>9) out(X/10);
    putchar(X%10+48);
}

int main()
{
    int now=0;in(n),in(size);
    int ty;tree_build(1,0,100);
    while(n--)
    {
        in(ty);
        if(ty==1)
        {
            in(ai[++now]);
            to=ai[now],x=1,tree_add();
            if(now>size) x=-1,to=ai[now-size],tree_add();
            continue;
        }
        if(ty==2)
        {
            double res=sum[1]/(double)dis[1];
            out((int)res),putchar('.'),putchar('0'),putchar('0'),putchar('
');
            continue;
        }
        if(ty==3)
        {
            double p=sum[1]/(double)dis[1];
            double res=(sum2[1]-sum[1]*2*p+p*p*dis[1])/dis[1];
            printf("%.2lf",res),putchar('
');
            continue;
        }
        if(ty==4)
        {
            int p=dis[1];
            if(p&1) out(tree_query((p>>1)+1)),putchar('.'),putchar('0'),putchar('0'),putchar('
');
            else printf("%.2f",(double)(tree_query(p>>1)+tree_query((p>>1)+1))/2.0),putchar('
');
        }
    }
    return 0;
}