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 ;
}

最新文章

  1. Ognl表达式基本原理和使用方法
  2. 如何使用jcraft 模拟SFTP登陆
  3. Java基础复习笔记系列 三
  4. 多态(RAW)
  5. Centos7下修改默认网卡名(改为eth0)的操作记录
  6. Linux内核
  7. iOS多线程之NSThread使用
  8. MyBatis学习总结_02_使用MyBatis对表执行CRUD操作
  9. [iOS微博项目 - 1.7] - 版本新特性
  10. UVA 572 Oil Deposits油田(DFS求连通块)
  11. editplus批量删除html代码空行
  12. NetAnalyzer笔记 之 五 一些抓包技巧分享(不定期更新)
  13. 推荐五款Android 应用的自动化测试工具
  14. JMeter脚本java代码String数组要写成String[] args,不能写成String args[],否则报错。
  15. count
  16. time模块的学习
  17. Nginx 测试环境配置,留作笔记使用
  18. Scrapy Crawl 运行出错 AttributeError: 'xxxSpider' object has no attribute '_rules' 的问题解决
  19. Qt setMouseTracking(true) 无效
  20. *args 和**kwargs 的溯源

热门文章

  1. 【51NOD】消灭兔子
  2. EditText中inputType详解
  3. 第一章:读取文件一行IO::File
  4. 手動設定 電池溫度 mtk platform
  5. centos 挂在ntfs
  6. 基于 Arduino 开发板,这款插座是可编程且开源的
  7. 【LOJbeta round1】ZQC的手办
  8. 使用Storm实现实时大数据分析(转)
  9. redis之(十)redis实现消息中间件的功能
  10. Max Points on a Line——数学&amp;&amp;Map