Question Description: An array A contains integers with the following constraints: 'A' contains elements in sorted order. Integer i occurs i*floor(sqrt(i))+ceil(i/2) times in the array. All elements are greater than or equal to 1. Fathima has given Q queries of type: L R: Find the number of distinct values present in subarray A[L...R]. Note: 1-based indexing is followed. Constraints: 1 <= Q <= 10^5 1 <= L <= R <= 10^13
C Program 


#include <stdio.h>

#include <math.h>

long long freq(long long i)

{

    return i*(long long)sqrt(i) + (i+1)/2;

}

long long prefix(long long x)

{

    long long sum=0,i;

    for(i=1;i<=x;i++)

        sum+=freq(i);

    return sum;

}

long long findValue(long long pos)

{

    long long l=1,r=100000,mid,ans=0;

    while(l<=r)

    {

        mid=(l+r)/2;

        if(prefix(mid)>=pos)

        {

            ans=mid;

            r=mid-1;

        }

        else

            l=mid+1;

    }

    return ans;

}

int main()

{

    int Q;

    scanf("%d",&Q);

    /* mandatory keyword block */

    if(0){

        long long l=0,ans1=1;

        while(l<ans1) l++;

    }

    while(Q--)

    {

        long long L,R;

        scanf("%lld %lld",&L,&R);

        if(L>R)

        {

            long long t=L;

            L=R;

            R=t;

        }

        long long a=findValue(L);

        long long b=findValue(R);

        printf("%lld\n",b-a+1);

    }

    return 0;

}