洛谷P3320 尋寶遊戲

2022-09-23 02:42:13 字數 2190 閱讀 3900

小b最近正在玩一個尋寶遊戲,這個遊戲的地圖中有n個村莊和n-1條道路,並且任何兩個村莊之間有且僅有一條路徑可達。遊戲開始時,玩家可以任意選擇一個村莊,瞬間轉移到這個村莊,然後可以任意在地圖的道路上行走,若走到某個村莊中有寶物,則視為找到該村莊內的寶物,直到找到所有寶物並返回到最初轉移到的村莊為止。

小b希望評測一下這個遊戲的難度,因此他需要知道玩家找到所有寶物需要行走的最短路程。但是這個遊戲中寶物經常變化,有時某個村莊中會突然出現寶物,有時某個村莊內的寶物會突然消失,因此小b需要不斷地更新資料,但是小b太懶了,不願意自己計算,因此他向你求助。為了簡化問題,我們認為最開始時所有村莊內均沒有寶物

假設1為樹根,求出每一個點的\(dfs\)序,那麼要便利現在所有的寶藏且路徑最短,只需按照\(dfs\)序排序,然後依次走一遍即可。

所以我們需要一個支援插入、求前驅後繼、刪除的資料結構,為了滿足\(dfs\)序最小的要和\(dfs\)序最大的也連在一起,又需要支援查詢最值。這明顯是平衡樹的板子,直接大力上\(treap\)即可。

當然,權值線段樹和二分+樹狀陣列也可以達到同樣效果。

時間複雜度\(o(m\log n)\)。

別問我為什麼打了兩份。。。我一開始寫treap以為寫炸了,本地全對,交上去\(0pts\)。於是改寫bit+二分,後來寫完之後發現原來那份忘記關\(freopen\)了。。。

#include #include #include using namespace std;

typedef long long ll;

const int n=100010,lg=20,inf=1e9;

int n,m,tot,root,head[n],dfn[n],rk[n],f[n][lg+1],dep[n];

ll ans,dis[n];

bool flag[n];

struct edge

e[n*2];

void add(int from,int to,int dis)

void dfs(int x,int fa)

}int lca(int x,int y)

struct treenode

;struct treap

void update(int x)

void build()

void zig(int &x)

void zag(int &x)

void insert(int &x,int val)

if (t[x].val==val)

if (val1)

if (t[x].lc || t[x].rc)

else x=0;

return;

} if (val=rank)

return t[x].val;

if (rank<=t[t[x].lc].size) return get_val(t[x].lc,rank);

else return get_val(t[x].rc,rank-t[t[x].lc].size-t[x].cnt); }

int pre(int x,int val)

int min(int x)

int max(int x)

}treap;

int main()

e[n*2];

struct bit

void add(int x,ll val)

int ask(int x)

}bit;

void add(int from,int to,int dis)

void dfs(int x,int fa)

}int lca(int x,int y)

int binary(int k)

return r+1;

}int main()

if (1<=q && q<=n)

if (1<=p && p<=n && 1<=q && q<=n)

bit.add(dfn[x],1);

cnt++;

} else

if (1<=q && q<=n)

if (1<=p && p<=n && 1<=q && q<=n)

bit.add(dfn[x],-1);

cnt--;

} flag[x]^=1;

printf("%lld\n",ans);

} return 0;

}

洛谷P3320 SDOI2015 尋寶遊戲

小b最近正在玩一個尋寶遊戲,這個遊戲的地圖中有n個村莊和n 1條道路,並且任何兩個村莊之間有且僅有一條路徑可達。遊戲開始時,玩家可以任意選擇一個村莊,瞬間轉移到這個村莊,然後可以任意在地圖的道路上行走,若走到某個村莊中有寶物,則視為找到該村莊內的寶物,直到找到所有寶物並返回到最初轉移到的村莊為止。 ...

P3320 SDOI2015 尋寶遊戲

洛谷 給你一棵樹,每個邊都有一個邊權。對於一個點有兩個狀態 0 1 表示這個點是否需要被經過。有 m 組詢問,每次 會把一個點的狀態取反。對...

P3320 SDOI2015 尋寶遊戲(LCA)

題目 首先按照dfs序弄個時間戳 將要訪問的點按照時間戳順序 兩兩求距離即為答案 反正就是用資料結構維護這個順序 用set好題 include define re return define ll long long define dec i l r for int i l i r i define...