【日常小测】市场

相关链接

题目传送门:https://ly.men.ci/problem/196

题目大意

搞一个数据结构来维护一个长度为$n(n \le 10^5)$的序列。
并进行$m(m \le 10^5)$个操作,操作分为以下四种:

  1. 区间加$c(-10^4 \le c \le 10^4)$
  2. 区间除$d$。即对于单个元素$a_i$,除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
  3. 询问区间和
  4. 询问区间最值

解题报告

考虑将所有的相邻的并且值相同的位置合成一个块
考虑一次修改操作最多增加两个块,于是总的块数不会超过$n+m$
那么对于操作二,我们暴力应用到区间的每一个块上
因为每一个块最多进行$\log val$次的操作二就会消失
所以总的操作次数不会超过$O ((n+m) \log (10^4))$

现在考虑具体实现
不嫌麻烦的话,我们可以使用$Splay$。脑袋里想想还是很好写的
要好写一点的话,我们就用线段树,记录一下一个点的子树中所有的值是否相等

相关拓展

这种将相同值合并到一起来保证复杂度的题目还在雅礼集训的时候见过一次啊
当时是要求将编号$l \to r$的结点的父亲全部设为$x$,然后单点修改权值,查询某个点的子树和
也是将$fa$相同的点搞在一起,然后用$Splay$维护一下

22 thoughts to “【日常小测】市场”

  1. Excellent items from you, man. I’ve have in mind your stuff prior to and you are simply too fantastic.
    I actually like what you have bought here, certainly like
    what you are saying and the way in which you assert it. You’re making it enjoyable and you still take care of to
    stay it sensible. I can’t wait to learn much more from
    you. That is actually a tremendous site.

  2. Excellent post however I was wanting to know if you could write a litte more on this topic?
    I’d be very thankful if you could elaborate a little
    bit more. Kudos!

  3. My partner and I stumbled over here from a different web page and thought I might as well check things out.
    I like what I see so now i’m following you. Look forward
    to finding out about your web page yet again.

  4. We stumbled over here coming from a different website and thought I should check things out.
    I like what I see so now i am following you. Look forward to looking into your web page repeatedly.

  5. I’d have to examine with you here. Which is not one thing I usually do! I take pleasure in reading a post that may make folks think. Additionally, thanks for permitting me to comment!

  6. Do you have a spam problem on this website; I also am a blogger, and I was wanting
    to know your situation; many of us have created some
    nice procedures and we are looking to trade methods with others, why not shoot me an e-mail if interested.

  7. Terrific post but I was wondering if you could write a litte more on this topic?
    I’d be very grateful if you could elaborate a little bit
    more. Thank you!

  8. I do believe all of the ideas you’ve offered in your post. They are very convincing and can definitely work. Still, the posts are very short for novices. Could you please prolong them a little from next time? Thank you for the post.

  9. I’ve been surfing online greater than three hours nowadays, but I never found any attention-grabbing article like yours.
    It is pretty price enough for me. Personally, if all
    website owners and bloggers made good content material as you did, the net will likely be
    a lot more useful than ever before.

Leave a Reply to quest bars cheap Cancel reply

Your email address will not be published. Required fields are marked *