Solve order-statistics and XOR-triplet problems

You are given two separate algorithmic problems.

Problem 1: Count smaller elements to the right

Given an integer array nums of length n, for each index i compute the number of indices j > i such that nums[j] < nums[i].

• Input: nums (may contain duplicates and negative values)
• Output: an array ans of length n , where ans[i] is the count of smaller elements strictly to the right of i
• Constraints (typical interview scale): 1 ≤ n ≤ 10^5 , |nums[i]| ≤ 10^9
• Expectation: design an appropriate data structure / approach to meet an efficient time bound (e.g., ~ O(n log n) ), and be ready to discuss complexity and edge cases.

Problem 2: Count triplets satisfying an XOR inequality on subarray XORs

You are given n integers a1, a2, ..., an (1 ≤ n ≤ 10^5, 0 ≤ ai ≤ 10^9). Define the function

• F(i, j) = ai XOR a(i+1) XOR ... XOR aj for 1 ≤ i ≤ j ≤ n .

Count the number of index triplets (x, y, z) with 1 ≤ x ≤ y ≤ z ≤ n such that:

• F(x, y) XOR F(y, z) > F(x, z) .

Notes:

• XOR is the bitwise exclusive-or.
• The output should be the count of valid triplets (an O(n^3) enumeration is not acceptable for the given constraints).
• You may assume the answer fits in 64-bit signed integer unless otherwise specified.
• Interview expectation: simplify using prefix XOR and reason about the inequality bit-by-bit to derive an efficient algorithm.