問題一覧 > 通常問題

No.3059 Range Tournament

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 19
作問者 : 👑 tute7627 / テスター : 👑 rin204 SPD_9X2
お気に入りにしたユーザー ProblemId : 11172 / 自分の提出
問題文最終更新日: 2025-03-13 23:37:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 460 (順位表) の他の問題:

Problem Statement

There are $N$ players $1,2,\dots,N$.

Using a permutation $P$ of $(1,2,\dots,N)$, $Q$ tournaments will now be held. The $i$-th tournament proceeds as follows.

  1. Form a queue in which players $P_{L_i}, P_{L_{i+1}}, \dots, P_{R_i}$ are lined up in this order from the front.
  2. Repeat the following process until only one player remains in the queue.
    • The first two players from the front play a match. The player with the larger player number wins and moves to the end of the queue. The player with the smaller number leaves the queue.

For each $i=1,2,\dots,N$, find the total number of matches that player $i$ wins over the $Q$ tournaments.

Input

$N$
$P_1\ P_2\ \dots \ P_N$
$Q$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_Q\ R_Q$

  • All inputs are integers.
  • $2 \le N \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $P$ is a permutation of $(1,2,\dots,N)$.
  • $1 \le L_i < R_i \le N$

Output

On the $i$-th line, output the total number of matches that player $i$ wins. Print a newline at the end.

Sample

Sample 1
Input
5
3 1 4 2 5
1
1 5
Output
0
0
1
1
2

The tournament starts with the player numbers lined up as $(3,1,4,2,5)$ from the front.

  • In match $1$, player $3$ and player $1$ play, and player $3$ wins. The queue becomes $(4,2,5,3)$.
  • In match $2$, player $4$ and player $2$ play, and player $4$ wins. The queue becomes $(5,3,4)$.
  • In match $3$, player $5$ and player $3$ play, and player $5$ wins. The queue becomes $(4,5)$.
  • In match $4$, player $4$ and player $5$ play, and player $5$ wins. The queue becomes $(5)$.

Sample 2
Input
14
5 9 12 7 4 1 14 6 13 3 11 2 8 10
10
12 13
1 14
3 8
2 13
4 11
3 11
4 6
5 8
4 14
2 14
Output
0
0
0
4
0
0
6
4
1
2
7
12
10
26

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。