SLAEL using Segment Tree

I was trying to solve SLAEL using Segment Tree. I built the segment tree in which every node contains largest and second largest element in the segment. But I was not able to figure out how to query this segment tree for a particular k.

Is it not possible to apply segment tree here

Initial solution of setter was binary search +Segment tree. But we noticed a simple solution based of difference of indices where A_i>k

Can you please help me with Segment tree approach. And please tell me whether my approach is correct or wrong.

I solved using Segment Tree but got an WA .
Code Seems to work right .
Anybody can help me with the mistakes ?

#include <iostream>
#include<bits/stdc++.h>

#define ll          long long

#define pb          push_back
#define mp          make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()


#define endl        '\n'
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define repr(i,a,b) for(long long i=a;i>=b;i--)


using namespace std;
long long getMid(long long s, long long e)  
{ 
    return s + (e - s) / 2; 
} 
  
/*  A recursive function to get the sum of 
    values in given range of the array.  
    The following are parameters for this 
    function. 
  
    st       -> Polong longer to segment tree 
    node     -> Index of current node in  
                the segment tree . 
    ss & se  -> Starting and ending indexes  
                of the segment represented 
                by current node, i.e., st[node] 
    l & r    -> Starting and ending indexes  
                of range query */
long long MaxUtil(long long* st, long long ss, long long se, long long l,  
            long long r, long long node) 
{ 
    // If segment of this node is completely 
    // part of given range, then return  
    // the max of segment 
    if (l <= ss && r >= se) 
        return st[node]; 
  
    // If segment of this node does not 
    // belong to given range 
    if (se < l || ss > r) 
        return -1; 
  
    // If segment of this node is partially 
    // the part of given range 
    long long mid = getMid(ss, se); 
      
    return max(MaxUtil(st, ss, mid, l, r,  
                       2 * node + 1), 
               MaxUtil(st, mid + 1, se, l,  
                       r, 2 * node + 2)); 
} 

long long getMax(long long* st, long long n, long long l, long long r) 
{ 
    // Check for erroneous input values 
    if (l < 0 || r > n - 1 || l > r)  
    { 
        printf("Invalid Input"); 
        return -1; 
    } 
  
    return MaxUtil(st, 0, n - 1, l, r, 0); 
} 
  
// A recursive function that constructs Segment 
// Tree for array[ss..se]. si is index of  
// current node in segment tree st 

void updateValue(long long arr[], long long* st, long long ss, long long se,  
                 long long index, long long value, long long node) 
{ 
    if (index < ss || index > se)  
    { 
        cout << "Invalid Input" << endl; 
        return; 
    } 
      
    if (ss == se)  
    {    
        // update value in array and in segment tree 
        arr[index] = value; 
        st[node] = value; 
    } 
    else { 
            long long mid = getMid(ss, se); 
              
            if (index >= ss && index <= mid) 
                updateValue(arr, st, ss, mid, index,  
                            value, 2 * node + 1); 
            else
                updateValue(arr, st, mid + 1, se,  
                            index, value, 2 * node + 2); 
              
            st[node] = max(st[2 * node + 1],  
                       st[2 * node + 2]); 
    } 
    return; 
} 
long long constructSTUtil(long long arr[], long long ss, long long se,  
                    long long* st, long long si) 
{ 
    // If there is one element in array, store 
    // it in current node of segment tree and return 
    if (ss == se)  
    { 
        st[si] = arr[ss]; 
        return arr[ss]; 
    } 
  
    // If there are more than one elements, then 
    // recur for left and right subtrees and  
    // store the max of values in this node 
    long long mid = getMid(ss, se); 
      
    st[si] = max(constructSTUtil(arr, ss, mid, st,  
                                 si * 2 + 1), 
                 constructSTUtil(arr, mid + 1, se,  
                                 st, si * 2 + 2)); 
      
    return st[si]; 
} 
  
/* Function to construct segment tree from given array. 
   This function allocates memory for segment tree.*/
long long* constructST(long long arr[], long long n) 
{ 
    // Height of segment tree 
    long long x = (long long)(ceil(log2(n))); 
  
    // Maximum size of segment tree 
    long long max_size = 2 * (long long)pow(2, x) - 1; 
  
    // Allocate memory 
    long long* st = new long long[max_size]; 
  
    // Fill the allocated memory st 
    constructSTUtil(arr, 0, n - 1, st, 0); 
  
    // Return the constructed segment tree 
    return st; 
} 

int  main()
{
  
  // ios::sync_with_stdio(0);
  // cin.tie(0);
  // cout.tie(0);

 long long tc;
 cin>>tc;
while(tc--)
{
	long long n,k;
	cin>>n>>k;

	long long arr[n];
	long long arrc[n];

	for(long long i=0;i<n;i++)
	{
	
		cin>>arr[i];
		arrc[i]=arr[i];
	}

	long long* st = constructST(arr, n); 
	
long long max_size=0;
	for(long long a=0;a<n;a++)
		{
			//arr=arrc;
copy(arrc, arrc + n, arr);
long long* st = constructST(arr, n); 


			for(long long b=a;b<n;b++)
				{
					copy(arrc, arrc + n, arr);
					long long* st = constructST(arr, n); 


					long long val =getMax(st, n, a, b) ;
					
					if(val>k)
					{
						for(long long i=a;i<=b;i++)
	{
		if(arr[i]==val)
		{
			updateValue(arr, st, 0, n - 1, i, -1, 0);
		}
	}
	long long val1 =getMax(st, n, a, b) ;
	
	if(val1<=k && val1!=-1)
	{
		// cout<<"yeyeye"<<endl;

		// cout<<a+1<<" "<<b+1<<endl;
		// cout<<val<<" "<<val1<<endl;
		max_size=max(max_size,(b-a+1));
		// cout<<max_size<<endl;
	}



					}

				
				}
			}

cout<<max_size<<endl;



}

  }

Your code fails at:
1
3 3
78 11 80

Ans: 1
Your output: 0

(All credits to ‘Bug Finder’ available at https://github.com/sarthakmanna/Bug-Finder for free). XD XD

2 Likes

Seems like overkill. A simple scan through the array will do the job.

1 Like

I solved it using Binary Search + Segment tree ,link text

But it is giving me tle ,may be because in the worst case the time complexity would be N*log(N)*log(N).Can some one look into my code and give some tips to reduce the time complexity.Any help is highly appreciated.Thanks in advance.

@mickey321 This can be solved using sliding window approach solution , which takes O(n) complexity

#HERE is a neat segment tree + binary search approach
#which is O(n*log^2(n)) and it is giving TLE.

Original solution is O(n) which is HERE

What i did is finding all the contiguous sub sequences and then comparing its largest and second largest element with k.

But unfortunately its giving TLE.

Can Someone help me with some other way

My Solution : https://www.codechef.com/viewsolution/21221508

For those who are unable to access:


num1=int(input())
for _ in range(num1):
    num2=map(int,raw_input().strip().split())
    num3=map(int,raw_input().strip().split())
    m=[num3[i:i+j] for i in range(0,num2[0]) for j in range(1,num2[0]-i+1)]
    m=sorted(m, key=len)[::-1]
    for k in m:
        p=sorted(list(set(k)))
        if len(p)>1:
            if num2[1]<p[-1] and num2[1]>=p[-2]:
                print len(k)
                break
        elif len(p)==1:
            if num2[1]<p[-1]:
                print 1
                break
            
</pre>

you just need to mark index whose value>k and then a simple logical approach will give you O(n) solution. You can have a look at my optimized soln which is O(n).
I have implemented both of them XD

you just need to mark index whose value>k and then a simple logical approach will give you O(n) solution. You can have a look at my optimized soln which is O(n).

you just need all triplets of marked indices such that their(all three marked index’s ) value is >k and no element except these three is >k in range [1st index , 3rd index]
and you find a segment which is excluding 1st and 3rd index.
check all such segments and output maximum size segment.

Thanks @sarthakmanna .
Still it gives TLE . How to optimise ?

So basically solutions including Binary search and Segment tree were not intended.
In the worst case there would be about 400 * 1000000=4*10^8 operations.Shouldn’t it pass in 2 sec time limit?

Hey i have also done this question using Segment Tree + Binary Search and i know that it is an overkill but still i am getting wrong answer and not TLE . So if can anyone plzz provide me any case where it may be failing .
Solution link : https://ideone.com/fFD7cM
Plzz help!!

I thought the same thing and wrote the code but as you can see merging two nodes of segment tree is O(1) but then too it’s a complex logic so I think it will multiply it by maybe by 2 so it would be 8*10^8 iterations so it won’t pass…
In short basic problem is constant associated with Big-O notation.

Thanks for your valuable feedback @l_returns

1 Like

welcome :slight_smile:

If I recall, initially the constraints were lower when segment tree+Binary search solution was proposed. I think they were raised so that SegTree+Binary search gets TLE.

//