Número de contagem de subseqüências crescentes: O (NlogN)
Dado um array arr [] de comprimento N , a tarefa é encontrar o número de subseqüências estritamente crescentes em um dado array.
Exemplos:
Entrada: arr [] = {1, 2, 3}
Resultado: 7
Todas as subseqüências crescentes serão:
1) {1}
2) {2}
3) {3}
4) {1, 2}
5) {1 , 3}
6) {2, 3}
7) {1, 2, 3}
Assim, answer = 7
Input: arr [] = {3, 2, 1}
Output: 3
Abordagem: uma abordagem O (N 2 ) já foi discutida neste artigo. Aqui, uma abordagem com tempo O (NlogN) usando a estrutura de dados da árvore de segmento será discutida.
No artigo anterior, a relação de recorrência utilizada foi:
dp [i] = 1 + somatório (dp [j]), onde i <jarr [i]
Devido ao fato de que toda a subarray arr [i + 1 ... n-1] estava sendo iterada para cada estado, um tempo O (N) extra estava sendo usado para resolvê-lo. Assim, a complexidade era (E 2 ).
A ideia é evitar a iteração do loop extra O (N) para cada estado e reduzir sua complexidade para Log (N).
Premissa: O número de subseqüências estritamente crescentes começando de cada índice 'i', onde i é maior que um número 'k' é conhecido.
Usando esta suposição acima, o número de subseqüências crescentes começando no índice 'k' pode ser encontrado no tempo log (N).
Portanto, a soma de todos os índices 'i' maiores que 'k' deve ser encontrada. Mas o problema é arr [i] deve ser maior do que arr [k]. Para lidar com o problema, pode-se fazer o seguinte:
1. Para cada elemento da array, seu índice é encontrado na array foi classificado. Exemplo - {7, 8, 1, 9, 4} Aqui, as classificações serão:
7 -> 3
8 -> 4
1 -> 1
9 -> 5
4 -> 2
2. Uma árvore de segmento de comprimento 'N' é criada para responder a uma consulta de soma de intervalo.
3. Para responder à consulta enquanto resolve o índice 'k', a classificação de arr [k] é encontrada primeiro. Vamos dizer que a classificação é R . Então, na árvore de segmento, a soma do intervalo do índice {R a N-1} é encontrada.
4. Em seguida, a árvore de segmento é atualizada por ponto como segmento- (R-1) é igual a 1 + segtree-query (R, N-1) + segtree-query (R-1, R-1)
Abaixo está a implementação da abordagem acima:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 10000
// Segment tree array
int seg[3 * N];
// Function for point update in segment tree
int update(int in, int l, int r, int up_in, int val)
{
// Base case
if (r < up_in || l > up_in)
return seg[in];
// If l==r==up
if (l == up_in and r == up_in)
return seg[in] = val;
// Mid element
int m = (l + r) / 2;
// Updating the segment tree
return seg[in] = update(2 * in + 1, l, m, up_in, val)
+ update(2 * in + 2, m + 1, r, up_in, val);
}
// Function for the range sum-query
int query(int in, int l, int r, int l1, int r1)
{
// Base case
if (l > r)
return 0;
if (r < l1 || l > r1)
return 0;
if (l1 <= l and r <= r1)
return seg[in];
// Mid element
int m = (l + r) / 2;
// Calling for the left and the right subtree
return query(2 * in + 1, l, m, l1, r1)
+ query(2 * in + 2, m + 1, r, l1, r1);
}
// Function to return the count
int findCnt(int* arr, int n)
{
// Copying array arr to sort it
int brr[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting array brr
sort(brr, brr + n);
// Map to store the rank of each element
map<int, int> r;
for (int i = 0; i < n; i++)
r[brr[i]] = i + 1;
// dp array
int dp[n] = { 0 };
// To store the final answer
int ans = 0;
// Updating the dp array
for (int i = n - 1; i >= 0; i--) {
// Rank of the element
int rank = r[arr[i]];
// Solving the dp-states using segment tree
dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
// Updating the final answer
ans += dp[i];
// Updating the segment tree
update(0, 0, n - 1, rank - 1,
dp[i] + query(0, 0, n - 1, rank - 1, rank - 1));
}
// Returning the final answer
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 10, 9 };
int n = sizeof(arr) / sizeof(int);
cout << findCnt(arr, n);
return 0;
}// Java implementation of the approach
import java.util.*;
class GFG
{
static final int N = 10000;
// Segment tree array
static int[] seg = new int[3 * N];
// Function for point update in segment tree
static int update(int in, int l, int r, int up_in, int val)
{
// Base case
if (r < up_in || l > up_in)
return seg[in];
// If l==r==up
if (l == up_in && r == up_in)
return seg[in] = val;
// Mid element
int m = (l + r) / 2;
// Updating the segment tree
return seg[in] = update(2 * in + 1, l, m, up_in, val) +
update(2 * in + 2, m + 1, r, up_in, val);
}
// Function for the range sum-query
static int query(int in, int l, int r, int l1, int r1)
{
// Base case
if (l > r)
return 0;
if (r < l1 || l > r1)
return 0;
if (l1 <= l && r <= r1)
return seg[in];
// Mid element
int m = (l + r) / 2;
// Calling for the left and the right subtree
return query(2 * in + 1, l, m, l1, r1) +
query(2 * in + 2, m + 1, r, l1, r1);
}
// Function to return the count
static int findCnt(int[] arr, int n)
{
// Copying array arr to sort it
int[] brr = new int[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting array brr
Arrays.sort(brr);
// Map to store the rank of each element
HashMap<Integer, Integer> r = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
r.put(brr[i], i + 1);
// dp array
int dp[] = new int[n];
// To store the final answer
int ans = 0;
// Updating the dp array
for (int i = n - 1; i >= 0; i--)
{
// Rank of the element
int rank = r.get(arr[i]);
// Solving the dp-states using segment tree
dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
// Updating the final answer
ans += dp[i];
// Updating the segment tree
update(0, 0, n - 1, rank - 1, dp[i] +
query(0, 0, n - 1, rank - 1, rank - 1));
}
// Returning the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 10, 9 };
int n = arr.length;
System.out.print(findCnt(arr, n));
}
}
// This code is contributed by PrinciRaj1992# Python3 implementation of the approach
N = 10000
# Segment tree array
seg = [0] * (3 * N)
# Function for point update in segment tree
def update(In, l, r, up_In, val):
# Base case
if (r < up_In or l > up_In):
return seg[In]
# If l==r==up
if (l == up_In and r == up_In):
seg[In] = val
return val
# Mid element
m = (l + r) // 2
# Updating the segment tree
seg[In] = update(2 * In + 1, l, m, up_In, val) + update(2 * In + 2, m + 1, r, up_In, val)
return seg[In]
# Function for the range sum-query
def query(In, l, r, l1, r1):
# Base case
if (l > r):
return 0
if (r < l1 or l > r1):
return 0
if (l1 <= l and r <= r1):
return seg[In]
# Mid element
m = (l + r) // 2
# CallIng for the left and the right subtree
return query(2 * In + 1, l, m, l1, r1)+ query(2 * In + 2, m + 1, r, l1, r1)
# Function to return the count
def fIndCnt(arr, n):
# Copying array arr to sort it
brr = [0] * n
for i in range(n):
brr[i] = arr[i]
# Sorting array brr
brr = sorted(brr)
# Map to store the rank of each element
r = dict()
for i in range(n):
r[brr[i]] = i + 1
# dp array
dp = [0] * n
# To store the final answer
ans = 0
# Updating the dp array
for i in range(n - 1, -1, -1):
# Rank of the element
rank = r[arr[i]]
# Solving the dp-states using segment tree
dp[i] = 1 + query(0, 0, n - 1, rank, n - 1)
# UpdatIng the final answer
ans += dp[i]
# Updating the segment tree
update(0, 0, n - 1, rank - 1,dp[i] + query(0, 0, n - 1, rank - 1, rank - 1))
# Returning the final answer
return ans
# Driver code
arr = [1, 2, 10, 9]
n = len(arr)
print(fIndCnt(arr, n))
# This code is contributed by mohit kumar 29// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static readonly int N = 10000;
// Segment tree array
static int[] seg = new int[3 * N];
// Function for point update In segment tree
static int update(int In, int l, int r,
int up_in, int val)
{
// Base case
if (r < up_in || l > up_in)
return seg[In];
// If l==r==up
if (l == up_in && r == up_in)
return seg[In] = val;
// Mid element
int m = (l + r) / 2;
// Updating the segment tree
return seg[In] = update(2 * In + 1, l, m, up_in, val) +
update(2 * In + 2, m + 1, r, up_in, val);
}
// Function for the range sum-query
static int query(int In, int l, int r, int l1, int r1)
{
// Base case
if (l > r)
return 0;
if (r < l1 || l > r1)
return 0;
if (l1 <= l && r <= r1)
return seg[In];
// Mid element
int m = (l + r) / 2;
// Calling for the left and the right subtree
return query(2 * In + 1, l, m, l1, r1) +
query(2 * In + 2, m + 1, r, l1, r1);
}
// Function to return the count
static int findCnt(int[] arr, int n)
{
// Copying array arr to sort it
int[] brr = new int[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting array brr
Array.Sort(brr);
// Map to store the rank of each element
Dictionary<int, int> r = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
r.Add(brr[i], i + 1);
// dp array
int []dp = new int[n];
// To store the readonly answer
int ans = 0;
// Updating the dp array
for (int i = n - 1; i >= 0; i--)
{
// Rank of the element
int rank = r[arr[i]];
// Solving the dp-states using segment tree
dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
// Updating the readonly answer
ans += dp[i];
// Updating the segment tree
update(0, 0, n - 1, rank - 1, dp[i] +
query(0, 0, n - 1, rank - 1, rank - 1));
}
// Returning the readonly answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 10, 9 };
int n = arr.Length;
Console.Write(findCnt(arr, n));
}
}
// This code is contributed by PrinciRaj1992<script>
// Javascript implementation of the approach
var N = 10000;
// Segment tree array
var seg = Array(3*N).fill(0);
// Function for point update inVal segment tree
function update(inVal, l, r, up_in, val)
{
// Base case
if (r < up_in || l > up_in)
return seg[inVal];
// If l==r==up
if (l == up_in && r == up_in)
return seg[inVal] = val;
// Mid element
var m = parseInt((l + r) / 2);
// Updating the segment tree
seg[inVal] = update(2 * inVal + 1, l, m, up_in, val)
+ update(2 * inVal + 2, m + 1, r, up_in, val);
return seg[inVal];
}
// Function for the range sum-query
function query(inVal, l, r, l1, r1)
{
// Base case
if (l > r)
return 0;
if (r < l1 || l > r1)
return 0;
if (l1 <= l && r <= r1)
return seg[inVal];
// Mid element
var m = parseInt((l + r) / 2);
// Calling for the left and the right subtree
return query(2 * inVal + 1, l, m, l1, r1)
+ query(2 * inVal + 2, m + 1, r, l1, r1);
}
// Function to return the count
function findCnt(arr, n)
{
// Copying array arr to sort it
var brr = Array(n);
for (var i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting array brr
brr.sort((a, b)=> a-b);
// Map to store the rank of each element
var r = new Map();
for (var i = 0; i < n; i++)
r[brr[i]] = i + 1;
// dp array
var dp = Array(n).fill(0);
// To store the final answer
var ans = 0;
// Updating the dp array
for (var i = n - 1; i >= 0; i--) {
// Rank of the element
var rank = r[arr[i]];
// Solving the dp-states using segment tree
dp[i] = 1 + query(0, 0, n - 1, rank, n - 1);
// Updating the final answer
ans += dp[i];
// Updating the segment tree
update(0, 0, n - 1, rank - 1,
dp[i] + query(0, 0, n - 1, rank - 1, rank - 1));
}
// Returning the final answer
return ans;
}
// Driver code
var arr = [1, 2, 10, 9 ];
var n = arr.length;
document.write( findCnt(arr, n));
</script>Saída:
11
