玄学问题求助
  • 板块P1471 方差
  • 楼主noocow
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/10/18 22:30
  • 上次更新2023/11/5 10:26:06
查看原帖
玄学问题求助
303230
noocow楼主2020/10/18 22:30
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') { 
    static short st[30];short tp=0;
    if(x<0) putchar('-'),x=-x;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar('0'|st[tp--]);
    putchar(ed);
}

#define FOR(i,a,n) for(int i=a;i<n;i++)
#define PFOR(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define RG register int
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define min(a,b) (((a)<(b))?(a):(b))      //如果参数中含有调用min或max的递归函数,请不要使用
#define max(a,b) (((a)>(b))?(a):(b))
#define abs(x) (((x)<0)?(-(x)):(x))
typedef vector<int> vt;
typedef long long ll;
using namespace std;
const int MAX=1e5+7;
const int INF=1e4;
const int mod=1e9+7;
ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}

int n,m;
double a[MAX],ans[MAX<<2],ans1[MAX<<2],tag[MAX<<2];
inline int ls(int x){
    return x<<1;
}
inline int rs(int x){
    return x<<1|1;
}
inline void push_up(int p){
    ans[p]=ans[ls(p)]+ans[rs(p)];    //维护,可更改
    ans1[p]=ans1[ls(p)]+ans1[rs(p)]; 
}
void build(int p,int l,int r){
    tag[p]=0;
    if(l==r){ans[p]=a[l];ans1[p]=a[l]*a[l];return ;}
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
inline void f(int p,int l,int r,double k){
    tag[p]=tag[p]+k;
    ans1[p]+=2*ans[p]*k+(r-l+1)*k*k;
    ans[p]=ans[p]+k*(r-l+1);       //更新
}
inline void push_down(int p,int l,int r){
    int mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(int nl,int nr,int l,int r,int p,double k){
    if(nl<=l&&r<=nr){      // [nl,nr] 为修改区间,[l,r] 为当前节点包含的区间,k为被修改的元素的变化量
        f(p,l,r,k);
        return ;
    }
    if (tag[p]&& l!=r) push_down(p,l,r);
    int mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
double query(int q_x,int q_y,int l,int r,int p){
    double res=0;
    if(q_x<=l&&r<=q_y)return ans[p];
    int mid=(l+r)>>1;
    if(tag[p]) push_down(p,l,r);
    if(q_x<=mid)res+=query(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
    return res;
}
double query1 (int q_x,int q_y,int l,int r,int p){
    double res=0;
    if(q_x<=l&&r<=q_y) return ans1[p];
    int mid=(l+r)>>1;
    if(tag[p]) push_down(p,l,r);
    if(q_x<=mid)res+=query1(q_x,q_y,l,mid,ls(p));
    if(q_y>mid) res+=query1(q_x,q_y,mid+1,r,rs(p));
    return res;
}
double query2 (int qx,int qy){      //方差
    double sum1=query1(qx,qy,1,n,1);
    double sum2=query(qx,qy,1,n,1);
    double ans=sum1/(qy-qx+1)-(sum2/(qy-qx+1))*(sum2/(qy-qx+1));   //ac
    return ans;    
}
double query3 (int qx,int qy){      //平均数
    double sum=query(qx,qy,1,n,1);
    return sum/(qy-qx+1);
}
//build(1,1,n);

int main(){                     //仔细看题!! a[i] 和 k 都是实数
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    int b,x,y;
    double k;
    for(int i=1;i<=m;i++){
        cin>>b;
        if(b==1){
            cin>>x>>y>>k;
            update(x,y,1,n,1,k);
        }
        else if(b==2){
            cin>>x>>y;
            cout<<fixed<<setprecision(4)<<query3(x,y)<<endl;
        }
        else if(b==3){
            cin>>x>>y;
            cout<<fixed<<setprecision(4)<<query2(x,y)<<endl;
        }
    }
    return 0;
}

其中query2部分写成下面 只能拿70分

double query2 (int qx,int qy){      
    double sum1=query1(qx,qy,1,n,1);
    double sum2=query(qx,qy,1,n,1);
    double ans=sum1/(qy-qx+1)-sum2*sum2/((qy-qx+1)*(qy-qx+1));//为什么是这里错误
    return ans;    
}

query2中所有数据都是double类型的

2020/10/18 22:30
加载中...