tech-pandit's blog

spoj Problem D-query
By tech-pandit, 9 years ago, In English

plz help me with this D-query problem .

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 5   Vote: I like it +10 Vote: I do not like it

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;
	}
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    are you sure this will work ? like for input- 1 2 3 4 1 2

    after preprocessing cnt array will be like this cnt- 0 0 1 1 1 1

    so for query [1,5] your answer will be sum=0+0+1+1+1=3 but actual anser will be 4

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

    wow,simple wow! such a beauty! :*

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

    Thats a beautiful solution. Thanks

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

    fokkinir put segment tree er code implement kore de -_- oi sob bal sal ami i pari

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

    How can someone possibly think of such a solution unless he has solved a similar problem in past?

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

    e-maxx.ru has it also

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

    Wow..great idea brother.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the problem's name contains the word "query" u had better use query-oriented language like SQL

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anybody know how to solve this if you can change elements also?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://pastebin.com/j9g9CHAL

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be solved online too with the same NLogn method using persistent segment tree

that's how i did it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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]); } }

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

    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.

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

      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]); } }

      → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

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

    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.

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice username

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

I'm getting WA on my code. I used MO's algorithm. Can anybody tell me why ? Link to my code

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

I wrote an answer about it on Quora.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
# 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)])
→ Reply