首页 > 代码库 > [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个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。