首页 > 其他分享 >杂题

杂题

时间:2023-05-12 20:12:29浏览次数:45  
标签:标记 pushdown add 区间 首项 杂题

P1438 无聊的数列
如果用上差分的思想,就变成了单点修改和区间查询,变得很容易写。

但是我没有这样想,我直接暴力做,记两个懒标记kd分别表示:该子树表示区间全部加上了首项是k,公差是d的等差数列。

维护的时候pushdown都很容易写,但是调了很久。

因为没注意到懒标记定义中的全部,也就是说,一开始调用add的时候要注意把输入的k换算成整个序列的首项。

标签:标记,pushdown,add,区间,首项,杂题
From: https://www.cnblogs.com/zhangchenxin/p/17396194.html

相关文章

  • 5月杂题
    5.7做了什么:坐飞机,大吃大喝。P9139[THUPC2023初赛]喵了个喵II:先考虑每个出现两次怎么做,发现只要每对区间不是包含关系即可。回到此题,相当于要把4个数分成两组,有\(1-2,3-4\),\(1-3,2-4\)两种选法。2-SAT+主席树优化建图即可。5.8做了什么:模拟赛,发的题,CF。LOJ647......
  • 几道好欺负的杂题
    P7325[WC2021]斐波那契会同余+set可以解决改题。CF1264D1BeautifulBracketSequence(easyversion)性质题,找到性质后就不会很难了CF1264D2BeautifulBracketSequence(hardversion)上一道题的强化版,如果你会范德蒙德卷积就很简单了,否则需要考虑组合意义来优化dp......
  • cf 数据结构杂题
    rand一些题目做一下,持续更新平衡树gym101261APersistentDequeYouneedtoprocessthefollowingqueries:Bvx—Addxtothebeginningofthedequewithversionv.Evx—Addxtotheendofthedequewithversionv.<v—Removethefirstelemen......
  • 杂题记录
    2023.4.27下午LZY讲题ICPC2022Shenyang-G题意给定\(n\)个点的两颗树\(T_1,T_2\)。\(m\)次询问\((a,b)\),求\(\max\limits_x\{d_1(a,x)+d_2(x,b)\}\)。\(n\leq10^5,q\leq5\times10^5\)。提交地址https://codeforces.com/gym/104160/problem/G。分析考虑若给定......
  • 4月CWOI杂题
    tips:为了避免一不留神题目就被邪恶的o老师隐藏,题面文件在cnblogs上有备份。C0216【0407C组】模拟测试这场比赛四道题代码加起来长度不超过1500个字符,赢!(223+399+330+541=1493)A【1231C组】数组计数定义\(f_{i,j}\)表示前\(i\)个数,和为\(j\)的方案数,前缀和优化转......
  • 4月CF杂题
    CodeforcesRound862(Div.2)E.ThereShouldBeaLotofMaximums题意:定义一棵点有颜色的树的\(\text{MAD}\)为树上编号最大的出现了至少两次的颜色。对于树上每条边,求出断开它后生成的两棵树的\(\text{MAD}\)的最大值。\(n\le2\times10^5,a_i\le10^9\)。先找到整棵树......
  • 4月AT杂题
    AtCoderBeginnerContest296D-M<=ab题意:求最小的正整数,不小于\(m\),且能被表示为两个不大于\(n\)的正整数的数,不存在输出-1。\(n,m\le10^{12}\)。直接枚举\(a\),计算最小的满足\(ab\gem\)的\(b\),如果\(a>b\)则后面的情况一定是重复的。时间复杂度\(\text{O}(\sqr......
  • 4月杂题
    距离NOI2023还有109天,不能再沉溺于省选的成功了。开始更新博客!4月重点在whk上,不会更很多,为了调和whk的。1.[NOI2023联合省选]填数游戏考虑对于第\(i\)个数,把\(T_i\)中的两个数连边,特别地,只有一个数连自环。此时每个连通块只能是树/基环树。基环树是好做的,因......
  • 【杂题乱写】ARC108
    AtCoderRegularContest108ASumandProduct\(O(\sqrt{n})\)枚举约数判断即可。BAbbreviateFox用栈维护,每次判断栈顶是不是fox,是则弹出。CKeepGraphConnect......
  • 杂题乱做4
    P8499首先,显然需要树哈希。哈希方法见OIwiki。设\(f_i\)表示\(i\)子树的哈希值,那么我们如何判断\(G\)能否通过删去不超过\(k\)个点变成\(H\)?考虑\(solve(i,j......