C. Fighting Tournament（模拟/map）

题目

题意

给定n个选手，每个选手有一个权值，且每个选手的权值取值各不相同，且范围为1到n。 即这n个选手的权值a[i]是一个关于n的排列。

两个选手进行比赛，权值大的那位选手获胜。

对于每轮比赛，做以下操作：

选择当前最前面两位选手，进行比赛。获胜的选手，排在第1位；失败的选手，排在最后1位。

例如5位选手，他们的权值为 3 1 4 5 2

第1轮，第1位选手和第2位选手比赛，第1位选手获胜，此时数组为 3 4 5 2 1

第2轮，第2位选手和第3位选手比赛，第3位选手获胜，此时数组为 4 5 2 1 3

第3轮，第3位选手和第4位选手比赛，第4位选手获胜，此时数组为 5 2 1 3 4

第4轮，第4位选手和第5位选手比赛，第4位选手获胜，此时数组为 5 1 3 4 2

第5轮，第4位选手和第2位选手比赛，第4位选手获胜，此时数组为 5 3 4 2 1 …

有q次询问，对于第i个选手，经过前k轮后，他总共获胜了多少次。

1 a[i] int Right[maxn];// leftest pos > i, which a[pos] > a[i] void init() { run = 0; while (true) { if (ve[0] == n) { break; } if (ve[0] > ve[1]) { swap(ve[0], ve[1]); } ++run; ++num[mp[ve[1]]]; int tmp = ve[0]; ve.pop_front(); ve.push_back(tmp); } int pos = 0; for (int i = 1; i a[i]) { Left[i] = pos; } else { Right[pos] = i; pos = i; } } } int cal() { int res; if (k >= run) {// case 1 res = num[pos]; if (a[pos] == n) { res += k - run; } return res; } // case 2.1 if (Left[pos] != -1) { return 0; } // case 2.2 k -= pos; if (k