D-query Editorial -SPOJ - UCS - Unleash-Coding-Skills

Friday, 23 March 2018

D-query Editorial -SPOJ - UCS


                         D-query Solution

Given a sequence of n numbers a1, a2, ..., an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, ..., aj.

Input

  • Line 1: n (1 ≤ n ≤ 30000).
  • Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
  • Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
  • In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

  • For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, ..., aj in a single line.

Example

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3 

D-query Problem link:

http://www.spoj.com/problems/DQUERY/


First of the in this solution we use offline MO's algorithm.

Precautions :
1) Declare array sizes based on given constraints.
2) If you are using C++ then dont use cin and cout instead use scanf and printf otherwise it will lead to TLE and your solution wont get passed the given testcases.

MO's algorithm rules used in sorting in this problem:
  1. Denote BLOCK_SIZE = sqrt(N);
  2. Rearrange all queries in a way we will call “Mo’s order”. It is defined like this: [L1, R1] comes earlier than [L2, R2] in Mo’s order if and only if:
       a) L1BLOCK_SIZE < L2BLOCK_SIZE
       b) L1BLOCK_SIZE == L2BLOCK_SIZE && R1 < R2

Solution:

#include <bits/stdc++.h>

using namespace std;



                                                                                                                                                                    



//This position is a struct used to handle queries

//it contains left ,right

// index to keep track of current query number since we use sort in it so order

//will be varied



struct position

{



 int left,right,index;   

}query[200010];



int block;







//it is used in sorting based on it the queries will be sorted

//This is sorting is based on MO's algorithm rules as mention above of this //solution

bool comparison(position p1,position p2)

{

  if((p1.left/block)!=(p2.left/block))

        return (p1.left/block)<(p2.left/block);

    else

return p1.right<p2.right;

}



int main() {

    int i,j,k,a[30003],hash[1000002],answer[400000],n,q;

      ios_base::sync_with_stdio(false);

//Take inputs first

  scanf("%d",&n);

    block=sqrt(n);

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

    }

    scanf("%d",&q);

    for(i=0;i<q;i++)

    {

        scanf("%d",&query[i].left);

        scanf("%d",&query[i].right);

        query[i].left--;

        query[i].right--;

        query[i].index=i;

    }

//sort the queries according to MO's algorithm

    sort(query,query+q,comparison);

    int l=0,r=-1,ans=0;



    for(i=0;i<q;i++)

    {

//These loops are used to move left and right based on queries and

//change the values of the hash array based on the requirement

  while(l<query[i].left)

  {

      hash[a[l]]--;

//if hash[a[l]] is equal to zero that means no array element is using this hash

//value now so it must be removed or decremented from ans value

      if(hash[a[l]]==0)

          ans-=1;

      l++;

  }

        int fl=0;

      

        while(r<query[i].right)

        {

            hash[a[r+1]]++;



//if hash[a[l]] is equal to one that means an array element is using this hash

//value now so it must be added or incremented from ans value

            if(hash[a[r+1]]==1)

                ans+=1;

            r++;

            fl=1;

        }

       

        while(l>query[i].left)

        {



            hash[a[l-1]]++;

            if(hash[a[l-1]]==1)

                ans+=1;

            l--;

        }

        while(r>query[i].right)

        {

            hash[a[r]]--;

            if(hash[a[r]]==0)

                ans-=1;

            r--;

        }

       //saving the ans values in answer array based on actual index or order

//given in input which is saved in index in query structure

        answer[query[i].index]=ans;

    }

 //printing the answer

    for(i=0;i<q;i++)

{

    printf("%d\n",answer[i]);

}

    return 0;

}

Happy Coding ....

No comments:

Post a comment