C. Game on Permutation
这道题需要求出先手必胜点
通过分析可知，每个位置结尾的最大上升子序列长度为2的点为先手必胜点，≥3的点为先手必败点。即只需要求出以每个位置为结尾的最大上升子序列长度为2的点的数量即可求出答案。
本题目的n (1≤n≤3⋅105)，所以无法使用O(n2)的方法，因此可使用树状数组进行优化为O(nlogn)的时间复杂度。
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const ll N = 3e5 + 10;
ll t, n;
ll p[N];
ll c[N];
ll f[N];
set<PII> st;
void add(ll x, ll p)
{
for(;x <= n;x += x & -x)
{
c[x] = max(p, c[x]);
}
}
ll query(ll x)
{
ll tot = 0;
for(;x > 0;x -= x & -x)
{
tot = max(tot, c[x]);
}
return tot;
}
signed main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while(t--)
{
stack<ll> stk;
cin >> n;
ll tot = 0;
ll now = 0;
for(ll i = 1;i <= n;i++)
{
c[i] = 0;
}
for(ll i = 1;i <= n;i++)
{
cin >> p[i];
int ans = query(p[i]);
if(ans == 1)
{
tot++;
}
add(p[i], ans + 1);
}
cout << tot << endl;
}
return 0;
}