洛谷P3899 談笑風生

2022-07-28 07:32:16 字數 1298 閱讀 6839

題目大意:給定一棵 n 個節點的有根樹,1 號節點為根節點,現給出 q 個詢問,每次詢問距離 u 號節點不超過 k 的節點 b,c 為 a 與 b 的後代,求這樣的三元組有多少個。

題解:學會了線段樹合併。

由於之前對線段樹合併理解的不深刻,導致狂 wa 不止qaq。

需要統計

\[\sum_ \operatorname((b)-1)

\]這是一個二維數點問題,可以在一個維度上建立權值線段樹,在另一個維度上統計權值和即可。

需要將詢問離線處理,因為當 n 棵線段樹合併完畢時,對於子節點的線段樹來說,裡面不僅有自己子樹的權值,也有其他子樹的權值(合併導致)。因此,需要在遞迴遍歷每個節點時,在遞迴結束時進行對每個節點統計詢問,最後統一輸出即可。

時間複雜度和空間複雜度均為 \(o(nlogn)\)。

**如下

#include #define pb push_back

using namespace std;

const int maxn=1e5+10;

typedef long long ll;

int n,a[maxn],d[maxn],cnt,ans[maxn];

vectorg[maxn];

struct nodet[maxn*20];

int tot,root[maxn];

inline void pushup(int o)

void insert(int &o,int l,int r,int pos)

int mid=l+r>>1;

if(pos<=mid)insert(ls(o),l,mid,pos);

else insert(rs(o),mid+1,r,pos);

pushup(o);

}int query(int o,int l,int r,int x,int y)

int merge(int x,int y,int l,int r)

int mid=l+r>>1;

ls(x)=merge(ls(x),ls(y),l,mid);

rs(x)=merge(rs(x),rs(y),mid+1,r);

return pushup(x),x;

}void read_and_parse()

void dfs(int u)

ans[u]=t[root[u]].sz-query(root[u],1,n,1,a[u]-1);

insert(root[u],1,n,a[u]);

}void solve()

int main()

洛谷P3899 湖南集訓 談笑風生 線段樹合併

題目連結 線段樹合併板子題,目前我看到兩種寫法,分別是這樣的。 前一種每次需要新建一個節點,空間是 o 4nlogn 後者不需要新建,空間是 o nlogn 面向資料算空間你懂得 ,但是需要離線,因為共用節點的緣故,之後的修改可能會修改到不需要修改的節點 好繞啊 這題就是把向上向下的貢獻分開算,然後...

題解 P3899 湖南集訓 談笑風生

luogu智慧推薦給我搞的這個題啊,亦可賽艇! 題目連結 題目大意 和wallace談笑風生,給定一棵有根樹,多次詢問給定點 p 和限制 k ,求有多少對有序三元組 p b c 滿足 p b 均為 c 的祖先且 p b 間距離不超過 k 主席樹,樹上差分 分析 首先我們分類討論一下 如果點 b 在點...

P3899 湖南集訓 談笑風生 線段樹合併)

設 t 為一棵有根樹,我們做如下的定義 設 a 和 b 為 t 中的兩個不同節點。如果 a 是 b 的祖先,那麼稱 a 比 b 不知道高明到 去了 。 設 a 和 b 為 t 中的兩個不同節點。如果 a 與 b 在樹上的距離不超過某個給定常數 x,那麼稱 a 與 b 談笑風生 。 給定一棵 n 個節...