萌新刚学线段树75分求助!!!
  • 板块P2122 还教室
  • 楼主罗小菜
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/21 13:06
  • 上次更新2023/10/28 03:12:39
查看原帖
萌新刚学线段树75分求助!!!
483252
罗小菜楼主2022/4/21 13:06

都开到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;
}
2022/4/21 13:06
加载中...