魔术帽游戏 [倍增

魔术帽游戏 [倍增_隐 III]

$mathcal{Solution}$

建图过程:

交换操作 可以看作魔术球在 帽子序列 中的移动,
使用每个魔术帽的位置为编号建图,
操作序列中的 $a, b$ 连两条 有向边, 分别为 $a$ -> $b$ 和 $a$ <- $b$ , 边权为当前 操作序号

带有小球的帽子交换一次, 表示小球走过一条边,
设该边编号为 $i$ , 到达了 $k$ 点, 则小球的下一次移动必定会经过满足以下条件的边 $↓$

与 $k$ 相连的
边的权值大于 $i$ 的所有边中 最小的那一条

对第二个条件的解释: 操作顺序在 $i$ 后, 继 $i$ 后下一次直接改变小球的位置的操作所代表的边.

对于加速该操作, 可以使用如代码中所示 $Fk_1[i, 0]=nxt[i 异或 1]$ , 然而这样会导致不可预料的 $bug$ (如最下方代码), 所以要谨慎使用

于是在一个固定的操作序列中, 即固定的图中, 小球的起点边一旦确定, 其路径也会随之固定,
确认了这一点之后, 使用倍增加速 $↓$

从魔术球所在的帽子所连出的边中寻找 $l$ 操作
魔术球从 $l$ 到 $r$ 的移动

$mathcal{Code}$

#include<bits/stdc++.h>
#define reg register

const int maxn = 2000005;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

struct Edge{ int nxt, to, w; } edge[maxn << 1];

int N;
int M;
int Q;
int num0;
int a[maxn];
int b[maxn];
int head[maxn];
int Fk_1[maxn][20];
int Fk_2[maxn][20];

void Add(int from, int to, int w){
        edge[++ num0] = (Edge){ head[from], to, w };
        head[from] = num0;
}

int main(){
        freopen("magic.in", "r", stdin);
        freopen("magic.out", "w", stdout);
        N = read();
        M = read();
        Q = read();
        for(reg int i = 1; i <= M; i ++) a[i] = read(), b[i] = read();
        num0 = 1, edge[0].w = 0x7f7f7f7f;
        for(reg int i = M; i >= 1; i --) Add(a[i], b[i], i), Add(b[i], a[i], i);
        for(reg int i = 2; i <= num0; i ++){
                Fk_1[i][0] = edge[i^1].nxt;
                Fk_2[i][0] = edge[i].nxt;
        } 
        for(reg int j = 1; j <= 19; j ++)
                for(reg int i = 2; i <= num0; i ++){
                        Fk_1[i][j] = Fk_1[Fk_1[i][j-1]][j-1]; 
                        Fk_2[i][j] = Fk_2[Fk_2[i][j-1]][j-1];
                }
        for(reg int i = 1; i <= Q; i ++){
                int x = read();
                int l = read();
                int r = read();
                int t = head[x];
                for(reg int i = 19; i >= 0; i --)
                        if(edge[Fk_2[t][i]].w < l) t = Fk_2[t][i];
                if(edge[t].w < l) t = Fk_2[t][0];
                t = edge[t].w>r?0:t;
                for(reg int i = 19; i >= 0; i --)
                        if(edge[Fk_1[t][i]].w <= r) t = Fk_1[t][i];
                printf("%d
", edge[t].to?edge[t].to:x);
        }
        return 0;
}

$mathcal{Code with bug}$

为什么以 $0$ 为第一条边就 $WA$ 掉了…

#include<bits/stdc++.h>
#define reg register

const int maxn = 2000005;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

struct Edge{ int nxt, to, w; } edge[maxn << 1];

int N;
int M;
int Q;
int num0;
int a[maxn];
int b[maxn];
int head[maxn];
int Fk_1[maxn][22];
int Fk_2[maxn][22];

void Add(int from, int to, int w){
        edge[num0] = (Edge){ head[from], to, w };
        head[from] = num0 ++;
}

int main(){
        freopen("magic.in", "r", stdin);
        freopen("magic.out", "w", stdout);
        N = read();
        M = read();
        Q = read();
        for(reg int i = 1; i <= M; i ++) a[i] = read(), b[i] = read();
        memset(head, -1, sizeof head);
        for(reg int i = M; i >= 1; i --) Add(a[i], b[i], i), Add(b[i], a[i], i);
        for(reg int i = 0; i < num0; i ++){
                Fk_1[i][0] = edge[i^1].nxt;
                Fk_2[i][0] = edge[i].nxt;
        } 
        for(reg int j = 1; j <= 20; j ++)
                for(reg int i = 0; i <= num0; i ++){
                        Fk_1[i][j] = Fk_1[Fk_1[i][j-1]][j-1]; 
                        Fk_2[i][j] = Fk_2[Fk_2[i][j-1]][j-1];
                }
        for(reg int i = 1; i <= Q; i ++){
                int x = read();
                int l = read();
                int r = read();
                int t = head[x];

                if(t == -1){ printf("%d
", x); continue ; }

                for(reg int i = 20; i >= 0; i --){
                        if(Fk_2[t][i] == -1) continue ;
                        if(edge[Fk_2[t][i]].w < l) t = Fk_2[t][i];
                }

                if(edge[t].w < l) t = Fk_2[t][0];

                if(t == -1 || edge[t].w > r){ printf("%d
", x); continue ; }

                for(reg int i = 20; i >= 0; i --){
                        if(Fk_1[t][i] == -1) continue ;
                        if(edge[Fk_1[t][i]].w <= r) t = Fk_1[t][i];
                }

                printf("%d
", edge[t].to?edge[t].to:x);

        }
        return 0;
}