CF 1860 C【最大上升子序列】

C. Game on Permutation

这道题需要求出先手必胜点

通过分析可知，每个位置结尾的最大上升子序列长度为2的点为先手必胜点，≥3的点为先手必败点。即只需要求出以每个位置为结尾的最大上升子序列长度为2的点的数量即可求出答案。

本题目的n (1≤n≤3⋅10⁵)，所以无法使用O(n²)的方法，因此可使用树状数组进行优化为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;
}