比赛 树形数据结构拔高 评测结果 AAAAAAAAAA
题目名称 高速公路 最终得分 100
用户昵称 李奇文 运行时间 0.796 s
代码语言 C++ 内存使用 9.03 MiB
提交时间 2025-04-17 21:59:11
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
/*typedef long long ll;
const int Maxn=1e5+5;
struct tree {
	ll l,r,tb,lazy;
} f[Maxn*4];
ll n,m;
ll gcd(ll x,ll y){
    if(y==0){
		return x;
	}
    return gcd(y,x%y);
}
void pushup(ll p){
	f[p].tb=f[p*2].tb+f[p*2+1].tb;
}
void pushdown(ll p){
	if(!f[p].lazy){
		return;
	}else{
		ll lp=p*2,rp=p*2+1;
		f[lp].lazy+=f[p].lazy;
		f[rp].lazy+=f[p].lazy;
		ll mid=(f[p].l+f[p].r)>>1;
		f[lp].tb+=(mid-f[p].l+1)*f[p].lazy;
		f[rp].tb+=(f[p].r-mid)*f[p].lazy;
		f[p].lazy=0;
	}
	return;
}
void build(ll p,ll l,ll r) { 
	f[p].l=l,f[p].r=r;
	if(l==r) {
		f[p].tb=0;
		return;
	}
	ll mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
	return;
}
ll query(ll p,ll x,ll y){
	if(x<=f[p].l&&f[p].r<=y) {
		return f[p].tb;
	}
	pushlazy(p);
	ll mid=(f[p].l+f[p].r)/2,sum=0;
	if(x<=mid) {
		sum+=ptt(p*2,x,y);
	}
	if(mid<y) {
		sum+=ptt(p*2+1,x,y);
	}
	return sum;
}
void change(ll p,ll l,ll r,ll k){
	if(l<=f[p].l&&f[p].r<=r){
		f[p].lazy+=k;
		f[p].tb+=(f[p].r-f[p].l+1)*k;
		return;
	}else{
		pushlazy(p);
		ll mid=(f[p].l+f[p].r)/2;
		if(l<=mid) change(p*2,l,r,k);
		if(mid<r) change(p*2+1,l,r,k);
		f[p].tb=f[p*2].tb+f[p*2+1].tb;
	}
	return;
}
void solve(int i,int j){
	ll fz,fm,ac=j-i;
	fm=(ac+1)*ac/2;
	
	printf("%lld/%lld",);
}
int main(){
	scanf("%lld%lld",&n,&m);
	build(1,1,n-1);
	while(m--){
		char op;
		ll l,r;
		scanf("%c%lld%lld",&op,&l,&r);
		if(op=='C'){
			ll v;
			scanf("%d",&v);
			change(1,l,r,k);
		}else{
			solve(l,r);
		}
	}
	return 0;
}*/
typedef long long ll;
const int N=100010;
int n,m;
ll cnt[N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
struct node
{
	ll sum,ans,lans,rans;
	int tag,len;
}tr[N<<2];
void build(int u,int l,int r)
{
	tr[u].len=(r-l+1);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(u<<1,l,mid); build(u<<1|1,mid+1,r);
}
inline void add(int u,int v)
{
	tr[u].sum+=1ll*tr[u].len*v;
	tr[u].tag+=v;
	tr[u].lans+=1ll*(tr[u].len+1)*tr[u].len/2*v;
	tr[u].rans+=1ll*(tr[u].len+1)*tr[u].len/2*v;
	tr[u].ans+=cnt[tr[u].len]*v;
}
inline void pushdown(int u)
{
	if(!tr[u].tag) return;
	add(u<<1,tr[u].tag); add(u<<1|1,tr[u].tag);
	tr[u].tag=0;
}
inline void pushup(node &u,node ls,node rs)	
{
	u.len=ls.len+rs.len;
	u.sum=ls.sum+rs.sum;
	u.ans=(ls.ans+rs.ans+ls.rans*rs.len+ls.len*rs.lans);
	u.lans=ls.lans+(ls.sum*rs.len+rs.lans);
	u.rans=rs.rans+(rs.sum*ls.len+ls.rans);
}
void modify(int u,int l,int r,int ml,int mr,int v)
{
	if(ml<=l&&r<=mr) {add(u,v); return;}
	pushdown(u);
	int mid=(l+r)>>1;
	if(ml<=mid) modify(u<<1,l,mid,ml,mr,v);
	if(mr>mid) modify(u<<1|1,mid+1,r,ml,mr,v);
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
node query(int u,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return tr[u];
	pushdown(u);
	int mid=(l+r)>>1;
	if(ql<=mid&&qr>mid) 
	{
		node res={0,0,0,0,0,min(r,ql)-max(l,ql)+1};
		pushup(res,query(u<<1,l,mid,ql,qr),query(u<<1|1,mid+1,r,ql,qr));
		return res;
	}
	if(ql<=mid) return query(u<<1,l,mid,ql,qr);
	else return query(u<<1|1,mid+1,r,ql,qr);
}
int main()
{
	freopen("roadxw.in","r",stdin);
	freopen("roadxw.out","w",stdout);
	scanf("%d%d",&n,&m);
	build(1,1,n);
	ll now=0;
	for(int i=1;i<=n;i++)
	{
		now+=1ll*i*(i-1);
		cnt[i]=(1ll*i*i*(i+1)/2)-now;
	}
	char ch[5]; int l,r,v;
	while(m--)
	{
		scanf("%s%d%d",ch,&l,&r);
		if(ch[0]=='C') scanf("%d",&v),modify(1,1,n,l,r-1,v);
		else 
		{
			ll son=query(1,1,n,l,r-1).ans,mom=1ll*(r-l+1)*(r-l)/2;
			ll d=gcd(son,mom);
			printf("%lld/%lld\n",son/d,mom/d);
		}
	}
	return 0;
}