A certain mountain range has N N mountains, all a...
Creato il: 26 marzo 2025
Domanda
A certain mountain range has
N
N mountains, all along a line. The peak of the
i
i-th mountain is at a height of
H
i
H
i
.
It is known that adjacent mountain peaks differ in height by exactly
1
1, i.e.
∣
H
i
−
H
i
−
1
∣
1
∣H
i
−H
i−1
∣=1 for every
i
i.
On each mountain peak lives a single person.
A person can move from one mountain peak to an adjacent mountain peak (i.e. a person standing on the
i
i-th peak can move to
i
−
1
i−1 or
i
+
1
i+1).
However, they will refuse to move to a mountain that's of the same height as one that has been visited before.
For example, if the heights are
[
1
,
2
,
3
,
2
,
3
]
[1,2,3,2,3], the person who is initially on the first peak can move to the second and third peaks, but will not move to the fourth (since it has a height of
2
2, which has already been visited along the way).
Similarly, the person initially on the fourth peak can move to the third or the fifth peak, but will not move to the second peak, since it has a height of
2
2 which is the same as the starting height.
Two people are considered to have a friendship between them if they can both reach the same mountain via some sequence of moves.
In the above example of
[
1
,
2
,
3
,
2
,
3
]
[1,2,3,2,3], the people on mountains
2
2 and
3
3 are friends (person
2
2 can move to mountain
3
3), and the people on mountains
1
1 and
4
4 are also friends (they can both move to mountain
3
3). However, the people on mountains
1
1 and
5
5 are not friends, because there's no common mountain where they can meet.
Given the heights of the mountain peaks, find the number of friendships.
Input Format
The first line of input will contain a single integer
T
T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains one integer
N
N — the number of mountain peaks.
The next line contains
N
N space-separated integers
H
1
,
H
2
,
…
,
H
N
H
1
,H
2
,…,H
N
, describing the mountain heights.
Output Format
For each test case, output on a new line a single integer: the number of friendships.
Constraints
1
≤
T
≤
1
0
5
1≤T≤10
5
1
≤
N
≤
2
⋅
1
0
5
1≤N≤2⋅10
5
1
≤
H
i
≤
N
1≤H
i
≤N
∣
H
i
−
H
i
−
1
∣
1
∣H
i
−H
i−1
∣=1 for each
1
≤
i
<
N
1≤i<N
The sum of
N
N over all test cases won't exceed
2
⋅
1
0
5
2⋅10
5
.
Sample 1:
Input
Output
2
5
3 4 5 4 3
4
1 2 1 2
10
5
Explanation:
Test case
1
1: Every person is able to reach the highest mountain, i.e.
5
5. Since for every pair of people there's a mountain they can both reach, every pair of people will be friends.
Test case
2
2: The friendships are as follows:
Persons
1
1 and
2
2 are friends: they're already adjacent to each other so one of them can just move to the other.
Similarly
(
2
,
3
)
(2,3) and
(
3
,
4
)
(3,4) are friends.
Persons
1
1 and
3
3 are friends: they can both move to mountain
2
2 and meet there.
Similarly, persons
2
2 and
4
4 are friends, since they can meet at mountain
3
3.
However, there's no way for persons
1
1 and
4
4 to ever meet.
The total number of friendships is hence
5
5.
code in java withiut comments
Risposta
javaimport java.io.*; import java.util.*; class Main { static class Event { int x, t; Event(int x, int t) { this.x = x; this.t = t; } } static int[] H, L, R, freq; static Event[] events; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static String next() throws IOException { while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine()); return st.nextToken(); } static int nextInt() throws IOException { return Integer.parseInt(next()); } public static void main(String[] args) throws IOException { int T = nextInt(); StringBuilder sb = new StringBuilder(); while(T-- > 0) { int N = nextInt(); H = new int[N+1]; for(int i=1;i<=N;i++) H[i] = nextInt(); L = new int[N+1]; R = new int[N+1]; freq = new int[N+1]; int start=1; for(int i=1;i<=N;i++){ while(freq[H[i]]>0){ freq[H[start]]--; start++; } freq[H[i]]++; L[i]=start; } Arrays.fill(freq,0); int end=N; for(int i=N;i>=1;i--){ while(freq[H[i]]>0){ freq[H[end]]--; end--; } freq[H[i]]++; R[i]=end; } events = new Event[2*N]; int idx=0; for(int i=1;i<=N;i++){ events[idx++] = new Event(L[i], 0); events[idx++] = new Event(R[i], 1); } Arrays.sort(events, 0, 2*N, (a,b)->{ if(a.x!=b.x) return a.x-b.x; return a.t-b.t; }); long ans=0; long open=0; for(int i=0;i<2*N;i++){ if(events[i].t==0){ ans+=open; open++; } else { open--; } } sb.append(ans).append("\n"); } System.out.print(sb); } }