洛谷P4556 雨天的尾巴 模板 線段樹合併

2022-09-23 07:07:05 字數 1710 閱讀 6046

因為一開始沒有理解透徹線段樹合併,一直錯樣例。。。

然後想著“反正除錯也調不出什麼”,然後盯著\(merge\)看了\(1.5h\),對著各種標程找錯。

最後放棄肉眼觀察,抱著試試看的心態去除錯。

結果發現是\(lca\)寫錯了。。。我帶你們打。。。

首先村落裡的一共有\(n\)座房屋,並形成一個樹狀結構。然後救濟糧分\(m\)次發放,每次選擇兩個房屋\((x,y)\),然後對於\(x\)到\(y\)的路徑上(含\(x\)和\(y\))每座房子裡發放一袋\(z\)型別的救濟糧。

然後深繪里想知道,當所有的救濟糧發放完畢後,每座房子裡存放的最多的是哪種救濟糧。

線段樹合併模板。

我們在樹的每一個節點處開一棵動態開點的線段樹,線段樹的一個葉子結點\([x,x]\)表示這個(樹的而不是線段樹的)節點有多少個\(x\)型號的救濟糧。維護區間\(max\)以及它的位置\(pos\)。

那麼對於一個修改操作\(x,y,k\),求出\(x,y\)的\(lca\)點\(z\),然後差分思想,在\(x,y\)兩個節點的線段樹的\(k\)處\(+1\),\(z\)和\(fa[z]\)兩個節點的線段樹的\(k\)處\(-1\)。

修改操作完成後,從下往上線段樹合併。合併完\(x\)為根的子樹時,就可以統計\(x\)的答案了。

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

#include #include #include using namespace std;

const int n=100010,lg=18;

int n,m,tot,head[n],f[n][lg+1],dep[n],rt[n],u[n],v[n],z[n],b[n],ans[n];

struct edge

e[n*2];

void add(int from,int to)

void dfs1(int x,int fa)

int lca(int x,int y)

struct treenode

;struct tree

else

}void update(int &x,int l,int r,int k,int val)

int mid=(l+r)>>1;

if (k<=mid) update(tree[x].lc,l,mid,k,val);

else update(tree[x].rc,mid+1,r,k,val);

pushup(x); }

void merge(int &x,int y,int l,int r) }

}tree;

void dfs2(int x)

if (tree.tree[rt[x]].maxn) ans[x]=tree.tree[rt[x]].pos;

}int main()

dfs1(1,0);

for (int i=1;i<=m;i++)

sort(b+1,b+1+m);

tot=unique(b+1,b+1+m)-b-1;

for (int i=1;i<=m;i++)

z[i]=lower_bound(b+1,b+1+tot,z[i])-b;

for (int i=1;i<=m;i++)

dfs2(1);

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

printf("%d\n",b[ans[i]]);

return 0;

}

洛谷P4556 雨天的尾巴(線段樹合併)

題目連結 題解 因為一個點可能存放多種物品,直接開二維陣列進行統計時間 空間複雜度都不能承受。因為每一個點所擁有的物品只與其子樹中的點有關,...

洛咕 P4556 Vani有約會 雨天的尾巴

終於把考試題清完了。。。又復活了。。。 樹上差分,合併用線段樹合併,但是空間會炸。 某大佬 lca和fa lca 減得時候一定已經存在這個節...