Beginner LEVEL Intuition Development for any OFFLINE QUERY QUESTIONS
In mostly every post in discuss everyone told the solution for this question.\nBut no one exactly has told the offline query concept. So i have tried to tell an
In mostly every post in discuss everyone told the solution for this question.\nBut no one exactly has told the offline query concept. So i have tried to tell and highlight my approach of seeing and identifying offline query type questions.\n\nHope it helps. Plz upvote if u like!\n\n**Intuition for Solving OFFLINE QUERIES QUESTION**\n1. There will be first of all some `queries will be given`.\n2. Then we should first consider of `solving a single query in the best optimized way`.\n3. Then after applying the optimised approach found for a single querie in step2 , we will `apply it in every query and time complexity would be somewhat close to O(q.size() * N) because for every query we will be traversing whole array.`.\n4. Now we should think about applying **offline query** and we need to observe below written type of a scenario for offline query.\n\n  ```\n```\n  ```\nIn most of the case there would be some limit value would be given for every query.\nThen we will see that:\n\t       For eg : <=7 will be also candidate for <=10 which will also be candidate for <=20 and so on.\nIf we observe above type of  scenario in any query type question. Then we simply need to apply the offline query algorithm.\n```\n```\n```\n\n>> **OUR MAIN FOCUS SHOULD ONLY BE ON `How to solve a single query in most efficient way` and secondly, `identifying whether it is a offline query type question or not by observing above scenarios`, because after identifying the algorithm for any offline type qery is approx same as below**\n\n\n# Generic Algorithm for any OFFLINE QUERY TYPE QUESTION: \n\n           //put indexes in the query\n\t\t   for(int i=0;i<q.size();i++) q[i].push_back(i);\n\t\t   //sort the queries and input\n           sort(begin(a),end(a));\n           sort(begin(q),end(q),[](auto &x,auto &y){ return x[1] < y[1]; });\n        \n           int i=0;\n           vector<int> ans(q.size());\n        \n           for(auto j:q){\n                 int c= j[0], p=j[1], idx= j[2];\n                for(;i<size(a) and a[i]<=p;i++) //call function for putting candidates of a single query\'\n\t\t\t\t//put answer of current query in its corresponding index number in the result array...\n                if(i==0) ans[idx]=-1;\n                else ans[idx]= //function for getting answer of single query \n           } \n        return ans;\n\n\n\n**Solution for this problem based on offline query concept** => C++\n   \n    class Solution {\n    public:\n\n    class DSU{\n        vector<int> par,rank;\n        public:\n        \n        DSU(int n){\n            par.resize(n);\n            rank.resize(n,1);\n            iota(begin(par),end(par),0);\n        }\n        \n        int find(int u){\n            if(par[u]==u) return u;\n            else return par[u]= find(par[u]);\n        }\n        \n        void union_p(int u,int v){\n            u= find(u);\n            v= find(v);\n            \n            if(rank[u]<rank[v]) par[u]=v;\n            else if(rank[u]>rank[v]) par[v]=u;\n            else{\n                par[v]=u;\n                rank[u]++;\n            }\n        }\n    };\n    \n    \n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>&a, vector<vector<int>>& q) {\n        \n       DSU d(n);\n       //Algofor offline queries\n       for(int i=0;i<q.size();i++) q[i].push_back(i);\n       //sort the queries and input\n       sort(begin(a),end(a),[](auto &x,auto &y){ return x[2] < y[2]; });\n       sort(begin(q),end(q),[](auto &x,auto &y){ return x[2] < y[2]; });\n    \n       int i=0;\n       vector<bool> ans(q.size());\n    \n       for(auto j:q){\n            int u= j[0], v=j[1], p=j[2], idx= j[3];\n            for(;i<size(a) and a[i][2]<p;i++) d.union_p(a[i][0],a[i][1]);\n            ans[idx]= (d.find(u)==d.find(v));\n       } \n       \n       return ans;\n        \n    }\n    };
['C']