【算法】数学

【题解】

1.平均数：累加前缀和。//听说要向下取整？

2.中位数：双堆法，大于中位数存入小顶堆，小于中位数存入大顶堆，保证小顶堆内数字数量≥大顶堆，奇数则取小堆顶，偶数则取两堆顶/2。

3.方差=(平方的均值)-(均值的平方)，即对于a,b,c，s²=(a²+b²+c²)/3-((a+b+c)/3)²。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=1000010;multiset
           
            q2;//小顶堆 struct cmp{ bool operator() (const int a,const int b)const { return a>b;}};multiset
            
             q1;//大顶堆 int n,k,a[maxn],sum[maxn],tot1,tot2;long long sums[maxn];double ans2;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}void compair(){ if(tot1>tot2) { int now=*q1.begin();tot1--;//????????? q1.erase(q1.begin());//一定要删除指定位置，删除multiset中的键值会把全部键值等于的都删掉。 q2.insert(now);tot2++; } if(tot2-1>tot1) { int now=*q2.begin();tot2--; q2.erase(q2.begin()); q1.insert(now);tot1++; } if((tot1+tot2)%2) ans2=*q2.begin(); else ans2=1.0*(*q1.begin()+*q2.begin())/2;}int main(){ n=read(),k=read(); sum[0]=0;sums[0]=0; int tot=0,task=0; for(int i=1;i<=n;i++) { task=read(); if(task==1) { tot++; a[tot]=read(); if(tot>k) { if(a[tot-k]
             
              =ans2)q2.insert(a[tot]),tot2++; else q1.insert(a[tot]),tot1++; compair(); sums[tot]=sums[tot-1]+a[tot]*a[tot]; } else if(task==2) { if(tot