subject

N people of different heights stand in a row at certain intervals. Everyone monitors whether the people they can see are doing other things according to the following rules.

• Rule: no one can be taller than me between me and the i-th person I want to monitor,
  No one can be taller than the i-th person. For example, according to the following [figure], number ⑤ can be monitored to number ③,
  However, ① cannot be monitored because ③ is higher than ⑤.
  

Suppose there are eight people standing as shown in the figure above. These people are numbered ① - ⑧ from left to right, and their height is the number on their heads.
For ①, there is no one to monitor on his left. On the right, ① can monitor ③ higher than ②, but ④ and ⑤ lower than ③ cannot be monitored. In addition, because there is no higher person in the middle, it can be monitored until ⑥, but it is impossible to monitor ⑦ and ⑧ lower than ⑥. In other words, ① can monitor ②, ③ and ⑥. For ②, it can monitor both ① on the left and ③ on the right. However, the height of number ③ on the right is higher than that of number ②, and number ② cannot monitor the rest of the people on the right. ③ It can monitor ① and ② on the left and ④, ⑤ and ⑥ on the right; However, ⑦ and ⑧ cannot be monitored because ⑥ standing in the middle is higher than ⑦ and ⑧. ⑥ It can monitor ①, ③ and ⑤ on the left and ⑦ and ⑧ on the right.
According to the given height data, calculate the total number of people that each person can monitor on the left and right sides.
※ according to the above figure, ① No. 2 can monitor three people (②, ③ and ⑥), No. 2 can monitor two people (① and ③), No. 3 can monitor five people (①, ②, ④, ⑤ and ⑥), No. ④ can monitor two people (③ and ⑤), and No. ⑤ can monitor three people (③, ④ and ⑥), ⑥ can monitor five people (①, ③, ⑤, ⑦ and ⑧), ⑦ can monitor two people (⑥ and ⑧), and ⑧ can monitor two people (⑥ and ⑦).

[restrictions]
1. The number of people standing N is an integer between 1 and 300000.
2. The height M of the person standing is an integer between 1 and 1000000000.
3. Everyone's height is different.

[input]
First, give the number of test cases T, and then enter t test cases. The number of people N is given in the first line of the test case. In the second line, give the height of N people, separated by spaces.

[output]
Output one test case per line. Each test case outputs "#x" (x is the number of test cases, starting from 1) and the total number of people that can be monitored on both sides of each person.

[input and output examples]
(input)
2
8
10 3 8 4 7 9 5 6
7
1 2 3 10 9 8 7

(output)
#1 24
#2 12

Problem solving ideas

Split it into two parts, calculate the number of people monitored by each person from left to right, and then calculate the number of people that can be monitored by each person from right to left
Take left to right as an example
1. The first cycle uses the two-way queue to find the position of the first person higher than him on the right of each person
2. The second cycle uses dynamic programming to calculate the maximum number of ascending subsequences for each person
3. The third cycle calculates the number of people i can monitor
If i+1 person is higher than the i-th person, the number of people that can be monitored is 1
If the i+1 person is shorter than the i-th person, it is the number of the longest ascending subsequence of the i+1 person - the number of the longest ascending subsequence of the first person on the right who is higher than the i-th person + 1 (if there is a person higher than the i-th person, there is no + 0), and then calculate it from right to left according to the above logic

Code (IndexTree)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Pro20211203IndexTree {
	static int asw, tree[];

	public static void update(int i, int val) {
		while (i > 0) {
			tree[i] += val;
			i /= 2;
		}
	}

	public static int query(int s, int e) {
		int result = 0;
		while (s <= e) {
			if (s % 2 > 0)
				result += tree[s];
			if (e % 2 == 0)
				result += tree[e];

			s = (s + 1) / 2;
			e = (e - 1) / 2;
		}

		return result;
	}

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("D:\\SW\\TestCase\\sample_input_20211203.txt"));

		long s = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());

			int idx = 1;
			while (idx < N)
				idx = idx << 1;

			int[][] data = new int[N][2];
			tree = new int[idx * 2];

			asw = 0;

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				data[i][0] = Integer.parseInt(st.nextToken());
				data[i][1] = i;
			}

			Arrays.sort(data, 0, N, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[0] - o1[0];
				}
			});

			for (int i = 0; i < N; i++) {
				int count = query(idx, idx + data[i][1] - 1) > 0 ? 1 : 0;
				count += query(idx + data[i][1] + 1, 2 * idx - 1) > 0 ? 1 : 0;

				asw += 2 * count;

				update(idx + data[i][1], 1);
			}

			System.out.println("#" + t + " " + asw);
		}

		long e = System.currentTimeMillis();

		System.out.println(e - s);
	}
}

Code (DP)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Pro20210924Topology {
	static int T, N, M, ASW, IN[];
	static Set<Integer>[] DATA;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("D:\\SW\\TestCase\\sample_input_20210924.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			ASW = N;

			IN = new int[N + 1];
			DATA = new HashSet[N + 1];
			for (int n = 1; n <= N; n++)
				DATA[n] = new HashSet<Integer>();

			for (int a, b, m = 0; m < M; m++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());

				if (DATA[a].add(b) && ++IN[b] == 1) ASW--;
			}

			if (ASW == 1) ASW = 0;

			for (int n = 1; n <= N; n++) {
				if (IN[n] > 0) continue;

				for (int next : DATA[n])
					if (IN[next] == 1) ASW++;
			}

			System.out.println(t + " " + ASW);
		}
	}
}