都开到5e7了还是re,应该不是数据范围原因。
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=5e7;
#define int long long
struct node
{
int sum1,sum2;
}tree[MAXN];
int tag[MAXN];
inline int gcd(int x,int y)
{
if(x%y==0) return y;
else return gcd(y,x%y);
}
int n,m;
inline void push_down(int rt,int l,int r)
{
int len=(r-l+1);
tree[rt].sum2+=(2*tag[rt]*tree[rt].sum1+tag[rt]*tag[rt]*len);
tree[rt].sum1+=(len*tag[rt]);
tag[rt*2]+=tag[rt];
tag[(rt*2)|1]+=tag[rt];
tag[rt]=0;
return ;
}
inline void push_up(int rt,int l,int r)
{
int mid=(l+r)/2;
push_down(rt,l,r);
push_down(rt*2,l,mid);
push_down((rt*2)|1,mid+1,r);
tree[rt].sum1=tree[rt*2].sum1+tree[(rt*2)|1].sum1;
tree[rt].sum2=tree[rt*2].sum2+tree[(rt*2)|1].sum2;
return ;
}
void update(int rt,int l,int r,int L,int R,int x)
{
push_down(rt,l,r);
int mid=(l+r)/2;
if(L<=l && r<=R)
{
tag[rt]+=x;
return ;
}
if(L<=mid) update(rt*2,l,mid,L,R,x);
if(R>mid) update((rt*2)|1,mid+1,r,L,R,x);
push_up(rt,l,r);
return ;
}
node query(int rt,int l,int r,int L,int R)
{
push_down(rt,l,r);
int mid=(l+r)/2;
if(L<=l && r<=R) return tree[rt];
node res;
res.sum1=0;
res.sum2=0;
if(L<=mid)
{
node t=query(rt*2,l,mid,L,R);
res.sum1+=t.sum1;
res.sum2+=t.sum2;
}
if(R>mid)
{
node t=query((rt*2)|1,mid+1,r,L,R);
res.sum1+=t.sum1;
res.sum2+=t.sum2;
}
return res;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
update(1,1,n,i,i,x);
}
for(int i=1;i<=m;i++)
{
int op,l,r;
cin>>op>>l>>r;
if(op==1)
{
int d;
cin>>d;
update(1,1,n,l,r,d);
}
if(op==2)
{
node ans=query(1,1,n,l,r);
if(ans.sum1==0) cout<<"0/1\n";
else
{
int v=gcd(ans.sum1,r-l+1);
cout<<ans.sum1/v<<"/"<<(r-l+1)/v<<"\n";
}
}
if(op==3)
{
node ans=query(1,1,n,l,r);
int len=(r-l+1);
int so=(ans.sum2*len-ans.sum1*ans.sum1);
int v=gcd(len*len,(ans.sum2*len-ans.sum1*ans.sum1));
if(so==0) cout<<"0/1\n";
else cout<<so/v<<"/"<<len*len/v<<"\n";
}
}
return 0;
}