adyyy's blog

By adyyy, history, 4 years ago, In English

Hey, Can we calculate LIS with queries in an online manner ?? I have read about a offline method using DAG but how to process online ?

  • Vote: I like it
  • -33
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adyyy (previous revision, new revision, compare).

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

If you mean online query is keep pushing at the back of the array, then here they are the implementations

If you only need the size of LIS

vector with binary search
fenwick tree with coordinate compression

if you want to trace back to get the LIS sequence

vector with binary search and finding LIS offline
vector with binary search and finding LIS online

Of course there are many other ways to solve LIS, and some other ways when you can push front-back and getting the size in $$$O(constant)$$$ or $$$O(polylog)$$$ while taking the LIS sequence can be done with $$$O(n)$$$ or $$$O(n\ log\ n)$$$

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

This video could be helpful (article is here). Care to elaborate what do you mean by online?

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

do you ask about CC november challange unusual queries problem? https://www.codechef.com/NOV20B/problems/UNSQUERS

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

    lol it seems so. They can't even tell the difference with LIS.

    Question is still open if it's about (l, r) LIS queries. Are there any sublinear algorithms (mb approximate)?

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

    Umm actually yes but I believe it is just a subpart not the whole thing and obviously long challenges about to gather information I guess !!!

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

      this is my full solution to your problem

      Spoiler