Solve three algorithmic tasks in Python

Implement in Python three tasks.

1. Movie Ratings (DP): Given an integer array ratings of length n, return both (a) the length of the longest strictly increasing subsequence (LIS) and (b) one valid LIS as a list of 1-based indices. Explain your DP formulation (state, transition) and provide code. Constraints: 1 ≤ n ≤ 200000; ratings[i] can be any 32-bit signed integer. Target complexity: O(n log n) time, O (n) memory.

2. Array Challenge (optimize with a tree structure): You are given n and an initial array a[1..n], followed by q operations of two types: (i) "add i x" — add integer x to a[i]; (ii) "sum l r" — output the sum of a[l..r], inclusive. Constraints: 1 ≤ n, q ≤ 200000. A naive O (n) per query will time out; implement an O(log n) per-operation solution using a Fenwick tree or segment tree.

3. Update Release Scheduler (sort and compare two lists): You receive two unsorted lists of integers: releases[0..n-1] (timestamps when builds become available) and windows[0..m-1] (deployment windows). Produce an array schedule[0..m-1] where schedule[j] is the timestamp of the latest release ≤ windows[j] that has not been assigned to any earlier window; if no release is available, set schedule[j] = -1. If multiple releases qualify for a window, choose the one with the greatest timestamp. Approach should sort both lists and scan with two pointers. Target complexity: O((n + m) log(n + m)) time, O(

4. extra space aside from outputs.