[HAOI2012]高速公路

传送门

题解

由于每种选择概率是一样的,那么答案显然=每种选择费用和/选择方案数,那么我们只需要计算每种选择费用和就好了。

考虑第i段路(经过费用ViV_i)对答案的贡献。

假设询问区间是l,r,经过这段路的方案数=(il+1)(ri)=(l1+r)ii2r(l1)=(i-l+1)(r-i)=(l-1+r)i-i^2-r(l-1),贡献显然就是((l1+r)ii2r(l1))Vi((l-1+r)i-i^2-r(l-1))V_i,答案就是i=lr1(((l1+r)ii2r(l1))Vi)=(l1+r)i=lr1iVii=lr1i2r(l1)i=lr1Vi\sum\limits_{i=l}^{r-1}(((l-1+r)i-i^2-r(l-1))V_i)=(l-1+r)\sum\limits_{i=l}^{r-1}iV_i-\sum\limits_{i=l}^{r-1}i^2-r(l-1)\sum\limits_{i=l}^{r-1}V_i,线段树维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
Author: CNYALI_LK
LANG: C++
PROG: 2221.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll rdc(){
char c;
while(!isalpha(c=getchar()));
return c=='Q';
}
ll sum[3][102424];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
struct smt{
ll s[3],add,ls,rs;
smt *l,*r;
void push_up(){
for(ll i=0;i<3;++i)s[i]=l->s[i]+r->s[i];
}
void put_tag(ll x){
if(x){
add+=x;
for(ll i=0;i<3;++i)s[i]+=x*(sum[i][rs]-sum[i][ls-1]);
}
}
void push_down(){
l->put_tag(add);
r->put_tag(add);
add=0;
}
smt(ll la,ll ra){
ls=la;rs=ra;
add=0;
s[0]=s[1]=s[2]=0;
if(la==ra){l=r=0;}
else {
ll mid=(la+ra)>>1;
l=new smt(la,mid);
r=new smt(mid+1,ra);
}
}
void Add(ll la,ll ra,ll w){
if(la<=ls&&rs<=ra)put_tag(w);
else{
push_down();
if(la<=l->rs)l->Add(la,ra,w);
if(r->ls<=ra)r->Add(la,ra,w);
push_up();
}
}
ll Sum(ll w,ll la,ll ra){
if(la<=ls&&rs<=ra)return s[w];
else{
push_down();
ll ans=0;
if(la<=l->rs)ans+=l->Sum(w,la,ra);
if(r->ls<=ra)ans+=r->Sum(w,la,ra);
return ans;
}
}
}*rt;
int main(){
#ifdef cnyali_lk
freopen("2221.in","r",stdin);
freopen("2221.out","w",stdout);
#endif
ll n,m,l,r,v,s1,s2,s0,s,t,g;
n=read();m=read();
for(ll i=1;i<=n;++i){
sum[0][i]=sum[0][i-1]+1;
sum[1][i]=sum[1][i-1]+i;
sum[2][i]=sum[2][i-1]+i*i;
}
rt=new smt(1,n-1);
for(;m;--m){
if(rdc()){
l=read();r=read();
s0=rt->Sum(0,l,r-1);
s1=rt->Sum(1,l,r-1);
s2=rt->Sum(2,l,r-1);
--l;
s=s1*(r+l)-l*r*s0-s2;
t=(r-l)*(r-l-1)>>1;
g=gcd(s,t);
printf("%lld/%lld\n",s/g,t/g);
}
else{
l=read();r=read();
v=read();
rt->Add(l,r-1,v);
}
}
return 0;
}
文章目录
  1. 1. 题解
|

博客使用Disqus作为评论系统