1905F - Field Should Not Be Empty - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
struct aint
{
    vector<pair<int, int>> a;
    vector<int> lazy;
    void resize(int n)
    {
        a = vector<pair<int, int>>(4 * n);
        lazy = vector<int>(4 * n);
    }
    void init(int node, int left, int right)
    {
        a[node].second = (right - left + 1);
        if (left != right)
        {
            int mid = (left + right) / 2;
            init(2 * node, left, mid);
            init(2 * node + 1, mid + 1, right);
        }
    }
    void prop(int node, int left, int right)
    {
        a[node].first += lazy[node];
        if (left != right)
        {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    pair<int, int> merge(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first)
        {
            return pair<int, int>{a.first, a.second + b.second};
        }
        return min(a, b);
    }
    void update(int node, int left, int right, int st, int dr, int val)
    {
        prop(node, left, right);
        if (right < st || left > dr)
        {
            return;
        }
        if (st <= left && dr >= right)
        {
            lazy[node] += val;
            prop(node, left, right);
            return;
        }
        int mid = (left + right) / 2;
        update(2 * node, left, mid, st, dr, val);
        update(2 * node + 1, mid + 1, right, st, dr, val);
        a[node] = merge(a[2 * node], a[2 * node + 1]);
    }
};
struct bit
{
    vector<int> a;
    void resize(int n)
    {
        a = vector<int>(n + 1);
    }
    void update(int pos, int val)
    {
        int n = (int)a.size() - 1;
        for (int i = pos; i <= n; i += i & (-i))
        {
            a[i] += val;
        }
    }
    int query(int pos)
    {
        int ans = 0;
        for (int i = pos; i; i -= i & (-i))
        {
            ans += a[i];
        }
        return ans;
    }
    int query(int st, int dr)
    {
        return query(dr) - query(st - 1);
    }
};
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        bool sortat = true;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] != i)
            {
                sortat = false;
            }
        }
        if (sortat)
        {
            cout << n - 2 << '\n';
            continue;
        }
        vector<pair<int, int>> qui(n + 1);
        stack<int> s;
        bit tree;
        tree.resize(n);
        for (int i = 1; i <= n; ++i)
        {
            while (!s.empty() && a[s.top()] < a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].first = s.top();
            }
            if (tree.query(a[i], n) > 1)
            {
                qui[i].first = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        while (!s.empty())
            s.pop();
        tree.resize(n);
        for (int i = n; i >= 1; --i)
        {
            while (!s.empty() && a[s.top()] > a[i])
            {
                s.pop();
            }
            if (!s.empty())
            {
                qui[i].second = s.top();
            }
            if (tree.query(1, a[i]) > 1)
            {
                qui[i].second = 0;
            }
            tree.update(a[i], 1);
            s.push(i);
        }
        aint lesgo;
        lesgo.resize(n);
        lesgo.init(1, 1, n);
        function<void(int, int)> upd = [&](int ind, int sign)
        {
            lesgo.update(1, 1, n, min(ind, a[ind]), max(ind, a[ind]), sign);
        };
        function<int()> count = [&]()
        {
            if (lesgo.a[1].first == 1)
            {
                return lesgo.a[1].second;
            }
            return 0;
        };
        function<void(int, int)> mySwap = [&](int i, int j)
        {
            upd(i, -1);
            upd(j, -1);
            swap(a[i], a[j]);
            upd(i, 1);
            upd(j, 1);
        };
        for (int i = 1; i <= n; ++i)
        {
            upd(i, 1);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (qui[i].first && qui[i].second)
            {
                mySwap(qui[i].first, qui[i].second);
                ans = max(ans, count());
                mySwap(qui[i].first, qui[i].second);
            }
        }
        vector<int> pos(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; ++i)
        {
            int qui1 = i;
            int qui2 = pos[i];
            mySwap(qui1, qui2);
            ans = max(ans, count());
            mySwap(qui1, qui2);
        }
        cout << ans << '\n';
    }
}