【题解】Game with Cards CF1539E dp ——HomuraCat

传送门

比赛的时候因为这题罚坐了 80 分钟，已经是废猫了。

题目描述

两个人抽卡，第 $n$张卡的数值为 $a_i$。

刚开始，每人都有一张数值为 0 的卡。

每次两个人必须有一人抽卡，并把自己手上的卡给丢掉。

在第 $i$次抽卡后，两个人的卡面数值需要满足在两个特定的区间内。

问是否有合法的抽卡方案，如果有，输出一种方案（0 表示 A 抽，1 表示 B 抽）。

思路

注意到，如果一次抽卡是 A 抽的，那么是否合法取决于这一次的卡是否在 A 的限定区间内，并且上一次 B 抽的卡是否在当前 B 的限定区间内。

注意到上一次 B 抽的卡可能是在很久很久之前，于是我们考虑将方案序列中的 0 和 1 看作整段考虑。

我们假设 $(l,r]$内方案序列都为 $0$，那么此序列合法需要满足：

1. $\forall p \in (l,r], r[p][0]\leq a[l] \leq r[p][1]$
2. $\forall p \in (l,r], l[p][0] \leq a[p] \leq l[p][1]$

第二个条件随便就能维护，第一个条件用一个 set<pair> 维护，元素为 $(a[l],l)$。

$1$的情况同理。

假设 $i-1$位已经维护完毕，维护第 $i$位。

我们记 $s[0/1]$表示当前序列中末尾为 $0/1$，上一个不同于末尾的数的合法位置。

以 $s[0]$的转移为例（此时 $s[0]$内是 $i-1$位的结果）。

第 $i – 1$位是 $0$：在满足 $l[i][0]\leq a[i]\leq l[i][1]$的前提下删掉 $s[0]$内不在区间 $[r[i][0],r[i][1]]$内的元素即可。

第 $i – 1$位是 $1$：在满足 $l[i][0]\leq a[i]\leq l[i][1]$的前提下，如果 $s[1]$内有元素，那么将 $(a[i-1],i-1)$加给 $s[0]$。

注意到要输出具体方案，我们记 $f[i][0]$表示第 $i$位为 $0$时，上一次的 $1$的位置。直接在 $s[0]$内随意找一个元素即可。$f[i][1]$同理。

时间复杂度 $O(n\log n)$

代码

//HomuraCat codes it!
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<queue>
#include<vector>
#include<set>
#include<cstdlib>
#include<iostream>
#include<utility>
#include<map>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 1000000007
#define lowbit(x) (x & -x)
#define N 100005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
#define pi std::pair<int, int>
inline ll read ()
{
    ll x = 0; bool flag = 0; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') flag = 1, ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    if (flag) x = -x; return x;
}
inline ll qabs (ll x) { return x < 0 ? -x : x; }
inline ll qpow (ll x, int y)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
int n, m, a[N], l[N][2], r[N][2], f[N][2], ans[N];
bool flag = 0;
std::set<pi> s[2];
int main ()
{
    n = read(); m = read();
    fo (i, 1, n)
    {
        a[i] = read();
        l[i][0] = read(); l[i][1] = read();
        r[i][0] = read(); r[i][1] = read();
    }
    if (l[1][0] <= a[1] && a[1] <= l[1][1] && r[1][0] == 0)
        s[0].insert(mp(0, 0));
    if (r[1][0] <= a[1] && a[1] <= r[1][1] && l[1][0] == 0)
        s[1].insert(mp(0, 0));

    fo (i, 2, n)
    {
        bool flag[2] = {0, 0};
        flag[0] = s[0].size() ? 1 : 0; flag[1] = s[1].size() ? 1 : 0;
        if (flag[1])
            s[0].insert(mp(a[i - 1], i - 1));
        if (flag[0])
            s[1].insert(mp(a[i - 1], i - 1));

        if (a[i] > l[i][1] || a[i] < l[i][0]) 
            s[0].clear();
        if (a[i] > r[i][1] || a[i] < r[i][0]) 
            s[1].clear();

        s[0].erase(s[0].begin(), s[0].lower_bound(mp(r[i][0], -1)));    
        s[0].erase(s[0].upper_bound(mp(r[i][1], n + 1)), s[0].end());
        s[1].erase(s[1].begin(), s[1].lower_bound(mp(l[i][0], -1)));
        s[1].erase(s[1].upper_bound(mp(l[i][1], n + 1)), s[1].end());

        if (!(s[0].size() || s[1].size())) break;
        if (s[0].size())
            f[i][0] = (*s[0].begin()).S;
        else
            f[i][0] = -1;
        if (s[1].size())
            f[i][1] = (*s[1].begin()).S;
        else
            f[i][1] = -1;
    }
    if (s[0].size() || s[1].size())
    {
        printf("Yes\n");
        int pos = n;
        bool now = f[pos][1] >= 0;
        while (pos)
        {
            int lst = pos;
            if (f[pos][now] >= 0)
            {
                pos = f[pos][now];
                fo (i, pos + 1, lst)
                    ans[i] = now;
                now ^= 1;
            }
        }
        fo (i, 1, n) printf("%d ", ans[i]);
    }
    else
        printf("No\n");
    return 0;
}