This code implements a "ReadOnlySegment" tree for a known array of values. It supports a (range combining) query like a normal segment tree, although this is not used in this problem. In addition, it implements Eric's 'countLeqThan' method that determines the maximum continous range left of a start index (leftbound) that is less than a given max…

MaximalSequence.java

/*
 * Maximal sequence inspired by Eric's segment tree idea.
 * Using Hassan's original segment tree code implementation.
 * 
 * @author godmar
 */
import java.util.*;

public class MaximalSequence
{
    @SuppressWarnings("unchecked")
    public static void main(String []av) {
        Scanner _s = new Scanner(System.in);    // slow scanner
        int n = _s.nextInt();
        Set [] a = new Set[n];
        for (int i = 0; i < n; i++)
            a[i] = Collections.singleton(_s.nextInt());

        /* Construct a read-only segment tree for this problem. 
         * The type of the elements in the segment tree are integer sets.
         */
        ReadonlySegmentTree<Set<Integer>> st = new ReadonlySegmentTree<Set<Integer>>(a) {
            // The empty set is the identity
            Set<Integer> getIdentity() { return Collections.emptySet(); }
            // The combine operation is set union
            Set<Integer> combine(Set<Integer> left, Set<Integer> right) { 
                HashSet<Integer> hset = new HashSet<>(left);
                hset.addAll(right);
                return hset;
            }
            // The less than operator is a subset test
            boolean isLessThan(Set<Integer> a, Set<Integer> b) {
                return b.containsAll(a);    // a is a subset of b
            }
        };

        int q = _s.nextInt();
        for (int k = 0; k < q; k++) {
            final int i = _s.nextInt();
            int m = _s.nextInt();
            final Set<Integer> querySet = new HashSet<>();
            for (int j = 0; j < m; j++)
                querySet.add(_s.nextInt());

            int answer = st.countLeqThan(i-1, querySet);
            System.out.println(answer);
        }
    }

    public static abstract class ReadonlySegmentTree<T>
    {
        // specify monoid operations by subclassing
        abstract T getIdentity();               // identity
        abstract T combine(T left, T right);    // assoc op
        // only need for countLeqThan
        boolean isLessThan(T a, T b) { throw new Error("not implemented"); }

        T [] values;        // underlying array (this tree does not support updates)
        Node root; 
        ReadonlySegmentTree(T [] v) {
            this.values = v;
            this.root = new Node(0, v.length - 1);
        }

        class Node {
            int start;   // start of range this node represents
            int end;     // end of range, inclusive
            T value;     // combined results of range [start, end]
            Node left, right;   // children representing [start, mid], and [mid+1, end]
             
            // populate tree with given array of elements.
            private Node(int s, int e) {
                start = s;
                end = e;

                if (s == e) {
                    value = values[s];
                } else { 
                    int mid = (s + e)/2;
                    left = new Node(s, mid);
                    right = new Node(mid + 1, e);
                    value = combine(left.value, right.value);
                }
            }
                      
            // is this segment entirely outside [from, to]?
            protected boolean isOutsideRange(int from, int to) {
                return to < start || from > end;
            }

            // is this segment entirely within [from, to]?
            protected boolean isInsideRange(int from, int to) {
                return from <= start && end <= to;
            }

            // compute aggregate over [from, to]
            public T query(int from, int to) {
                if (isOutsideRange(from, to))
                    return getIdentity();
             
                if (isInsideRange(from, to))
                    return value;
                else
                    return combine(left.query(from, to), right.query(from, to));  
            }

            public String toString() {
                return "[" + start + ", " + end + "]: " + value;
            }

            // count how many consecutive values in this segment are both
            // at an index >= leftbound and are <= maxValue
            int countLeqThan(int leftbound, T maxValue)
            {
                if (!isLessThan(values[leftbound], maxValue))
                    return 0;

                if (isLessThan(value, maxValue))    // entire range is less
                    return end - leftbound + 1;

                if (left.end < leftbound) {
                    return right.countLeqThan(leftbound, maxValue);
                } else {
                    int count = left.countLeqThan(leftbound, maxValue);
                    // if all of [leftbound, left.end] were less, check right
                    if (count == left.end - leftbound + 1)  
                        count += right.countLeqThan(right.start, maxValue);
                    return count;
                }
            }
        }

        /* Count how many elements starting from [left, left+1, ...]
         * are <= maxValue */
        int countLeqThan(int left, T maxValue) {
            return root.countLeqThan(left, maxValue);
        }
    }
}