3283 - Alice and Array in Flames

Created by Luis Manuel Díaz Barón
Added by luismo (2015-05-20)
Limits
Total Time: 15000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Alice is taking a new course named "Analysis and Design of Algorithms" as part of her Engineering degree. This week, she and her classmates are studying about Sorting Algorithms and their performance. They learn about how some algorithms are very efficient under certain circumstances and inefficient in other cases. For instance, some of the algorithms are quite fast when sorting arrays which are randomly ordered, but they are remarkably slow when the input array of elements is initially sorted or partially sorted, etc.

As part of the final project, Alice and their classmates are working on a new algorithm to sort integers. They are very excited by its preliminary results but not all is going well. After many tests, they determined that the algorithm is very inefficient when sorting sequences that are either increasing or non-decreasing. A sequence of numbers is said to be non-decreasing if every next element to the right isn't less than previous element. A sequence of numbers is said to be increasing if every next element to the right is strictly greater than previous element. A sequence containing a single element is said to be increasing and non-decreasing, at the same time.

In order to prove that their suspicion is correct, they are preparing a special array of N integer numbers. The elements in the array are conveniently numbered 1 to N from left to right. They need the (final) array to satisfy certain properties about the number of increasing and non-decreasing sequences on it. During their tests, they need to perform a sequence of operations over the array, where each operation is one of these two types:
  • Type 1: Given two integers i and x, set the value of the i-th element in the array to x.
  • Type 2: Given two integers i and j, determine whether the sequence in the interval [i, j] (i.e. the sequence starting with the element i and ending at the element j) is an increasing sequence, non-decreasing sequence, or none of these.
As you are a smart boy, Alice is certain that you can help her with this difficult task. Are you ready to help her?
Alicia está cursando una nueva materia llamada "Análisis y Diseño de Algoritmos" como parte de su grado de Ingeniera. Esta semana, ella y sus compañeros de clase están estudiando sobre los Algoritmos de Ordenamiento y su rendimiento. Ellos aprenden cómo algunos algoritmos son muy eficientes bajo determinadas circunstancias, o lo contrario en otros casos. Por ejemplo, algunos algoritmos funcionan muy rápido al ordenar arreglos que se encuentran ordenados aleatoriamente, pero pueden ser notablemente lentos si el arreglo de elementos está inicialmente ordenado o parcialmente ordenado, etc.

Como parte de la evaluación final, Alicia y sus compañeros de clase están trabajando en un nuevo algoritmo para ordenar números enteros. Ellos están muy emocionados por sus resultados preliminares, pero no todo está saliendo bien. Luego de muchas pruebas, ellos determinaron que el algoritmo es muy ineficiente cuando se ordena arreglos cuyos elementos son números que forman una secuencia creciente o no decreciente. Una secuencia de números se dice que es no decreciente si cada elemento siguiente a la derecha no es menor que el elemento anterior. Una secuencia de números se dice que es creciente si cada elemento siguiente a la derecha es estrictamente mayor que el elemento anterior. Una secuencia que contiene un solo elemento se dice que es creciente y no decreciente, al mismo tiempo.

Con el fin de investigar que sus sospechas son correctas, ellos están preparando un arreglo especial de N números enteros. Los elementos del arreglo están convenientemente numerados entre 1 y N de izquierda a derecha. Ellos necesitan que al final el arreglo termine cumpliendo ciertas propiedades sobre la cantidad de secuencias crecientes y no decrecientes presentes en él. Durante el proceso de pruebas, ellos necesitan realizar una serie de operaciones sobre el arreglo, y cada operación pertenece a uno de estos dos tipos:
  • Tipo 1: Dados dos números enteros i y x, se tiene que cambiar el valor de i-ésimo elemento del arreglo por x.
  • Tipo 2: Dados dos números enteros i y j, se necesita saber si la secuencia en el intervalo [i, j] (es decir, la secuencia que comienza con el elemento i y termina con el elemento j) es una secuencia creciente, una secuencia no decreciente, o ninguna de ellas.
Usted es un chico inteligente, así que Alicia está segura de que puedes ayudarles con este difícil trabajo. ¿Estás preparado para ayudarla?
Alice is taking a new course named "Analysis and Design of Algorithms" as part of her Engineering degree. This week, she and her classmates are studying about Sorting Algorithms and their performance. They learn about how some algorithms are very efficient under certain circumstances and inefficient in other cases. For instance, some of the algorithms are quite fast when sorting arrays which are randomly ordered, but they are remarkably slow when the input array of elements is initially sorted or partially sorted, etc.

As part of the final project, Alice and their classmates are working on a new algorithm to sort integers. They are very excited by its preliminary results but not all is going well. After many tests, they determined that the algorithm is very inefficient when sorting sequences that are either increasing or non-decreasing. A sequence of numbers is said to be non-decreasing if every next element to the right isn't less than previous element. A sequence of numbers is said to be increasing if every next element to the right is strictly greater than previous element. A sequence containing a single element is said to be increasing and non-decreasing, at the same time.

In order to prove that their suspicion is correct, they are preparing a special array of N integer numbers. The elements in the array are conveniently numbered 1 to N from left to right. They need the (final) array to satisfy certain properties about the number of increasing and non-decreasing sequences on it. During their tests, they need to perform a sequence of operations over the array, where each operation is one of these two types:
  • Type 1: Given two integers i and x, set the value of the i-th element in the array to x.
  • Type 2: Given two integers i and j, determine whether the sequence in the interval [i, j] (i.e. the sequence starting with the element i and ending at the element j) is an increasing sequence, non-decreasing sequence, or none of these.
As you are a smart boy, Alice is certain that you can help her with this difficult task. Are you ready to help her?

Input specification

The first line of input contains two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^4). The next line contains N space separated integers: these are the initial values of the array listed from left to right. The next Q lines contain three space separated integers with one of the following formats:
  • 1 i x - denoting the first type of operation, with (1 <= i <= N) and x (-10^6 <= x <= 10^6).
  • 2 i j - denoting the second type of operation, with (1 <= i <= j <= N).
La primera línea de entrada contiene dos números enteros N (1 <= N <= 10^5) y Q (1 <= Q <= 10^4) separados por espacios. La siguiente línea contiene N números enteros separados por espacios: los valores iniciales del arreglo listados de izquierda a derecha. Las siguientes Q líneas contienen tres enteros separados por espacios con uno de los siguientes formatos:
  • 1 i x - denota el primer tipo de operación, con (1 <= i <= N) y X (-10^6 <= x <= 10^6).
  • 2 i j - denota el segundo tipo de operación, con (1 <= i <= j <= N).
The first line of input contains two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^4). The next line contains N space separated integers: these are the initial values of the array listed from left to right. The next Q lines contain three space separated integers with one of the following formats:
  • 1 i x - denoting the first type of operation, with (1 <= i <= N) and x (-10^6 <= x <= 10^6).
  • 2 i j - denoting the second type of operation, with (1 <= i <= j <= N).

Output specification

For each operation of type two, output a line with an integer number between 0 and 2:
  • Output 2 if the elements in the interval [i, j] form an increasing sequence.
  • Else, output 1 if the elements in the interval [i, j] form non-decreasing sequence.
  • Else, output 0 if the sequence formed by the elements in the interval [i, j] is neither increasing nor non-decreasing.
Para cada operación de tipo dos usted debe imprimir una línea con un número entero entre 0 y 2:
  • Usted debe imprimir 2 si los elementos en el intervalo [i, j] son una secuencia creciente.
  • De lo contrario, usted debe imprimir 1 si los elementos en el intervalo [i, j] son una secuencia no decreciente.
  • De lo contrario, usted debe imprimir 0 si los elementos en el intervalo [i, j] no son del tipo de secuencias descritas anteriormente.
The first line of input contains two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^4). The next line contains N space separated integers: these are the initial values of the array listed from left to right. The next Q lines contain three space separated integers with one of the following formats:
  • 1 i x - denoting the first type of operation, with (1 <= i <= N) and x (-10^6 <= x <= 10^6).
  • 2 i j - denoting the second type of operation, with (1 <= i <= j <= N).

Sample input

6 7
2 4 -5 7 9 9
2 1 3
1 3 5
2 1 3
2 1 6
1 4 9
2 4 6
2 4 4

Sample output

0
2
1
1
2

Hint(s)