2025-10-06 04:58:38【DAG博弈+主席树】Wannafly挑战赛15 F 下棋

S

o

u

r

c

e

:

Source:

Source:Wannafly挑战赛15

I

d

e

a

:

Idea:

Idea: 有向无环图直接求每个点的sg，放棋子相当于是一个新点。每个棋子对应一个游戏，最后求nim游戏和。那么问题在于求

m

e

x

[

L

,

R

]

mex[L,R]

mex[L,R]，用莫队+分块直接就能做。 然后学习一波主席树的做法。对于

m

e

x

[

L

,

R

]

mex[L,R]

mex[L,R],相当于在前缀

1

−

R

1-R

1−R，由sg值构成权值线段树，每个点存其出现的最大位置，那么二分出现位置小于L的最小sg值。

C

o

d

e

:

Code:

Code:

#include

using namespace std;

#define fi first

#define se second

#define pb push_back

#define ALL(X) (X).begin(), (X).end()

#define CLR(A, X) memset(A, X, sizeof(A))

#define bitcount(X) __builtin_popcountll(X)

typedef double DB;

typedef long long LL;

typedef pair PII;

const int INF = 0x3f3f3f3f;

const int N = 1e5+10;

int cnt[N], sg[N];

vector G[N];

struct Node { int l, r, d; } T[N*20];

int root[N], qv, qd, node_cnt;

void build(int &o, int L, int R, int pre) {

o = ++node_cnt;

T[o] = T[pre];

if(L == R) {

T[o].d = qd;

return;

}

int M = (L+R)>>1;

if(qv <= M) build(T[o].l, L, M, T[pre].l);

else build(T[o].r, M+1, R, T[pre].r);

T[o].d = min(T[T[o].l].d, T[T[o].r].d);

}

int query(int o, int L, int R, int k) {

if(L == R) return L;

int M = (L+R)>>1;

if(T[T[o].l].d < k) return query(T[o].l, L, M, k);

return query(T[o].r, M+1, R, k);

}

int main() {

int n, m, q;

scanf("%d%d%d", &n, &m, &q);

while(m--) {

int u, v;

scanf("%d%d", &u, &v);

G[u].pb(v);

}

int mx = -1;

for(int i = 1; i <= n; i++) {

sg[i] = mx+1;

for(int v:G[i]) if(--cnt[sg[v]] == 0) {

sg[i] = min(sg[i], sg[v]);

}

for(int v:G[i]) cnt[sg[v]]++;

cnt[sg[i]]++;

mx = max(mx, sg[i]);

qv = sg[i], qd = i;

build(root[i], 0, n, root[i-1]);

}

int ans = 0;

while(q--) {

int l, r;

scanf("%d%d", &l, &r);

ans ^= query(root[r], 0, n, l);

}

printf("%s\n", ans?"Alice":"Bob");

return 0;

}