JZYZOJ1527 [haoi2012]高速公路 线段树 期望
2024-08-28 18:28:20
http://172.20.6.3/Problem_Show.asp?id=1527
日常线段树的pushdown写挂,果然每次写都想得不全面,以后要注意啊……
求期望部分也不熟练,和平均数搞混也是orz,我已经是个期望都求不出来的废人了。
这道题显然(大概)每个段的贡献是val[i]*(y-i+1)*(i-x+1);
整体来说算是一看就是线段树的题。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define lc x*2
#define rc x*2+1
const int maxn=<<;
long long n,m;char ch[]={};
struct seg{
long long l,r,v,w,v1,v2,w1,w2;
seg(){l=r=v1=v2=w1=w2=v=w=;}
}e[maxn];
long long v1,v2,v3;
void pushdown(long long x,long long v){
if(v!=){
long long siz=e[x].r-e[x].l+;
e[x].v+=siz*v;
e[x].w1+=e[x].v1*v;
e[x].w2+=e[x].v2*v;
e[x].w+=v;
}
}
void doit(long long x){
pushdown(lc,e[x].w);
pushdown(rc,e[x].w);
e[x].w=;
}
void pushup(long long x){
if(e[x].l<e[x].r){
e[x].v=e[lc].v+e[rc].v;
e[x].w1=e[lc].w1+e[rc].w1;
e[x].w2=e[lc].w2+e[rc].w2;
}
}
void cha(long long x,long long l,long long r,long long w){
if(l<=e[x].l&&e[x].r<=r){
pushdown(x,w);
return;
}doit(x);
long long mid=(e[x].l+e[x].r)/;
if(l<=mid)cha(lc,l,r,w);
if(r>mid)cha(rc,l,r,w);
pushup(x);
}
void sum(long long x,long long l,long long r){
if(l<=e[x].l&&e[x].r<=r){
v1+=e[x].v;v2+=e[x].w1;v3+=e[x].w2;
return;
}doit(x);
long long mid=(e[x].l+e[x].r)/;
if(l<=mid)sum(lc,l,r);
if(r>mid)sum(rc,l,r);
pushup(x);
}
void build(long long x,long long l,long long r){
e[x].l=l;e[x].r=r;
if(l==r){
e[x].v1=l;e[x].v2=l*l;return;
}
long long mid=(l+r)/;
build(lc,l,mid);
build(rc,mid+,r);
e[x].v1=e[lc].v1+e[rc].v1;e[x].v2=e[lc].v2+e[rc].v2;
}
long long gcd(long long x,long long y){
while(y){
long long w=y;y=x%y;x=w;
}
return x;
}
int main(){
build(,,<<);
scanf("%I64d%I64d",&n,&m);
long long x,y,v;
for(int i=;i<=m;i++){
scanf("%s",&ch);
if(ch[]=='C'){
scanf("%I64d%I64d%I64d",&x,&y,&v);
cha(,x,y-,v);
}
else{
scanf("%I64d%I64d",&x,&y);
v1=v2=v3=;sum(,x,y-);
long long ans=v1*(y-x*y)+v2*(x+y-)-v3;
long long z=y-x;long long zong=z*(z+)/;
long long w=gcd(ans,zong);
printf("%I64d/%I64d\n",ans/w,zong/w);
}
}
return ;
}
最新文章
- Ognl表达式基本原理和使用方法
- 如何使用jcraft 模拟SFTP登陆
- Java基础复习笔记系列 三
- 多态(RAW)
- Centos7下修改默认网卡名(改为eth0)的操作记录
- Linux内核
- iOS多线程之NSThread使用
- MyBatis学习总结_02_使用MyBatis对表执行CRUD操作
- [iOS微博项目 - 1.7] - 版本新特性
- UVA 572 Oil Deposits油田(DFS求连通块)
- editplus批量删除html代码空行
- NetAnalyzer笔记 之 五 一些抓包技巧分享(不定期更新)
- 推荐五款Android 应用的自动化测试工具
- JMeter脚本java代码String数组要写成String[] args,不能写成String args[],否则报错。
- count
- time模块的学习
- Nginx 测试环境配置,留作笔记使用
- Scrapy Crawl 运行出错 AttributeError: 'xxxSpider' object has no attribute '_rules' 的问题解决
- Qt setMouseTracking(true) 无效
- *args 和**kwargs 的溯源