tech-pandit's blog

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

plz help me with this D-query problem .

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

Comments Comments (28)
| Write comment?
»
11 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
  • »
    »
    11 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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wow,simple wow! such a beauty! :*

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

    Thats a beautiful solution. Thanks

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

    e-maxx.ru has it also

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

    Wow..great idea brother.

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

    wow

    → Reply
»
11 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
»
11 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
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://pastebin.com/j9g9CHAL

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

I wrote an answer about it on Quora.

→ Reply