我代码中 3 操作计算未约分分子分母的代码:
cin>>x>>y; int sz=y-x+1;
ans1=get_ph(1,x,y)*sz-pow(get_h(1,x,y),2);
ans2=sz*sz;
其中 ans1 是分子,ans2 是分母,get_h 计算区间和,get_ph 计算区间平方和。这样写会 70pts WA。然而换成
cin>>x>>y; int sz=y-x+1;
ans1=get_ph(1,x,y)*sz-get_h(1,x,y)*get_h(1,x,y);
ans2=sz*sz;
就会 AC。请问是为什么?是关于 pow
的特性吗?完整代码:
#include<bits/stdc++.h>
#define int long long
#define db long double
#define Pii pair<int,int>
#define x first
#define y second
#define f(x,y) fixed<<setprecision(y)<<x
#define idl (id<<1)
#define idr ((id<<1)|1)
using namespace std;
const int N=1e5+10;
int n,m,p[N];
struct node{int L,R,sz,lazy,h,ph;}tr[N*4];
inline void down(int id)
{
if(!tr[id].lazy) return;
int k=tr[id].lazy;
tr[idl].lazy+=k;
tr[idl].ph+=2*k*tr[idl].h+tr[idl].sz*k*k;
tr[idl].h+=k*tr[idl].sz;
tr[idr].lazy+=k;
tr[idr].ph+=2*k*tr[idr].h+tr[idr].sz*k*k;
tr[idr].h+=k*tr[idr].sz;
tr[id].lazy=0;
}
inline void up(int id)
{
tr[id].h=tr[idl].h+tr[idr].h;
tr[id].ph=tr[idl].ph+tr[idr].ph;
}
inline void build(int id,int l,int r)
{
tr[id].L=l; tr[id].R=r; tr[id].lazy=0; tr[id].sz=r-l+1;
if(l==r) {tr[id].h=p[l]; tr[id].ph=p[l]*p[l]; return;}
int mi=l+r>>1;
build(idl,l,mi); build(idr,mi+1,r); up(id);
}
inline void update(int id,int l,int r,int k)
{
if(tr[id].L>r||tr[id].R<l) return;
if(l<=tr[id].L&&tr[id].R<=r)
{
tr[id].lazy+=k;
tr[id].ph+=2*k*tr[id].h+tr[id].sz*k*k;
tr[id].h+=k*tr[id].sz;
return;
}
down(id); update(idl,l,r,k); update(idr,l,r,k); up(id);
}
inline int get_h(int id,int l,int r)
{
if(tr[id].L>r||tr[id].R<l) return 0;
if(l<=tr[id].L&&tr[id].R<=r) return tr[id].h;
down(id); return get_h(idl,l,r)+get_h(idr,l,r);
}
inline int get_ph(int id,int l,int r)
{
if(tr[id].L>r||tr[id].R<l) return 0;
if(l<=tr[id].L&&tr[id].R<=r) return tr[id].ph;
down(id); return get_ph(idl,l,r)+get_ph(idr,l,r);
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m; int op,x,y,k,ans1,ans2;
for(int i=1;i<=n;++i) cin>>p[i];
build(1,1,n);
while(m--)
{
cin>>op>>x>>y; int sz=y-x+1;
if(op==1) cin>>k,update(1,x,y,k);
else if(op==2) ans1=get_h(1,x,y),ans2=sz;
else ans1=get_ph(1,x,y)*sz-get_h(1,x,y)*get_h(1,x,y),ans2=sz*sz;
if(op>1)
{
if(ans1==0) {cout<<"0/1\n"; continue;}
k=__gcd(ans1,ans2);
ans1=ans1/k; ans2=ans2/k;
cout<<ans1<<"/"<<ans2<<"\n";
}
}
return 0;
}
//update=ph+2k*h+n*k^2
//ans=ph/n-(h/n)^2