Smart Cheater
题解
首先显然的,每个乘客是独立计算的,然后我们发现,一个乘客在 \(i\) 到 \(i+1\) 不买票的期望贡献是一定的,为 \(\dfrac{x_{i+1}-x_i}{2}-c*p_i\),所以我们其实就是要对于每个乘客的区间求最大子段和,简单线段树板子,感觉也没啥细节。
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,m,c;
double x[150005],p[150005],a[150005];
struct Node {int l,r;double ans,lans,rans,d;};
struct Segment_Tree {
Node t[4*150005];
int ls(int p) {return p<<1;}
int rs(int p) {return p<<1|1;}
void pushup(int p) {
t[p].d=t[ls(p)].d+t[rs(p)].d;
t[p].ans=max(max(t[ls(p)].ans,t[rs(p)].ans),t[ls(p)].rans+t[rs(p)].lans);
t[p].lans=max(t[ls(p)].lans,t[ls(p)].d+t[rs(p)].lans);
t[p].rans=max(t[ls(p)].rans+t[rs(p)].d,t[rs(p)].rans);
}
void build(int p,int l,int r) {
t[p].l=l,t[p].r=r;
if(l==r) {t[p].d=t[p].lans=t[p].rans=t[p].ans=a[l];return;}
int m=(l+r)>>1;
build(ls(p),l,m);build(rs(p),m+1,r);
pushup(p);
}
Node query(int p,int l,int r) {
if(t[p].r<l||t[p].l>r) return {0,0,0,0,0,0};
if(l<=t[p].l&&t[p].r<=r) return t[p];
double s=0;int m=(t[p].l+t[p].r)>>1;
Node x=query(ls(p),l,r),y=query(rs(p),l,r),ans;
ans.d=x.d+y.d;
ans.ans=max(max(x.ans,y.ans),x.rans+y.lans);
ans.lans=max(x.lans,x.d+y.lans);
ans.rans=max(x.rans+y.d,y.rans);
return ans;
}
}t;
double ans;
signed main() {
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
scanf("%lf",&x[i]);
for(int i=1;i<n;i++)
scanf("%lf",&p[i]),p[i]/=100;
for(int i=1;i<n;i++)
a[i]=(x[i+1]-x[i])/2.0-c*p[i];
t.build(1,1,n-1);
while(m--) {
int l=rd(),r=rd();
ans+=t.query(1,l,r-1).ans;
}
printf("%.6lf",ans);
return 0;
}
标签:max,ch,int,题解,lans,rans,ans,CF150C
From: https://www.cnblogs.com/operator-/p/17974754