首页 > 其他分享 >2.7 小记

2.7 小记

时间:2023-02-07 23:44:22浏览次数:46  
标签:le 贡献 键值 生效 2.7 就是 小记

杂题选讲。

讲了一车题,就做了一个。

这几天在洛谷的提交量骤降,要被超过去了喵。

#3692. 「JOISC 2022 Day3」洒水器

简单小水题。

就是设 \(d[i][j]\) 表示以 \(i\) 为根的子树里距离根的长度为 \(j\) 的点要乘的权值。

然后修改就是网上跳,改 \(D-dis,D-dis-1\)的就行。

查询也是往上跳。

#3033. 「JOISC 2019 Day2」两个天线

憨憨数据结构,但是我是憨憨。

拆贡献,然后从左向右考虑。只考虑 \(H_j-H_i,j>i\) 的贡献,另外一种反转一下即可。

考虑把询问挂在右端点上,考虑每次加入一个新点 \(j\)。

在两个条件中,其中一个要求 \(i+a_i\le j\le i+b_i\) ,也就是左边的点有一定生效时间,那么只需要在开始生效的时候在 \(i\) 处加入自己表示生效,结束后再让自己失效。

另外一个条件是 \(j-b_i\le i \le j-a_i\) ,这是用 \(j\) 的一部分限制 \(i\) ,这就是在 \(j\) 处,在一定区间内加入 \(j\) 产生的贡献。

具体而言就是每个点两个键值,一个表示自己产生的贡献 \(-H_i\) ,另一部分指后面的产生的贡献,\(H_j\),满足第一个条件就是在开始生效时在自己的第一个键值处加上贡献。第二个条件就是加 \(j\) 的时候对一段区间的第二个键值取 \(\max\) 。因为最后求 \(\max\),所以不用 tree beats,直接打 tag 就行。

查询就是在右端点区间查历史最大值,因为所有贡献都是在左边的点上,所以不符合的一定统计不进去。

赞美太阳!!

注意的是在单点修改第一个键值的时候把这个位置的第二个键值清空,因为要消掉以前的贡献。

废话

我最近有点浮躁。总想吃小孩,式子总推错。

我会努力改掉的,对吧

我前几天生成函数之类的什么做的恶心。现在想做点思维或者数据结构散散心(?)

转吧转吧 丑陋的马啊

我知道你不甘当下

现啊实啊 太复杂让时间作答

眼中藏的海洋 会冲刷旁人吵闹

最奇怪的总是你是你

最独特的也是你是你

这世界 绝对不会只有一个轴心

最孤单的还是你是你

最心疼的是赌上所有安全感 作为筹码(丑马)的你

标签:le,贡献,键值,生效,2.7,就是,小记
From: https://www.cnblogs.com/cc0000/p/17100197.html

相关文章

  • 2023.2.7 日寄
    2023.2.7日寄一言\(~~~~\)HewasmyNorth,mySouth,myEastandWest,\(~~~~\)MyworkingweekandmySundayrest,\(~~~~\)Mynoon,mymidnight,mytalk,......
  • 闲话 23.2.7
    闲话草感觉写闲话时浑身不自在(溜了溜了今日推歌:临川浮梦链接自行搜吧(但是好听!模拟赛题解感觉最近好颓啊……T1神奇纸牌我怎么写不出容斥式子了?srds感觉验题......
  • 毕设周报2.7
    毕设进展目前集中在写一个公共的量化模板lenet_mnist未量化跟量化都训练成功。cifar10_vgg16未量化的模型甚至都训练不出来,代码我放目录里,我尝试print了几层,似乎它的......
  • 2.7 vp Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)
    A1-Non-alternatingDeck(easyversion)题意给出一个数字n,两个人轮流玩游戏从n中拿数,第一个人首先拿1,第二个人拿2,3,第一个人拿1...循环往复,直到数字全被拿完思路模......
  • 2.6-2.7
    LinkCutTree(动态树)概念讲解LCT维护的对象其实是一个森林。在实链剖分的基础下,LCT支持更多的操作,即树剖升级版,但在实际做题中因为树剖的常数小且相对容易调试,所以能......
  • python2.7 + MySQL 拼接SQL语句的技巧 (处理unicode,时间)
    背景在Python2.7中,可以使用单引号,双引号,三引号表示字符串,当字符串的值为中文时,则会默认转换成unicode。但是在MYSQL中,使用SQL语句时,直接用unicode作为列的查询条件(例如......
  • python基础:split、join、replace、remove、del、pop、index小记
    这里总结了平时写脚本时经常用到的一些基础方法,做个记录1、split()函数可以基于分隔符将字符串分割成由若干子串组成的列表str.split(str="",num=string.count(str))......
  • Dubbo2.7的Dubbo SPI实现原理细节
    总结/朱季谦本文主要记录我对DubboSPI实现原理的理解,至于什么是SPI,我这里就不像其他博文一样详细地从概念再到JavaSPI细细分析了,直接开门见山来分享我对DubboSPI的见解......
  • COREDNS小记
    一、coredns的域名解析流程CoreDNS是一个Go语言编写的灵活可扩展的DNS服务器,在Kubernetes中,作为一个服务发现的配置中心,在Kubernetes中创建的Service和Pod都会......
  • 2023.02.04小记
    买到了想了很久的裙子今天加班,本来可以居家办公的,但是我选择来公司,溜溜我的新裙子和新小皮鞋旧图镇楼,2018年的我真好啊,这图还是当时的舍友帮我拍+P的当年的裙子今天......