BZOJ2743 采花

题目大意

有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。
n,m<=1000,000

Solution

刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。

我会函数式线段树,于是有口胡了一个可持久化线段树的做法,就是维护出所有1~r的线段树,且1~i+1的线段树是从1~i的线段树修改几个点后继承过来的。花了10分钟写完,开数组时发现要开三个2e7的数组,空间240MB,而内存限制只有128MB,不得已,砍掉一半,数组大小定了1e7。交上去后,喜闻乐见地RE了o(╥﹏╥)o。

后来又发现,这道题没有强制在线,所以对读入的数据按右端点排序后,可以每次加入一个数i后处理完右端点为i的询问,就不需要记录前面的线段树了。不需要可持久化的线段树,空间复杂度变成了O(n)。

单点修改,区间查询和,其实也能用树状数组,只是懒得改线段树了。

Code

1596 条评论
  1. Thanks so much for the blog.Much thanks again. Really Cool.

  2. Thanks so much for the article post.Really looking forward to read more. Cool.

  3. I see you’re a blog owner, so please add me to your email / mailing list. My email is: mediciondigital@gmail.com – I buy websites that meet certain metrics. This site looks like it might, so please reach out to me

发表一条评论