Game on Permutation

题面翻译

两人在一个长为 $n$ 排列 $p$ 上玩游戏，先手初始可以任意选择一个位置（注意先手不能选择一个不能移动的位置），然后他们以先手选择的位置为起点后手先依次交替移动，每次只能向左移动到比当前数字小的位置（即如果 $i<j$ 且 $p_i<p_j$ ，则可从 $j$ 移动到 $i$ ），如果一个人不能移动，则此人获胜，请问先手开始选择有必胜策略的位置的个数。

题目描述

Alice and Bob are playing a game. They have a permutation $ p $ of size $ n $ (a permutation of size $ n $ is an array of size $ n $ where each element from $ 1 $ to $ n $ occurs exactly once). They also have a chip, which can be placed on any element of the permutation.

Alice and Bob make alternating moves: Alice makes the first move, then Bob makes the second move, then Alice makes the third move, and so on. During the first move, Alice chooses any element of the permutation and places the chip on that element. During each of the next moves, the current player has to move the chip to any element that is simultaneously to the left and strictly less than the current element (i. e. if the chip is on the $ i $ -th element, it can be moved to the $ j $ -th element if $ j < i $ and $ p_j < p_i $ ). If a player cannot make a move (it is impossible to move the chip according to the rules of the game), that player wins the game.

Let’s say that the $ i $ -th element of the permutation is lucky if the following condition holds:

• if Alice places the chip on the $ i $ -th element during her first move, she can win the game no matter how Bob plays (i. e. she has a winning strategy).

You have to calculate the number of lucky elements in the permutation.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) – the number of elements in the permutation.

The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ ). All $ p_i $ are distinct.

The sum of $ n $ over all test cases doesn’t exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the number of lucky elements in the permutation.

样例 #1

样例输入 #1

4
3
2 1 3
2
2 1
3
1 2 3
4
2 1 4 3

样例输出 #1

1
0
1
2

提示

In the first test case of the example, the $ 3 $ -rd element of the permutation is lucky.

In the second test case of the example, there are no lucky elements.

In the third test case of the example, the $ 2 $ -nd element of the permutation is lucky.

In the fourth test case of the example, the $ 3 $ -rd and the $ 4 $ -th element of the permutation are lucky.

关于必胜态和必败态，爱丽丝想要赢，就只能让鲍勃操作一次然后自己不能操作，如果不是的话，就会被鲍勃操纵，让爱丽丝只能操作一次，相当于把主控权让给了别人

关于树状数组，就会发现一个数要是幸运的，排在他前面的数还比他小的就必须从大到小排，就比如3214，4是幸运，如何找呢，从1到n，到i就查询一次比它小的并且还是递增的有几个，如果是一个，就满足3->4,树状数组里的max就是找以当前数字结尾的最长上升子序列有多长

const int N = 1e5 + 10;
int t, n, a[300005], b[300005];
void add(int x, int p) { for (; x <= n; x += x & -x) a[x] = max(a[x], p); }
int query(int x) { int ans = 0; for (; x; x -= x & -x) ans = max(ans, a[x]); return ans; }

void solve()
{
    cin >> n; int ans = 0;
    for (int i = 1; i <= n; i++) cin >> b[i], a[i] = 0;
    for (int i = 1; i <= n; i++) {
        int k = query(b[i]);
        if (k == 1) ans++;
        add(b[i], k + 1);
    }cout << ans << "\n";
}

更棒的写法（耿直）

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l, r, ans;
    l = r = 1e18;
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (l < a[i] && a[i] < r)
        {
            ans++;
            r = min(r, a[i]);
        }
        l = min(l, a[i]);
    }
    cout << ans << '\n';