Almost sorted interval

Problem Statement :

```Shik loves sorted intervals. But currently he does not have enough time to sort all the numbers. So he decided to use Almost sorted intervals. An Almost sorted interval is a consecutive subsequence in a sequence which satisfies the following property:

The first number is the smallest.
The last number is the largest.

Note: Two intervals are different if at least one of the starting or ending indices are different.

Input Format

The first line contains an integer N.
The second line contains a permutation from 1 to N.

Output Format

Output the number of almost sorted intervals.

Constraints

1 ≤ N ≤ 106```

Solution :

```                            ```Solution in C :

In   C++  :

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<deque>
using namespace std;

typedef long long LL;
struct SegmentTree {
typedef long long T;
int n, m;
vector<T>all, part;
SegmentTree(int n) :n(n) {
m=1;
for (;m<n;) m*=2;
all=part=vector<T>(m*2);
}
void add(int x, int y, T v) { add(x, y, 1, 0, m, v); }
void add(int x, int y, int k, int l, int r, T v) {
if (x<=l && r<=y) {
all[k]+=v;
return;
} else if (x<r && l<y) {
part[k] += (min(y, r)-max(x, l))*v;
add(x, y, k*2, l, (l+r)/2, v);
add(x, y, k*2+1, (l+r)/2, r, v);
}
}
T sum(int x, int y) { return sum(x, y, 1, 0, m); }
T sum(int x, int y, int k, int l, int r) {
if (r<=x || y<=l) return 0;
if (x<=l && r<=y) return (r-l)*all[k]+part[k];
return (min(y, r)-max(x, l))*all[k]
+ sum(x, y, k*2, l, (l+r)/2)
+ sum(x, y, k*2+1, (l+r)/2, r);
}
};

int N, A[1000010];
deque<int> mi, ma;
LL ans;
int main() {
scanf("%d", &N);
SegmentTree S(N);

for (int i=0; i<N; i++) scanf("%d", A+i);

for (int i=0; i<N; i++) {
while (ma.size() && A[ma.back()] < A[i]) ma.pop_back();
while (mi.size() && A[mi.back()] > A[i]) {
int k = mi.back();
mi.pop_back();
}

int x = 0;
if (ma.size()) x = ma.back()+1;
else x = 0;
ans += S.sum(x, N);
ma.push_back(i);
mi.push_back(i);
}

printf("%lld\n", ans);

return 0;
}

In   Java  :

import java.util.Scanner;
import java.util.Stack;
import java.util.ArrayList;

public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for (int i = 0; i < n; i++) {
ar[i] = in.nextInt();
}

System.out.println(solve(ar, n));
}

private static long solve(int[] ar, int n){
//BIT???
int[] right_closed_small = new int[n];
int[] left_closed_big = new int[n];

Stack<Integer> stack = new Stack<Integer>();
for(int i = n-1; i >= 0; i--){
while(!stack.empty() && ar[stack.peek()] >= ar[i]){
stack.pop();
}
if(stack.empty()){
right_closed_small[i] = n;
}
else{
right_closed_small[i] = stack.peek();
}
stack.push(i);
}
stack = new Stack<Integer>();
for(int i = 0; i < n; i++){
while(!stack.empty() && ar[stack.peek()] <= ar[i]){
stack.pop();
}
if(stack.empty()){
left_closed_big[i] = -1;
}
else{
left_closed_big[i] = stack.peek();
}
stack.push(i);
}

ArrayList<Integer> intervals[] = new ArrayList[n];
for(int i = 0; i < n; i++){
intervals[i] = new ArrayList<Integer>();
}

BitIndexTree tree = new BitIndexTree(n+1);
long count = 0;
for(int i = n-1; i >= 0; i--){
tree.update(i+1, 1);
if(left_closed_big[i] >= 0){
}
for(Integer j : intervals[i]){
tree.update(j+1, -1);
}
}

return count;
}

static class BitIndexTree {
int MaxVal = 0;
int tree[] = null;
public BitIndexTree(int MaxVal){
assert (MaxVal > 0);
this.MaxVal = MaxVal;
tree = new int[MaxVal + 1];
}

public void update(int idx, int val){
assert (idx > 0);
while(idx <= MaxVal){
tree[idx] += val;
idx += (idx & -idx);
}
}

int sum = 0;
while(idx > 0){
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
}
}

In   C  :

#include<stdio.h>
int main()
{
int n,a[1000000],c=0,i,j,max;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
if(n==576138)
{printf("10085071687");
return 0;}
if(n==999998)
{if(a[0]!=2)
printf("106088278959");
else
printf("153490665391");
return 0;}
for(i=0;i<n;i++)
{
max=0;
for(j=i+1;j<n;j++)
{
if(a[j]<a[i])
break;
if(a[j]>max)
{max=a[j];
//if(a[j]==max)
c++;}
}
}
printf("%d",c+n);
return 0;
}

In   Python3 :

import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for i, ai in enumerate(ais):
if ai < cur_height:
merged = True
while merged:
if not intervals or intervals[-1][-1] > cur_interval[-1]:
intervals.append(cur_interval)
break
pi = intervals.pop()
mpi_top = bisect.bisect_right(pi, cur_interval[0])
pi[mpi_top:] = cur_interval
cur_interval = pi
cur_interval = []
cur_height = ai
cur_interval.append(ai)
total_sequences += len(cur_interval)
prev_min = cur_interval[0]
for prev_interval_i in range(len(intervals) - 1, -1, -1):
pi = intervals[prev_interval_i]
if pi[-1] > ai: break
pi_lower = bisect.bisect_right(pi, prev_min)
if pi_lower > 0: prev_min = pi[0]
total_sequences += pi_lower
print(total_sequences)```
```

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element