[JAVA] Three Approaches [ Segment Tree + Binary Search ] [ Union Find] [Array Based]
\n\n# Segment Tree + Binary Search\n\n\nclass LUPrefix {\n    int tree [] ;\n    int update(int l , int r , int index,int value){\n        if(l==r && l==value){
\n\n# Segment Tree + Binary Search\n```\n\nclass LUPrefix {\n    int tree [] ;\n    int update(int l , int r , int index,int value){\n        if(l==r && l==value){\n            tree[index] = 1;\n            return 1;\n        }\n        int mid = (l+r)/2;\n        if(r<value || value<l) return tree[index];\n        else{\n            int left = update(l,mid,2*index+1,value);\n            int right = update(mid+1,r,2*index+2,value);\n            tree[index]=left+right;\n            return tree[index];\n        }\n        \n    }\n    \n    \n    int query(int l ,int r , int index , int a , int b){\n        if(a<=l && b>=r)\n            return tree[index];\n        else if(b<l || a>r) return 0;\n        else\n        {\n            int mid = (l+r)/2;\n            int left = query(l,mid,2*index+1,a,b);\n            int right = query(mid+1,r,2*index+2,a,b);\n            return left+right;\n        }\n    }\n    int n;\n    public LUPrefix(int n) {\n        tree = new int[4*n];\n        this.n = n;\n    }\n    \n    public void upload(int video) {\n        update(1,n,0,video);\n    }\n    \n    public int longest() {\n        int low = 1;\n        int high = n;\n        int ans = 0;\n        while(low<=high){\n            \n            int mid = (low + high)/2;\n            \n            int count = query(1,n,0,1,mid);\n            if(count == mid){\n                ans = mid;\n                low = mid+1;\n            }\n            else\n            {\n                high = mid - 1;\n            }\n            \n        }\n        return ans;\n        \n        \n    }\n}\n\n```\n\n# Union Find \n\n```\n\nclass LUPrefix {\n    int [] parent ;\n\n    int find(int a ){\n        if(parent[a]==a) return a;\n        return parent[a]=find(parent[a]);\n    }\n\n    void union(int a , int b){\n        parent[b]= parent[a];\n    }\n\n    public LUPrefix(int n) {\n        parent = new int[n+1];\n        for(int i = 0;i<=n;i++) parent[i] = i;\n    }\n    \n    public void upload(int video) {\n        union(video,video-1);\n    }\n    \n    public int longest() {\n       return find(0);\n    }\n}\n\n\n```\n\n# Array \n\n```\n\nclass LUPrefix {\n   \n    int marker [] ;\n    int current = 0;\n    public LUPrefix(int n) {\n        marker = new int[n];\n    }\n    \n    public void upload(int video) {\n        marker[video-1] = 1;\n    }\n    \n    public int longest() {\n       while(current<marker.length && marker[current]==1) current++;\n       return current;\n    }\n}\n\n```\n\n
['Java']