Duelist1234's blog

By Duelist1234, history, 8 months ago, In English

So the problem is as following: You are given two integers n and q , and there is an array length n with all zeroes. There are q operations of 3 types: -output the sum in array a from i to j; -a[i] becomes 1; -a[i] becomes 0.

I know this can be done using segment trees but I think that is complicating it.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think it could be done with segment trees look at this article: https://cp-algorithms.com/data_structures/segment_tree.html

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What about BIT?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    or just use set

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and multiset can solve this problem :

      • sum of l ~ r
      • a[i]++
      • a[i]--
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks ill look into that

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        please elaborate

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          we can think it on another side :

          some ball in the bag and ball has a value

          query l~r -> count ball that in the bag and value is l~r a[i]=1 -> put a ball with value i in the bag a[i]=0 -> remove a ball with value i from bag

          if the bag is a set last two query is easy and how to do the first query? we can use lower_bound and upper_bound

          here we solve it

          for the first problem ball's value are different so we can use set and the second (my) problem ball's value maybe same so we use multiset

          My English is bad thank you owo

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what will we store in the multiset? indexes of elements with a[i] = 1?

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              a[i] means how many of ball with value i in the bag

              so if a = [0, 1, 2, 1] (one base)

              set will be {2, 3, 3, 4}

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                a[i] can never be 2, as we are not incrementing it, we're just setting a[i] = 1 or a[i] = 0, so a[i] has only 2 possible values 1 and 0

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            To find the number of balls you will need distance between 2 iterators which is $$$O(n)$$$

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              yes, so its O(n*q)?

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              you are right i forget set lower bound can't do that

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              but will it work if stored i such that a[i] = 1 in the set and used lowerbound to find the number of indexes in the range l to r in the set?

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              can't we find the difference between the iterators can't we just subtract them, wouldn't it be O(1)?

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It is possible to subtract two iterators, but not for a std::set. We can use set from pb_ds. This is the solution to problem.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                And, certainly, we can do more complex things with Cartesian Tree.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i feel like you could use a bitset(N must not be 1e18 or something , then you cant)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As already writted, you can use Fenwick tree(binary indexed tree), it's very quick to implement, but not so easy to understand. If you want to know easy to understand solution with at least decent time complexity, you can look into the sqrt decomposition