题解：CF1685E The Ultimate LIS Problem

KK_lang · 2026-03-07 19:04:01 · 题解

拍了一年发现数组开小了，怎么回事呢？？

但是这真是神仙题吧

【sol】

根据 dilworth 定理，LIS 不超过 n 即为可以用 n 个下降子序列覆盖整个排列。考虑序列长度为 2n+1，故推测 n 个子序列为 n-1 个长度为 2 的和一个长度为 3 的。

然后就不会了，然后就严肃研读题解了。猜测一定是 >n+1 的和 <n+1 的一一配对，然后将 n+1 插入到某个组中。

发现这样做一定是好的。考察如果有 >n+1 的两两配对以及 <n+1 的两两配对，讨论一下，一定可以调整为 >n+1 的和 <n+1 的之间配对。

形如括号匹配。将 >n+1 的视为左括号，<n+1 的视为右括号，即要找出一个循环位移使括号匹配合法，并且 n+1 在某一对括号之间。

括号匹配的结论为，( 视为 1，) 视为 -1，所有前缀和都非负且序列之和为 0，即为合法括号序列。一定存在一个循环位移使括号序列合法，因为可以把前缀和的最小值 rotate 到序列末尾，而且我们已知 ( 与 ) 数量一样。

对于 n+1，如果它已经在一组括号之间，即 rotate 后 n+1 处的前缀和 >0，那么我们已经找到答案了。

对于 n+1 不在一组括号内的情况，其前缀和为 0，所以左右两边都独立构成合法括号序列，所以可以选择将 n+1 rotate 到开头或末尾，此时括号序列依旧是合法的。

然后手玩或打表发现，当且仅当 1\rightarrow n 和 n+2\rightarrow 2n+1 都是上升序时，才无解，否则可以调整使得 n+1 加入某个组中。

最小前缀和以及是否上升序都可以用线段树维护。后者具体为，在线段树上对每个 i 维护 [pos_i>pos_{i+1}]，然后对于循环位移，判断一下 1 或 2n+1 与 n+1 的位置关系，可以判断 1\rightarrow n 和 n+2\rightarrow 2n+1 是否因为循环位移产生一个断点，然后就对了。

【code】

#include<bits/stdc++.h>
using namespace std;
#define int long long

int lc(int x) { return x << 1; }
int rc(int x) { return x << 1 | 1; }

const int nr = 1e5 + 10;
int n, q, M, p[nr << 1], pre[nr << 1], pos[nr << 1];
int calc(int x) { return x == n + 1 ? 0 : x > n + 1 ? 1 : -1; }

struct segment1
{
    pair<int, int> seg[nr << 3];
    int tag[nr << 3];

    void pushup(int x)
    {
        seg[x] = min(seg[lc(x)], seg[rc(x)]);
    }

    void build(int x, int l, int r)
    {
        tag[x] = 0;
        if (l == r)
        {
            seg[x] = make_pair(pre[l], l);
            return;
        }
        int mid = l + r >> 1;
        build(lc(x), l, mid);
        build(rc(x), mid + 1, r);
        pushup(x);
    }

    void movetag(int x, int k)
    {
        seg[x].first += k;
        tag[x] += k;
    }

    void pushdown(int x)
    {
        if (tag[x])
        {
            movetag(lc(x), tag[x]);
            movetag(rc(x), tag[x]);
        }
        tag[x] = 0;
    }

    void upd(int x, int l, int r, int ql, int qr, int k)
    {
        if (ql <= l && r <= qr)
        {
            movetag(x, k);
            return;
        }
        pushdown(x);
        int mid = l + r >> 1;
        if (ql <= mid) upd(lc(x), l, mid, ql, qr, k);
        if (mid + 1 <= qr) upd(rc(x), mid + 1, r, ql, qr, k);
        pushup(x);
    }

    int query(int x, int l, int r, int q)
    {
        if (l == r) return seg[x].first;
        pushdown(x);
        int mid = l + r >> 1;
        if (q <= mid) return query(lc(x), l, mid, q);
        return query(rc(x), mid + 1, r, q);
    }
} tr1;

struct segment2
{
    int seg[nr << 3];

    void pushup(int x)
    {
        seg[x] = seg[lc(x)] + seg[rc(x)];
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            seg[x] = pos[l] > pos[l + 1];
            return;
        }
        int mid = l + r >> 1;
        build(lc(x), l, mid);
        build(rc(x), mid + 1, r);
        pushup(x);
    }

    void upd(int x, int l, int r, int q)
    {
        if (q < 1 || q > (n << 1)) return;
        if (l == r)
        {
            seg[x] = pos[l] > pos[l + 1];
            return;
        }
        int mid = l + r >> 1;
        if (q <= mid) upd(lc(x), l, mid, q);
        else upd(rc(x), mid + 1, r, q);
        pushup(x);
    }

    int query(int x, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr) return seg[x];
        int mid = l + r >> 1, res = 0;
        if (ql <= mid) res += query(lc(x), l, mid, ql, qr);
        if (mid + 1 <= qr) res += query(rc(x), mid + 1, r, ql, qr);
        return res;
    }
} tr2;

signed main()
{
//  freopen("hack.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= (n << 1 | 1); i++)
        cin >> p[i], pos[p[i]] = i, pre[i] = pre[i - 1] + calc(p[i]); M = pos[n + 1];
    tr1.build(1, 1, n << 1 | 1);
    tr2.build(1, 1, n << 1);
    while (q--)
    {
        int x, y; cin >> x >> y; 
        tr1.upd(1, 1, n << 1 | 1, x, n << 1 | 1, calc(p[y]) - calc(p[x]));
        tr1.upd(1, 1, n << 1 | 1, y, n << 1 | 1, calc(p[x]) - calc(p[y]));
        swap(pos[p[x]], pos[p[y]]), swap(p[x], p[y]), M = pos[n + 1];
        tr2.upd(1, 1, n << 1, p[x] - 1), tr2.upd(1, 1, n << 1, p[x]);
        tr2.upd(1, 1, n << 1, p[y] - 1), tr2.upd(1, 1, n << 1, p[y]);
        pair<int, int> mn = tr1.seg[1];
        int pre = tr1.query(1, 1, n << 1 | 1, M), nowpre = max(pre - mn.first, pre);
        if (nowpre > 0) { cout << (mn.first < 0 ? mn.second % (n << 1 | 1) : 0) << '\n'; continue; }
        if (tr2.query(1, 1, n << 1, 1, n) - (pos[1] > M) > 0) { cout << M % (n << 1 | 1) << '\n'; continue; }
        if (tr2.query(1, 1, n << 1, n + 1, n << 1) - (pos[n << 1 | 1] < M) > 0) { cout << M - 1 << '\n'; continue; }
        cout << -1 << '\n';
    }
    return 0;
}