Frequent values

explain ur idea in brief...that will be easier for me to tell if ur idea has any bug or not.....
and if u want to know how i have solved it ,i can share it too....

yes, i've used segment tree too........
but before i go into details of my solution, answer my following queries:-

1.you seemed to be new to the use of segment tree, because segment tree is not intended to store those index values of the range, rather they can be easily mapped with the node no. whenever you are going to traverse the tree......
am i right?

2.what do you mean by that?

how is it feasible?

3.you effectively store only the maximum of the range at each node.....then there is no possibility that you can combine the left_child and right_child to generate the necessary information for the parent node...how have you done that?
(i think one needs atleast 3 things to be stored at each node)

reply me soon.....

it seems u have not used segment tree(atleast as far as i know, this is not the standard way a segment tree should be formed)..
in segment tree, if the parent node is holding the information abut the range [l,r], then left_child should keep [l,m] and right_child [m+1,r].......... where m = floor((l+r)/2)

now,I got ur idea little bit (but i still dont understand how u ve written qry)......
however, i'm telling u a lot simpler approach that i follow (actually this is the most convenient way how u should solve problems with segment tree):-

at each node u r storing 1.max_freq(mf), 2.freq_of_leftmost_element(lf) ,3.rf

for leaf nodes(containg exactly 1 element):- mf=lf=rf=1
for any nonleaf node containing segment[l,r]:- m=floor[(l+r)/2]
mf= max{mf_of_lt_chld, mf_of_rt_chld , rf_of_lt_chld+lf_of_rt_chld(if exist when a[m]==a[m+1])}
lf =lf_of_lt_chld+lf_of_rt_chld(if exist when a[l]==a[m+1])
rf can be calculated in the same way

just defining the appropriate relation between parent node and child nodes for calculating the necessary informations, u can easily solve such problems using segment trees....if u go with some ad hoc ideas , u need to find new ideas for each and every problem though they are pretty similar problem......
using this concept, u can solve GSS1,GSS3,GSS5,BRCKTS,KGSS too.........

hope, this will help u.......

I getting time limit exceeded for this code can anyone pls help

#include <iostream>
using namespace std;
struct node
{
	int lf,mf,rf;
};
node ar[300000];
int max1(int a,int b,int c)
{
	if(a>b)
		b=a;
	if(c>b)
		b=c;
	return b;
}
void insert(int a[],int start,int end,int node)
{
	if(start==end)
	{
		ar[node].lf=1;
		ar[node].mf=1;
		ar[node].rf=1;
	}
	else
	{
		insert(a,start,(start+end)/2,2*node);
		insert(a,(start+end)/2+1,end,2*node+1);
		int m=(start+end)/2;
		if(a[m]==a[m+1])
			ar[node].mf=max1(ar[2*node].mf,ar[2*node+1].mf,ar[2*node].rf+ar[2*node+1].lf);
		else
			ar[node].mf=(ar[2*node].mf>ar[2*node+1].mf?ar[2*node].mf:ar[2*node+1].mf);
		if(a[start]==a[m+1])
			ar[node].lf=ar[2*node+1].lf+ar[2*node].lf;
		else
			ar[node].lf=ar[2*node].lf;
		if(a[m]==a[end])
			ar[node].rf=ar[2*node+1].rf+ar[2*node].rf;
		else
			ar[node].rf=ar[2*node+1].rf;
	}
}
int query(int a[],int start,int end,int i,int j,int node)
{
	int p1, p2;
	if (i > end || j < start)
		return -1;
	if (start >= i && end <= j)
		return ar[node].mf;
	p1 = query(a,start,(start+end)/2,i,j,2*node);
	p2 = query(a,(start+end)/2+1,end,i,j,2*node+1);
	if (p1 == -1)
		return p2;
	if (p2 == -1)
		return p1;
	if(p1>p2)
		return p1;
	else
		return p2;
}
int main()
{
	while(1)
	{
		int n,q;
		cin>>n;
		if(n==0)
			break;
		int a[n];
		cin>>q;
		for(int i=0;i<n;i++)
			cin>>a[i];
		insert(a,0,n-1,1);
		int t1,t2,f;
		for(int i=0;i<q;i++)
		{
			cin>>t1>>t2;
			f=query(a,0,n-1,t1-1,t2-1,1);
			if(f!=-1)
				cout<<f<<endl;
		}
	}
}

First of all use the code tags to put the code. The first post has it, so it should be obvious how to do that. Your code is very hard to read and because of that you're making it difficult for people to help you.

I didn't check the program logic, just tried to analyse the complexity itself. I think that it's correctly implemented O(N*log(N)) and I think that's the right complexity for this problem. The recursive calls also don't seem to loop for any ranges.

The constant can be reduced though. I think the recursive calls could be removed from insert function, but that's probably not the problem. What is eating a lot of time here, and maybe causes TLE, are the arithmetic operations. You have a lot of "x*2" and "x/2" expressions. Try changing all of them to "x<>1" respectively. If you haven't heard of them, those are bitwise shifts. You can read more about them on the net. When you're multiplying or dividing by a power of 2, you can always express that with a shift and it will be much faster.

If that doesn't help, I guess you should try a different approach. For example: merging equal values into single blocks with data about the size or range:
{-1,-1,-1,2,2,2,2} => {(-1,3),(2,4)}
{-1,-1,-1,2,2,2,2} => {(-1,0,3),(2,3,7)}

It will be harder to implement and I don't think that's necessary here, but I don't have other ideas at the moment.

The program from first post seems very similar and it was getting WA, so maybe you have some looping problem that I missed. Maybe somebody else will find something more.

My implementation is very similar with yeduguru... except what the querry functions returns . Any way im getting Tle also... im not getting what is the reason. I got RTE when my array size was [200020]... But if the input size is 100000 at it best then the number of maximum nodes is 2*100000-1. So it shud have not given RTE. I increased it to 300000 then Tle !!!! . NY suggestion highly appreciated !!!

dipto very nice explaination. but i want to ask one thing, left most element ? what exactly do you mean by that ?

should it be max frequency in the left array ? (i mean lf) ? please correct me.

thanks.

lf is the frequency of the left most element in a segment.
for example, if a segment looks like [1,1,1,2,5,5,9]
then, lf = frequency of 1 i.e. 3

please let me know if you still have any doubt.

dipto, seriously your these 2 posts make me to do GSS1, GSS3, FREQUENT in 2 days only. wow.... thanks alot.. trying to do GSS5.. but i think it is a little bit tuff...

Get back to me if u need any help.
Happy coding.

Hello everyone. I am solving this problem and I get WA. I use a different approach that any of you talk about in this post. I tried a looot of testcases and they were all incorect. Please check my code. Thanks:)

#include <cstdio>
#include <algorithm>
using namespace std;
struct val {
    int f, l;
};
struct n {
    int v, c;
};
n tree[ 600000 ];
val array[ 300000 ];
int A[ 200000 ];
void init( int node, int i, int j ) {
    if ( i == j ) {
        tree[ node ] = ( ( n ) { A[ i ], 1 } );
    }
    else {
        init( node * 2, i, ( i + j ) / 2 );
        init( node * 2 + 1, ( i + j ) / 2 + 1, j );
        int v1 = tree[ node * 2 ].v, v2 = tree[ node * 2 + 1 ].v, c1 = tree[ node * 2 ].c, c2 = tree[ node * 2 + 1 ].c;
        if ( array[ v1 ].l > ( i + j ) / 2 ) {
            if ( array[ v1 ].l > j ) {
                c1 += j - ( i + j ) / 2;
            }
            else {
                c1 += array[ v1 ].l - ( i + j ) / 2;
            }
        }
        if ( array[ v2 ].f <= ( i + j ) / 2 ) {
            if ( array[ v2 ].f < i ) {
                c2 += ( i + j ) / 2 - i + 1;
            }
            else {
                c2 += ( i + j ) / 2 + 1 - array[ v2 ].f; 
            }
        }
        if ( c1 > c2 ) {
            tree[ node ] = ( ( n ) { v1, c1 } );
        }
        else {
            tree[ node ] = ( ( n ) { v2, c2 } );
        }
    }
}
n query( int node, int a, int b, int l, int r ) {
    if ( a > b || a > r || b < l ) {
        return ( ( n ) { -1, 0 } );
    }
    else if ( a >= l && b <= r ) {
        return tree[ node ];
    }
    n p1 = query( node * 2, a, ( a + b ) / 2, l, r );
    n p2 = query( node * 2 + 1, ( a + b ) / 2 + 1, b, l, r );
    if ( p1.v == -1 ) {
        return p2;
    }
    if ( p2.v == -1 ) {
        return p1;
    }
    if ( array[ p1.v ].l > ( a + b ) / 2 ) {
        if ( array[ p1.v ].l > b ) {
            p1.c += b - ( a + b ) / 2;
        }
        else {
            p1.c += array[ p1.v ].l - ( a + b ) / 2;
        }
    }
    if ( array[ p2.v ].f <= ( a + b ) / 2 ) {
        if ( array[ p2.v ].f < a ) {
            p2.c += ( a + b ) / 2 - a + 1;
        }
        else {
            p2.c += ( a + b ) / 2 + 1 - array[ p2.v ].f;
        }
    }
    if ( p1.c > p2.c ) {
        return p1;
    }
    else {
        return p2;
    }
}
int main() {
    int i, j, N, Q, l, r;
    while ( 1 ) {
        scanf( "%d", &N );
        if ( N == 0 ) {
            return 0;
        }
        scanf( "%d", &Q );
        for ( i = 0; i <= 250000; ++i ) {
            array[ i ] = ( ( val ) { 1000000, -1 } );
        }
        for ( i = 0; i < N; ++i ) {
            scanf( "%d", A + i );
            A[ i ] += 100001;
            array[ A[ i ] ].f = min( array[ A[ i ] ].f, i );
            array[ A[ i ] ].l = max( array[ A[ i ] ].l, i );
        }
        init( 1, 0, N - 1 );
        for ( i = 0; i < Q; ++i ) {
            scanf( "%d%d", &l, &r );
            printf( "%d\n", query( 1, 0, N - 1, l - 1, r - 1 ).c );
        }
    }
}

Hi can someone provide me with some edge case, and few more test case. My solution run fine for many test cases still it is giving wrong answer.
Thanks

There are not really any special test cases here. You should be able to brute force generate many test cases as the constraints are simple.