「CF1458E」Nim Shortcuts

发表于 分类于

$Link$

有一个两堆石子的 $Nim$ 游戏，但是多了 $n$ 个必败态 $(x_i,y_i)$，表示第一堆石子数为 $x_i$，第二堆石子为 $y_i$ 时，就无法执行任何操作了。（石子数量有序）

询问 $m$ 次，每次询问给你 $(a_i,b_i)$，你需要回答当第一堆石子数为 $a_i$，第二堆石子数为 $b_i$ 时，先手的胜负状态。

$1\le n,m\le10^5,0\le x_i,y_i,a_i,b_i\le10^9$。

一个状态 $(x,y)$ 必胜当且仅当 $(x,y)$ 正下方或者正左方存在必败点。

$n=0$ 时，容易得到只有 $(x,x)$ 必败。

$n=1$ 时，设唯一的多出来的必败态为 $(a,b)$：

  • 若 $a<b$，则 $\forall x\ge b,(x,x+1)$ 必败，相当于删去了第 $b$ 列后 $(x,x)$ 必败。

  • 若 $a=b$，没有影响。

  • 若 $a>b$，则 $\forall x\ge a,(x+1,x)$ 必败，相当于删去了第 $a$ 行后 $(x,x)$ 必败。

再考虑一般情况，对于所有点 $(a,b)$，假设所有在这个点左下方的多出来的必败态删掉了 $u$ 行 $v$ 列，再令 $d=u-v$，那么 $(x,y)$ 必败当且仅当 $x=y+d$。

这时如果新增了一个必败点 $a,b$：

  • 若 $a<b+d$，则删去第 $b$ 列。
  • 若 $a>b+d$，则删去第 $a$ 行。

把修改和询问离线并离散化，按照 $x$ 为第一关键字，$y$ 为第二关键字排序，顺序做过去即可。

使用树状数组维护当前被删去的列数，支持单点插入和查询前缀和，时间复杂度 $O((n+m)\log n))$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int n, m;
struct Opt {
    int type, x, y;
    inline bool operator <(const Opt a) const
    {
        return x == a.x?(y == a.y?type < a.type:y < a.y):x < a.x;
    }
} opt[N * 2 + 1];
namespace BIT
{
int tr[N * 2 + 1];
inline int lowbit(int x)
{
    return x & (-x);
}
inline void add(int x)
{
    int u = x;

    while (u <= N * 2) {
        tr[u]++;
        u += lowbit(u);
    }
    return;
}
inline int query(int x)
{
    if (!x)
        return 0;

    int ans = 0, u = x;

    while (u) {
        ans += tr[u];
        u -= lowbit(u);
    }
    return ans;
}
}
int a[N * 2 + 1];
map<int, int> hhash;
int del[N * 2 + 1], delh, tot;
int ans[N + 1];

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        int x = read(), y = read();
        opt[i] = { 0, x, y };
        a[i] = y;
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        opt[n + i] = { i, x, y };
        a[n + i] = y;
    }
    sort(opt + 1, opt + n + m + 1);
    sort(a + 1, a + n + m + 1);
    for (int i = 1; i <= n + m; i++)
        if (!hhash[a[i]])
            hhash[a[i]] = ++tot;

    int la = -1;

    for (int i = 1; i <= n + m; i++) {
        if (!opt[i].type) {
            int d = delh - BIT::query(hhash[opt[i].y]);
            if (opt[i].x < opt[i].y + d) {
                if (!del[hhash[opt[i].y]]) {
                    del[hhash[opt[i].y]] = 1;
                    BIT::add(hhash[opt[i].y]);
                }
            }
            if (opt[i].x > opt[i].y + d) {
                if (la != opt[i].x) {
                    la = opt[i].x;
                    delh++;
                }
            }
        } else {
            if (!opt[i - 1].type && opt[i - 1].x == opt[i].x && opt[i - 1].y == opt[i].y) {
                ans[opt[i].type] = 1;
            } else {
                if (opt[i].x != la) {
                    int d = delh - BIT::query(hhash[opt[i].y]);
                    if (!del[hhash[opt[i].y]] && opt[i].x == opt[i].y + d)
                        ans[opt[i].type] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= m; i++)
        printf("%s\n", ans[i]?"LOSE":"WIN");
    return 0;
}