Hello I'm trying to solve problem SUPPER from SPOJ. I think a number x[n] is defined to be super if length of LIS[n] (longest increasing subsequence ending at x[n]) plus LDC[n] (length of longest decreasing subsequence ending at x[n] , when reading the input permutation in reverse) equals the length of longest increasing subsequence of the entire input permutation . Solution Complexity is O(N log N). I'm using Segment Tree , suppose node n covers interval [i .. j] , then tree[n] = max { LIS [ x [ i ] ] , LIS [ x [ i + 1 ] ] , ... , LIS [ x [ j ] ] }

I used an O(N^2) solution to compare my answers against. Thanks a lot in advance for any help.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 100001;
int N;
int x[MAXN];
int LIS[MAXN];
int LDS[MAXN];
int lis[MAXN];
int lds[MAXN];
int tree[4 * MAXN];
int best;

int query(int node , int s , int e , int qs , int qe){
   if(s > qe || e < qs)
      return 0;
   if(s >= qs && e <= qe)
      return tree[node];
   return max(query(2 * node , s , (s+e)/2 , qs , qe) , query(2 * node + 1 , (s+e)/2+1, e , qs , qe));
}
void update(int node , int s , int e , int idx , int val){
   if(s == e && s == idx){
      tree[node] = val;
      return;
   }
   if(s > idx || e < idx)
      return;
   update(2 * node , s , (s+e)/2 , idx , val);
   update(2 * node + 1 , (s+e)/2 + 1 , e , idx , val);
   tree[node] = max(tree[2 * node] , tree[2 * node + 1]);
   return;
}

int main(){
   scanf("%d" , &N);
   for(int n = 1 ; n <= N ; n++)
      scanf("%d" , &x[n]);
   for(int n = 1 ; n <= N ; n++){
      LIS[n] = 1 + query(1 , 1 , N , 1 , x[n] - 1);
      update(1 , 1 , N , x[n] , LIS[n]);
      best = max(best , LIS[n]);
   }
   memset(tree , 0 , sizeof(tree));
   for(int n = N ; n >= 1 ; n--){
      LDS[n] = 1 + query(1 , 1 , N , x[n] + 1 , N);
      update(1 , 1 , N , x[n] , LDS[n]);
   }
   vector < int > res;
   for(int n = 1 ; n <= N ; n++){
	  // printf("%d %d\n" , LIS[n],LDS[n]);
      if(LIS[n] + LDS[n] - 1 == best)
         res.push_back(x[n]);
   }

   
   /*
   for(int n = 1 ; n <= N ; n++){
       lis[n] = 1;
	   for(int h = 1 ; h < n ; h++)
		   if(x[n] > x[h])
			   lis[n] = max(lis[n] , lis[h] + 1);
   }
   for(int n = N ; n >= 1 ; n--){
       lds[n] = 1;
	   for(int h = N  ; h > n ; h--)
		   if(x[n] < x[h])
		     lds[n] = max(lds[n] , lds[h] + 1);
   }
   printf("\n\n");
   for(int n =  1 ; n <= N ; n++)
	   printf("%d %d\n" , lis[n] , lds[n]);
   
  */

   sort(res.begin() , res.end());
   printf("%d\n" , res.size());
   for(int i = 0 ; i < (int)(res.size()) - 1 ; i++)
      printf("%d " , res[i]);
   printf("%d\n" , res.back());
   return 0;
}

Example test case :

Input : 
25
19 6 7 11 5 9 8 18 14 4 23 1 13 10 25 2 16 3 12 15 21 17 20 22 24 

Output (by both O(N log N) and O(N^2) solutions): 
11
6 7 8 9 10 12 15 17 20 22 24