首页 > 代码库 > [HAOI2012]高速公路
[HAOI2012]高速公路
题目描述
Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。
Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的l,r(l<r),在第l个到第r个收费站里等概率随机取出两个不同的收费站a和b，那么从a行驶到b将期望花费多少费用呢?
输入输出格式
输入格式：
第一行2个正整数N,M，表示有N个收费站，M次调整或询问
接下来M行，每行将出现以下两种形式中的一种
C l r v 表示将第l个收费站到第r个收费站之间的所有道路的通行费全部增加v
Q l r 表示对于给定的l,r，要求回答小A的问题
所有C与Q操作中保证1<=l<r<=N
输出格式：
对于每次询问操作回答一行，输出一个既约分数
若答案为整数a，输出a/1
输入输出样例
输入样例#1：
4 5 C 1 4 2 C 1 2 -1 Q 1 2 Q 2 4 Q 1 4
输出样例#1：
1/1 8/3 17/6
#include<bits/stdc++.h>
#define MAXN 100050
#define ll unsigned long long
using namespace std;
inline int read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
struct Tree
{
ll l,r;
ll v,pv,ppv,tag;
}s[MAXN*4];
ll n,m;
ll sum[MAXN],ssum[MAXN];
ll gcd(ll a,ll b)
{
if(a<b) swap(a,b);
if(b==0) return a;
return gcd(b,a%b);
}
inline void pushup(ll pos)
{
s[pos].v=s[pos<<1].v+s[pos<<1|1].v;
s[pos].pv=s[pos<<1].pv+s[pos<<1|1].pv;
s[pos].ppv=s[pos<<1].ppv+s[pos<<1|1].ppv;
}
inline void pushdown(ll pos)
{
if(s[pos].l==s[pos].r||s[pos].tag==0) return;
ll d=s[pos].r-s[pos].l+1;
s[pos<<1].v+=s[pos].tag*(d-(d>>1));
s[pos<<1|1].v+=s[pos].tag*(d>>1);
s[pos<<1].pv+=s[pos].tag*(sum[s[pos<<1].r]-sum[s[pos<<1].l-1]);
s[pos<<1|1].pv+=s[pos].tag*(sum[s[pos<<1|1].r]-sum[s[pos<<1|1].l-1]);
s[pos<<1].ppv+=s[pos].tag*(ssum[s[pos<<1].r]-ssum[s[pos<<1].l-1]);
s[pos<<1|1].ppv+=s[pos].tag*(ssum[s[pos<<1|1].r]-ssum[s[pos<<1|1].l-1]);
s[pos<<1].tag+=s[pos].tag;
s[pos<<1|1].tag+=s[pos].tag;
s[pos].tag=0;
}
inline void build(ll l,ll r,ll pos)
{
s[pos].l=l,s[pos].r=r;
if(l==r) return;
ll mid=(l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,pos<<1|1);
}
inline void update(ll l,ll r,ll pos,ll x)
{
if(l==s[pos].l&&s[pos].r==r)
{
s[pos].tag+=x;
s[pos].v+=x*(s[pos].r-s[pos].l+1);
s[pos].pv+=x*(sum[s[pos].r]-sum[s[pos].l-1]);
s[pos].ppv+=x*(ssum[s[pos].r]-ssum[s[pos].l-1]);
return;
}
pushdown(pos);
ll mid=(s[pos].l+s[pos].r)>>1;
if(r<=mid) update(l,r,pos<<1,x);
else if(l>mid) update(l,r,pos<<1|1,x);
else
{
update(l,mid,pos<<1,x);
update(mid+1,r,pos<<1|1,x);
}
pushup(pos);
}
inline ll query(ll l,ll r,ll pos,ll x)
{
if(l==s[pos].l&&s[pos].r==r)
{
if(x==1) return s[pos].v;
if(x==2) return s[pos].pv;
if(x==3) return s[pos].ppv;
}
pushdown(pos);
ll mid=(s[pos].l+s[pos].r)>>1;
if(r<=mid) return query(l,r,pos<<1,x);
else if(l>mid) return query(l,r,pos<<1|1,x);
else return query(l,mid,pos<<1,x)+query(mid+1,r,pos<<1|1,x);
}
void init()
{
for(ll i=1;i<=100000;i++) sum[i]=sum[i-1]+i;
for(ll i=1;i<=100000;i++) ssum[i]=ssum[i-1]+i*i;
}
int main()
{
n=read(),m=read();
init();
build(1,n,1);
while(m--)
{
char ch;
cin>>ch;
ll l=read(),r=read();
r--;
if(ch==‘C‘)
{
ll c=read();
update(l,r,1,c);
}
else
{
ll x=(l+r)*query(l,r,1,2)+(-l+r-l*r+1)*query(l,r,1,1)-query(l,r,1,3);
ll y=(r-l+2)*(r-l+1)/2;
ll d=gcd(x,y);
printf("%lld/%lld\n",x/d,y/d);
}
}
}
[HAOI2012]高速公路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。