题解：P14175 【MX-X23-T5】向死存魏

__liujy · 2026-07-25 17:45:32 · 题解

P14175 【MX-X23-T5】向死存魏

好题！但是代码太难写了。

令 f_x 为询问为 3 x 的答案。考虑怎么求出 f_x。

首先这个在询问前显然可以预处理出来。具体的，令 g_{x, i} 为对于 j>x 满足 a_j=i 的最小的 j。这样就引出了我们的第一个问题：万一后面没有 i 怎么办？可以在 a 后面添加 1 \sim V。相似的，对于操作 2，可以离线下来，将每个数字按顺序放在 a 的后面，这样对于一次询问 3 x，如果 f_x 超过了 n 加上前面有的操作 2 的数量就无解，否则答案为 f_x。显然的，f_x = \max^{V}_{i=1} g_{x, i}。这一部分可以枚举 x 然后做。时间复杂度 O(n\log n)。

接下来只需要考虑操作 1 就行了。思考：为什么将一些数变为 0 而不是别的数？因为这样相当于将这些数删除了，对答案会产生影响。具体的，令 tl 为 l 前面第一个等于 x 的位置，tr 为在 r 后面第一个等于 x 的位置，显然的，假设 i\in[tl+1,tr-1],f_x=\max(f_x, tr)。那时间复杂度为多少？因为每一次操作等价于一次删除操作，而这些数一共只有 (n+m) 个，所以总的询问复杂度为 O(m\log(n+m))。

我的代码写了 233 行，太勾石了，就只把主要代码放出来。 ::::info[code]

    for(int i = n, cnt = 0; i >= 1; i--)
    {
        if(!LCR[a[i]])
            cnt++;

        LCR[a[i]] = i, S1.modify(1, 1, V, a[i], a[i], i);

        if(cnt != V)
            S2.modify(1, 1, n, i, i, INT_MAX);
        else
        {
            int mx = S1.mx[1];

//          std::cout << mx << ' ';

            S2.modify(1, 1, n, i, i, mx);
        }
    }
//  /*
    for(int i = 1; i <= m; i++)
    {
        int op = qy[i].op, l = qy[i].l, r = qy[i].r, x = qy[i].x;

        if(op == 2)
        {
            N++;
            continue;
        }

        if(op == 1)
        {
//          /*
            auto L = s[x].lower_bound(l), R = s[x].upper_bound(r);

            S2.modify(1, 1, n, *prev(L) + 1, (*R) - 1, *R);
//          /*
            std::vector<int> vec;

            for(auto it = L; it != R; it++)
                vec.pb(*it);
            for(auto it : vec)
                s[x].erase(it);
//          */
        }
        else
        {
//          /*
            int ans = S2.query(1, 1, n, l, l);

//          std::cout << ans << ' ' << N << ' ';

            if(ans > N) ans = -1;

            printf("%d\n", ans);
//          */
        }
    }

::::