### tech-pandit's blog

By tech-pandit, 9 years ago,

plz help me with this D-query problem .

• +2

 » 9 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; } } 
•  » » 9 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
•  » » » 9 years ago, # ^ |   0 if indexes starts since 0, the sum will be 0+1+1+1+1==4. it seems it's right code.
•  » » » » 9 years ago, # ^ |   0 What if the query was [1,1] — answer 0?!
•  » » » » » 9 years ago, # ^ | ← Rev. 3 →   +3 just try it. implement & run code above, if you can't understand it. my version
•  » » 7 years ago, # ^ |   0 wow,simple wow! such a beauty! :*
•  » » 7 years ago, # ^ |   0 Thats a beautiful solution. Thanks
•  » » 5 years ago, # ^ |   0 fokkinir put segment tree er code implement kore de -_- oi sob bal sal ami i pari
•  » » 4 years ago, # ^ |   0 How can someone possibly think of such a solution unless he has solved a similar problem in past?
•  » » 3 years ago, # ^ |   0 e-maxx.ru has it also
•  » » 4 hours ago, # ^ |   0 Wow..great idea brother.
 » 9 years ago, # |   0 Since the problem's name contains the word "query" u had better use query-oriented language like SQL
 » 9 years ago, # |   +1 Does anybody know how to solve this if you can change elements also?
•  » » 8 years ago, # ^ |   0 Something similar to this.
•  » » 5 years 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!
•  » » 4 years ago, # ^ |   0 this is the same problem that u are asking https://www.hackerrank.com/contests/algoelite-v18/challenges/escaping-black-holes-v18
 » 8 years ago, # |   0
 » 6 years ago, # |   0 It can be solved online too with the same NLogn method using persistent segment tree that's how i did it
•  » » 6 years ago, # ^ |   0 Can you provide some links where I can learn Persistent Segment Trees ??
•  » » » 6 years ago, # ^ |   0
 » 6 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.
»
5 years 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]); } }

•  » » 5 years 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.
• »
»
»
5 years 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]); } }

•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 MO's algorithm + printf/scanf gives AC. Here is my code
 » 5 years 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.
•  » » 5 years 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.
•  » » » 5 years 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/
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Okay, Thanks! Any idea how can we solve Dquery xD
•  » » » » » 5 years ago, # ^ |   0 it can be solved using both offline and online programming . i solved this problem using MO's algorithm and BIT .
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 If you have coded the solution in Java using MO's algorithm I would appreciate your help! :)
•  » » » » » » » 5 years 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 .
•  » » 12 months ago, # ^ |   0 I loved your that video.Can you please give me some hints to solve the question without Mo , using segment tree . Thanks for help in advance.
 » 5 years ago, # |   0 Nice username
 » 4 years ago, # |   0 I'm getting WA on my code. I used MO's algorithm. Can anybody tell me why ? Link to my code
 » 4 years ago, # |   0 I wrote an answer about it on Quora.
 » 15 months ago, # |   0 # creating pos of last and occur tables posOfLast=[-1 for i in range(1000001)] occur=[0 for i in range(n)] # helps in understanding the approach # creating event by merging query and arr and sorting event=[] event+=Q for i in range(n): event.append((-1,i)) event.sort(key=lambda x:(x[1],x[0])) # fen_tree obj obj=fen_tree(n+1) ans={} # offline Query for l,r in event: if l==-1: # update if posOfLast[arr[r]]!=-1: occur[posOfLast[arr[r]]]-=1 # just for understanding obj.update(posOfLast[arr[r]]+1,-1) posOfLast[arr[r]]=r occur[posOfLast[arr[r]]]+=1 # just for understanding obj.update(posOfLast[arr[r]]+1,+1) else: # query ans[(l,r)]=obj.query(r+1)-obj.query(l) # printing ans for l,r in Q: print(ans[(l,r)])