玄关,为什么会爆 long long?
查看原帖
玄关,为什么会爆 long long?
1255837
Liyanxi1028楼主2025/1/26 16:52

我代码中 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
2025/1/26 16:52
加载中...