When I do an exercise I have a problem that let Ai <= 60 and n <= 1e5 and q <= 1e5, Count number of distinct elements in l to r. With type 1 query update change all elements from l to r to v. Type 2 query answer the number of distinct elements from l to r.
Example:
5 5
1 1 1 1 1
1 2 4 2
1 5 5 3
2 1 5 // is 3.
2 1 4 // is 2.
2 2 4 // is 1.
I know how if we update an element we can do this with the segment tree. But i don't know updating the range. Is this possible? if yes please explain to me. thanks for help!
for each value v from 1 to 60 make a segment tree, the value of a node of the vth segment tree is 1 if its range contains v and 0 otherwise, you can easily implement the rest of the solution.
Actually, making 60 segtrees is unneeded. Since the leaves and all the other nodes can only contain 0 or 1, you can use only 1 segtree of 64-bit integers instead. The nodes will contain the mask of present numbers on the respective ranges.
that's a very good idea
I know we can use The bitMask of 1 node of segment tree will denote the presence of ith number or not, we will find out that by checking the ith bit of our bitMask, if the ith bit is on, that means i’th element is present, otherwise not present. And combine the two node of the tree with bitwise OR operation. But what I want to ask is how can I update the range on this segment tree.
you update using simple lazy propagation
But how do you clear the ith bit in mask and combine the two node in the segment tree when you update with lazy propagation.
when you update a node which covers some range [l,r] to contain Ai=v, you know whatever else was there before isn't, so you can just set the entire mask to (1<<v) (and flag it so it gets pushed down if every the child nodes are queried). Merging is simple, you just OR the bitmasks of the two children.
There's a minor bug in your code. It's necessary to use
__builtin_popcountllfor counting bits in long long.It's also possible to use AtCoder ac-library. Their Lazy Segtree is documented here. And they have a Lazy Segtree tutorial, which explains how to pick mapping and composition functions.
Using a library results in a somewhat shorter code: