### tech-pandit's blog

By tech-pandit, 5 years ago, ,

plz help me with this D-query problem .

•
• +2
•

 » 5 years ago, # | ← Rev. 5 →   +10 there is simple NlogN offline solution: int posOfLast[2e6] = {-1, -1 ....}; int a[n]; int cnt[n]; // input for (int i = 0; i < n; ++i) { if (posOfLast[a[i]] != -1) cnt[posOfLast[a[i]]]--; posOfLast[a[i]] = i; cnt[posOfLast[a[i]]]++; for (all q in Queries where q.R == i) { sum = 0; // { this part can be done in O(Log(n)) // using Range Sum Query structure, or fenvick tree, or segment tree for (int j = q.L; j <= q.R; j++) sum += cnt[j]; // } ans[q.Id] = sum; } } 
•  » » 5 years ago, # ^ |   0 are you sure this will work ? like for input- 1 2 3 4 1 2after preprocessing cnt array will be like this cnt- 0 0 1 1 1 1so for query [1,5] your answer will be sum=0+0+1+1+1=3 but actual anser will be 4
•  » » » 5 years ago, # ^ |   0 if indexes starts since 0, the sum will be 0+1+1+1+1==4. it seems it's right code.
•  » » » » 5 years ago, # ^ |   0 What if the query was [1,1] — answer 0?!
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +3 just try it. implement & run code above, if you can't understand it. my version
•  » » 3 years ago, # ^ |   0 wow,simple wow! such a beauty! :*
•  » » 3 years ago, # ^ |   0 Thats a beautiful solution. Thanks
•  » » 11 months ago, # ^ |   0 fokkinir put segment tree er code implement kore de -_- oi sob bal sal ami i pari
•  » » 6 months ago, # ^ |   0 How can someone possibly think of such a solution unless he has solved a similar problem in past?
 » 5 years ago, # |   0 Since the problem's name contains the word "query" u had better use query-oriented language like SQL
 » 5 years ago, # |   +1 Does anybody know how to solve this if you can change elements also?
•  » » 4 years ago, # ^ |   0 Something similar to this.
•  » » 11 months ago, # ^ |   0 It can be done in per query, for every two indices l, r such that l < r, al = ar and there is no such index x such that al = ax and l < x < r, store the 2D point (l, r) in some 2D data structure. The answer to a query is the length of the segment minus the number of points inside some rectangle. Which one, you may ask? This is left as an exercise for the reader!
•  » » 6 months ago, # ^ |   0 this is the same problem that u are asking https://www.hackerrank.com/contests/algoelite-v18/challenges/escaping-black-holes-v18
 » 4 years ago, # |   0
 » 3 years ago, # |   0 It can be solved online too with the same NLogn method using persistent segment tree that's how i did it
•  » » 3 years ago, # ^ |   0 Can you provide some links where I can learn Persistent Segment Trees ??
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 Mo's Algorithm which runs in O(NsqrtN) works in time and is fairly easy to code. I used C++, so some slower languages may get TLE.
»
21 month(s) ago, # |
-10

i am still getting tle

# include<bits/stdc++.h>

using namespace std;

int main() { int n,p,count; scanf("%d",&n);

int a[n+1]; int pos[1000001]={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; for(int m=1;m<=p;m++) { count=0; if(q[m].second==i) { for(int k=q[m].first;k<=q[m].second;k++) count+=cnt[k]; ans[m]=count; } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

•  » » 21 month(s) ago, # ^ |   0 you need to use a segment tree or a Fenwick tree to calculate sum from q[m].first to q[m].second in O(log n) time.
• »
»
»
20 months ago, # ^ |
0

it still is giving tle.

# include<bits/stdc++.h>

using namespace std; int tree[6000000]; void build(int node, int start, int end,int *cnt) { if(start == end) { // Leaf node will have a single element tree[node] = cnt[start]; } else { int mid = (start + end) / 2; // Recurse on the left child build(2*node, start, mid,cnt); // Recurse on the right child build(2*node+1, mid+1, end,cnt); // Internal node will have the sum of both of its children tree[node] = tree[2*node] + tree[2*node+1]; } } int query(int node, int start, int end, int l, int r) { if(r < start or end < l) { // range represented by a node is completely outside the given range return 0; } if(l <= start and end <= r) { // range represented by a node is completely inside the given range return tree[node]; } // range represented by a node is partially inside and partially outside the given range int mid = (start + end) / 2; int p1 = query(2*node, start, mid, l, r); int p2 = query(2*node+1, mid+1, end, l, r); return (p1 + p2); } int main() { int n,p,count; scanf("%d",&n);

int a[n+1]; int pos[1000001]={0}; int cnt[n+1]={0}; for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&p); pair<int,int> q[p+1]; int ans[p+1]; for(int i=1;i<=p;i++) { scanf("%d%d",&q[i].first,&q[i].second); } for(int i=1;i<=n;i++) { if(pos[a[i]]!=0) cnt[pos[a[i]]]--; pos[a[i]]=i; cnt[pos[a[i]]]++; build(1,1,i,cnt); for(int m=1;m<=p;m++) { if(q[m].second==i) { ans[m]=query(1,1,i,q[m].first,q[m].second); } } } for(int m=1;m<=p;m++) { printf("%d\n",ans[m]); } }

•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 MO's algorithm + printf/scanf gives AC. Here is my code
 » 19 months ago, # |   +5 I referred this article to make an editorial on the problem. It uses Mo's algorithm, which is offline query processing, to solve the problem in N*sqrt(N). Here is the video link.
•  » » 17 months ago, # ^ |   0 gkcs with the help of your video link and the article you mentioned in your post I came up with a solution to this problem. I tried optimizing it further since its giving me TLE can you please look into my code and tell me where am I going wrong.
•  » » » 17 months ago, # ^ |   0 Hi Prabal, I tried to submit my Java solution to this problem also, and it gave a TLE. The reason, I think, is not to do with the code being optimised. Spoj has very strict time limits, and so java code is difficult to get an AC with.I suggest you try another problem on codechef using the same Mo's algorithm: https://www.hackerearth.com/problem/algorithm/substrings-count-3/
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 Okay, Thanks! Any idea how can we solve Dquery xD
•  » » » » » 16 months ago, # ^ |   0 it can be solved using both offline and online programming . i solved this problem using MO's algorithm and BIT .
•  » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 If you have coded the solution in Java using MO's algorithm I would appreciate your help! :)
•  » » » » » » » 16 months ago, # ^ |   0 i coded in c++ :) AC using Mo'S https://paste.ubuntu.com/24957700/ AC using BIT https://paste.ubuntu.com/24957711/ happy coding :) hope it'll help you .
 » 16 months ago, # |   0 Nice username
 » 7 months ago, # |   0 I'm getting WA on my code. I used MO's algorithm. Can anybody tell me why ? Link to my code
 » 6 months ago, # |   0 I wrote an answer about it on Quora.