2752: [HAOI2012]高速公路(road)

Time Limit:?20 Sec??Memory Limit:?128 MB
Submit:?1346??Solved:?499
[Submit][Status][Discuss]

Description

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將期望花費多少費用呢?

Input

第一行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

Output

對于每次詢問操作回答一行，輸出一個既約分數
若答案為整數a，輸出a/1

Sample Input

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

Sample Output

1/1
8/3
17/6

HINT

數據規模

所有C操作中的v的絕對值不超過10000

在任何時刻任意道路的費用均為不超過10000的非負整數

所有測試點的詳細情況如下表所示

Test N M

1 =10 =10

2 =100 =100

3 =1000 =1000

4 =10000 =10000

5 =50000 =50000

6 =60000 =60000

7 =70000 =70000

8 =80000 =80000

9 =90000 =90000

10 =100000 =100000

Source

分析：

就是一個線段樹...

線段樹維護的是區間內所有子串之和，這個很好維護，合并的時候就維護一個所有的以$r$為結尾的子串之和記為$suf$，所有以$l$為開頭的子串記為$pre$，然后合并兩個區間$x,y$的時候就是下面這個式子：

res.ans=x.ans+y.ans+1LL*x.suf*y.len+1LL*y.pre*x.len;

?

現在考慮如何區間加上一個數字，因為是整體加一個數字，所以直接對于每個區間維護一個值叫做$siz$維護的是區間內所有子串的數字個數之和，加的時候就給$ans$加上$val*siz$就好啦...

代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> //by NeighThorn using namespace std;const int maxn=100000+5;int n,m;char opt[3];struct M{int l,r,len;long long pre,suf,sum,ans,siz,lazy;inline void init(void){pre=suf=sum=ans=siz=len=lazy=0;}}tree[maxn<<2];inline M merge(M x,M y){M res;res.init();res.l=x.l,res.r=y.r;res.len=x.len+y.len;res.sum=x.sum+y.sum;res.pre=x.pre+y.pre+1LL*y.len*x.sum;res.suf=y.suf+x.suf+1LL*x.len*y.sum;res.ans=x.ans+y.ans+1LL*x.suf*y.len+1LL*y.pre*x.len;res.siz=x.siz+y.siz+1LL*x.len*y.len*(y.len+1)/2+1LL*y.len*x.len*(x.len+1)/2;return res; }inline void build(int l,int r,int tr){tree[tr].l=l,tree[tr].r=r;tree[tr].init();if(l==r){tree[tr].len=tree[tr].siz=1;return;}int mid=l+r>>1;build(l,mid,tr<<1),build(mid+1,r,tr<<1|1);tree[tr]=merge(tree[tr<<1],tree[tr<<1|1]); }inline void change(int l,int r,int val,int tr){if(tree[tr].l==l&&tree[tr].r==r){tree[tr].pre+=1LL*val*tree[tr].len*(tree[tr].len+1)/2;tree[tr].suf+=1LL*val*tree[tr].len*(tree[tr].len+1)/2;tree[tr].ans+=1LL*val*tree[tr].siz;tree[tr].sum+=1LL*val*tree[tr].len;tree[tr].lazy+=val;return;}int mid=(tree[tr].l+tree[tr].r)>>1;if(tree[tr].lazy)change(tree[tr].l,mid,tree[tr].lazy,tr<<1),change(mid+1,tree[tr].r,tree[tr].lazy,tr<<1|1),tree[tr].lazy=0;if(r<=mid)change(l,r,val,tr<<1);else if(l>mid)change(l,r,val,tr<<1|1);else change(l,mid,val,tr<<1),change(mid+1,r,val,tr<<1|1); tree[tr]=merge(tree[tr<<1],tree[tr<<1|1]); }inline M query(int l,int r,int tr){if(tree[tr].l==l&&tree[tr].r==r)return tree[tr];int mid=(tree[tr].l+tree[tr].r)>>1;if(tree[tr].lazy)change(tree[tr].l,mid,tree[tr].lazy,tr<<1),change(mid+1,tree[tr].r,tree[tr].lazy,tr<<1|1),tree[tr].lazy=0;if(r<=mid)return query(l,r,tr<<1);else if(l>mid)return query(l,r,tr<<1|1);elsereturn merge(query(l,mid,tr<<1),query(mid+1,r,tr<<1|1)); }inline long long gcd(long long x,long long y){return y==0?x:gcd(y,x%y); }signed main(void){ #ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin); #endifscanf("%d%d",&n,&m);build(1,n-1,1);for(int i=1,x,y,s;i<=m;i++){scanf("%s%d%d",opt,&x,&y);if(opt[0]=='C')scanf("%d",&s),change(x,y-1,s,1);else{M tmp=query(x,y-1,1);long long ans=tmp.ans,siz=1LL*tmp.len*(tmp.len+1)/2,Gcd=gcd(ans,siz);if(Gcd==0) puts("0/1");else printf("%lld/%lld\n",ans/Gcd,siz/Gcd);}}return 0; }

?

?

---

By NeighThorn

轉載于:https://www.cnblogs.com/neighthorn/p/6631277.html

總結

以上是生活随笔為你收集整理的BZOJ 2752: [HAOI2012]高速公路(road)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。