洛谷 P3924 康娜的线段树_HJ921004的博客-程序员信息网

题目描述

小林是个程序媛,不可避免地康娜对这种人类的“魔法”产生了浓厚的兴趣,于是小林开始教她OI。

今天康娜学习了一种叫做线段树的神奇魔法,这种魔法可以维护一段区间的信息,是非常厉害的东西。康娜试着写了一棵维护区间和的线段树。由于她不会打标记,因此所有的区间加操作她都是暴力修改的。具体的代码如下:

struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1) int sumv[N<<2],minv[N<<2]; inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];} inline void build(int o,int l,int r){ if(l==r){sumv[o]=a[l];return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(o); } inline void change(int o,int l,int r,int q,int v){ if(l==r){sumv[o]+=v;return;} int mid=(l+r)>>1; if(q<=mid)change(lson,l,mid,q,v); else change(rson,mid+1,r,q,v); pushup(o); } }T; 

在修改时,她会这么写:

for(int i=l;i<=r;i++)T.change(1,1,n,i,addv);

显然,这棵线段树每个节点有一个值,为该节点管辖区间的区间和。

康娜是个爱思考的孩子,于是她突然想到了一个问题:

如果每次在线段树区间加操作做完后,从根节点开始等概率的选择一个子节点进入,直到进入叶子结点为止,将一路经过的节点权值累加,最后能得到的期望值是多少?

康娜每次会给你一个值 qwqqwq ,保证你求出的概率乘上 qwqqwq 是一个整数。

这个问题太简单了,以至于聪明的康娜一下子就秒了。

现在她想问问你,您会不会做这个题呢?

输入输出格式

输入格式:

 

第一行整数 n,m,qwqn,m,qwq 表示线段树维护的原序列的长度,询问次数,分母。

第二行 nn 个数,表示原序列。

接下来 mm 行,每行三个数 l,r,xl,r,x 表示对区间[l,r][l,r] 加上 xx

 

输出格式:

 

共 mm 行,表示期望的权值和乘上qwq结果。

 

输入输出样例

输入样例#1:
8 2 1
1 2 3 4 5 6 7 8
1 3 4
1 8 2
输出样例#1:
90
120

说明

对于30%的数据,保证 1 \leq n,m \leq 1001n,m100

对于70%的数据,保证 1 \leq n,m, \leq 10^{5}1n,m,105​​

对于100%的数据,保证1 \leq n,m \leq 10^61n,m106​​

-1000 \leq a_i,x \leq 10001000ai​​,x1000

思路:首先,考虑每一次增加的x可以为期望增加多少 
设一条路路径和为sum 
该叶节点的期望为sum/2^(dep-1) 
但每个叶子的dep不一定相同 
所以可以给sum乘以2^(maxdep-dep),然后就可以统一除以2^(maxdep-1) 
先O(n)把叶节点的sum和求出来 
修改的话维护每一个数的贡献,用前缀和数组 
修改时ans+=(s[r]-s[l-1])*x。

 

错因:本题卡常

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAXN 1000005
using namespace std;
int deep[MAXN];
int n,m,maxdeep;
long long QwQ,ans,y;
long long sum[MAXN],tree[MAXN*4];
void read(long long &x){
    x=0;int f=1; register char c=getchar();
    while(c>'9'||c<'0'){ if(c=='-')    f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar();}x*=f;
}
void build(int now,int l,int r,int de){
    if(l==r){
         
        read(tree[now]);
        deep[l]=de;
        maxdeep=max(maxdeep,de);
        return ;
    }
    int mid=(l+r)/2;
    build(now*2,l,mid,de+1);
    build(now*2+1,mid+1,r,de+1);
    tree[now]=tree[now*2]+tree[now*2+1];
}
long long query(int now,int l,int r,int de,long long s){
    if(l==r)
        return    (1ll<<de)*(s+tree[now]);
    int mid=(l+r)/2;
    if(r<=mid)    return query(now*2,l,r,de-1,s+tree[now]);
    else if(l>mid)    return query(now*2+1,l,r,de-1,s+tree[now]);
    else    return query(now*2,l,mid,de-1,s+tree[now])+query(now*2+1,mid+1,r,de-1,s+tree[now]);
}
int main(){
    scanf("%d%d%d",&n,&m,&QwQ);
    build(1,1,n,1);
    ans=query(1,1,n,maxdeep-1,0);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+(((1ll<<deep[i])-1)<<(maxdeep-deep[i]));
    y=(1ll<<maxdeep-1);
    long long p= __gcd(y,QwQ);
    QwQ/=p;y/=p;
    for(int i=1;i<=m;i++){
        long long l,r,x;
        read(l);read(r);read(x);
        ans+=(sum[r]-sum[l-1])*x;
        printf("%lld\n",ans*QwQ/y);
    }
}

 

转载于:https://www.cnblogs.com/cangT-Tlan/p/7608309.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/HJ921004/article/details/101369342

智能推荐

广搜与深搜_Demosdd的博客-程序员信息网_深搜和广搜

一般来说,广搜常用于找单一的最短路线,或者是规模小的路径搜索,它的特点是"搜到就是最优解", 而深搜用于找多个解或者是"步数已知(好比3步就必需达到前提)"的标题,它的空间效率高,然则找到的不必定是最优解,必需记实并完成全数搜索,故一般情况下,深搜需要很是高效的剪枝(优化).像搜索最短路径这些的很显著若是用广搜,因为广搜的特征就是一层一层往下搜的,保证当前搜到的都是最优解,当然,最短路径只是一方面的操作,像什么起码状态转换也是可以操作的。深搜就是优先搜索一棵子树,然后是另一棵,它和广搜对比,有着内存需要

使用μC/OS-II操作系统的短信息电话机_zhourui1982的博客-程序员信息网

使用μC/OS-II操作系统的短信息电话机作 者: 东南大学 何昭辉 谢吉华摘 要:将μC/OS-II实时嵌入式操作系统移植到EPSON八位单片机上来开发短信息电话机。此电话机除普通电话的通用功能外,还增加了短消息收/发功能、信息浏览与查阅功能、信息点播与信息订阅功能等。关键词:短信息电话机 实时操作系统 μC/OS-II1 背 景  后PC时代的到来,使人

学习笔记(二十一)—— 使用SMTP发送电子邮件_别呀的博客-程序员信息网_smtp发送邮件

一、常用的电子邮件协议常用的电子邮件协议有SMTP、POP3、IMAP4,它们都隶属于TCP/IP协议簇,默认状态下,分别通过TCP端口25、110和143建立连接。下面分别对其进行简单介绍1.1、SMTP协议SMTP的全称是"SimpleMailTransferProtocol",即简单邮件传输协议。它是一组用于从源地址到目的地址传输邮件的规范,通过它来控制邮件的中转方式。SMTP协议属于TCP/IP协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。SMTP服务器就是遵循SMTP协议的发送

j e t brains idea 历史版本怎么下载_JaneYork的博客-程序员信息网

方法一:官网下载https://www.jetbrains.com/idea/download/other.html方法二:第三方平台下载或网友分享放方法三:自己随时存在网盘里各个版本,留备用...

Mybatis 一键生成器的操作教学_少年阿枫的博客-程序员信息网

首先是软件的下载链接 —— 点击下载此软件也是由Java语言编写,可以一键生成表对应的实体类、mapper文件、mapping文件,亲测好用!好了,我们直奔主题!首先下载软件,然后解压压缩文件解压后的目录就是这样,然后点击startup.bat进入软件的主页面然后点击左上角的数据库连接连接成功后按照我下面的步骤操作~有的人可能点击生成会碰到这样的提示~这样操作完了之后就已...

随便推点

Tiktok培训可以去学习吗?_普通网友的博客-程序员信息网

伴随着TIKTOK不断发展,全球化app的红利让人垂涎三尺,在网上有关TIKTOK培训的广告可谓是铺天盖地,当然对这种培训持保留态度。做其实任何事,其实都是需要自己钻研,因为凡事抵不过用心,至于培训,也是可取的,毕竟可以减少时间成本!这里不分享别的,就只谈谈tiktok上面的视频搬运之道。搬运视频,不只是往tiktok上面搬,也可以把tiktok上的视频往YouTube上面搬。做视频搬运其实很简单,几乎没有任何门槛。最重要的是环境问题,因为这个直接影响后面账号能不能正常。环境对于账号的重要性就如人需要空

执行git pull显示already up-to-date,但是本地代码并没有显示出来其他人的改动_徐行莫停的博客-程序员信息网_git pull后already up-to-deta,但本地没有改变

如题之后我再push我的代码就报错,错误信息如下,但是pull、fetch又显示已是最新,令人头秃To http://git.sankuai.com/scm/myfe/canary.git ! [rejected] feature/double_redpack1.2 -&gt; feature/double_redpack1.2 (non-fast-forward)...

js 前端导出报错 格式不正确_vue项目前端导出word文件(bug解决)_weixin_39646107的博客-程序员信息网

摘要:之前项目中导出价格表是由后端实现,前端只需要调用接口下载word即可,后来业务改变比较大,word模版需要一直改动,后端改起来相对麻烦,后来直接前端自己定义模版,实现下载word文档。一、需要安装的依赖1、docxtemplater介绍:docxtemplater是一种邮件合并工具,它以编程方式使用,处理条件、循环,并且可以扩展为表格、HTML、图像等。安装方法:cnpm i docxtem...

Linux iptables防火墙详解(二)——iptables基本配置_永远是少年啊的博客-程序员信息网_linux防火墙iptables配置

本文主要内容是Linux iptables防火墙的基本配置。1、iptables基本参数。2、iptables参数使用示例。

记录一次大坑,org.apache.catalina.startup.Catalina.start Server startup in 72651 ms_————大风起兮云飞扬的博客-程序员信息网

起因今天新弄了一个服务器安装jdk -在解压tomcat,安装正常流程走,部署项目的时候给提示org.apache.catalina.startup.Catalina.start Server startup in 72651 ms一直也不报错,也没显示启动成功的logo,项目地址也访问不到,折腾了一上午,各种找错, 还是没解决,网上各种各样的解决方法,都不行,后...

推荐文章

热门文章

相关标签