wonderful_trip's blog

Question about counting the number of distinct elements in l to r and update range?
By wonderful_trip, history, 3 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that's a very good idea

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you update using simple lazy propagation

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Spoiler

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There's a minor bug in your code. It's necessary to use __builtin_popcountll for counting bits in long long.

              → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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:

        My variant of a C++ solution using AtCoder ac-library
        → Reply